Xreferat.com » Рефераты по информатике и программированию » Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

уровня Практикум по решению линейных задач математического программирования (т.е. прямую Практикум по решению линейных задач математического программирования, проходящую через начало координат).

Перемещаем линию уровня Практикум по решению линейных задач математического программирования параллельно самой себе в направлении вектора Практикум по решению линейных задач математического программирования (если задача на максимум (max)) или в противоположном направлении (если задача на минимум (min)) до тех пор, пока линия уровня имеет хотя бы одну общую точку с ОДР.

Находим координаты Практикум по решению линейных задач математического программирования этой общей крайней точки, решая систему уравнений прямых, на пересечении которых она находится.

Подставляем эти координаты в целевую функцию и находим ее max (или min).

Пример. Решить задачу линейного программирования графическим методом


Практикум по решению линейных задач математического программирования max

Практикум по решению линейных задач математического программирования


Решение. Третье и четвертое ограничения системы – двойные неравенства, преобразуем их к более привычному для подобных задач виду Практикум по решению линейных задач математического программирования, это Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования, т.о. первое из полученных неравенств Практикум по решению линейных задач математического программирования (или Практикум по решению линейных задач математического программирования) относится к условию неотрицательности, а второе Практикум по решению линейных задач математического программирования к системе ограничений. Аналогично, Практикум по решению линейных задач математического программирования это Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования.

Т.о. задача примет вид


Практикум по решению линейных задач математического программирования max

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования, Практикум по решению линейных задач математического программирования

Заменив знаки неравенств на знаки точных равенств, построим область допустимых решений по уравнениям прямых:

Практикум по решению линейных задач математического программирования; Практикум по решению линейных задач математического программирования; Практикум по решению линейных задач математического программирования; Практикум по решению линейных задач математического программирования.

Областью решений неравенств является пятиугольник ABCDE.

Построим вектор Практикум по решению линейных задач математического программирования. Через начало координат перпендикулярно вектору Практикум по решению линейных задач математического программирования проведем линию уровня Практикум по решению линейных задач математического программирования. И затем будем перемещать ее параллельно самой себе в направлении вектора Практикум по решению линейных задач математического программирования до точки выхода из области допустимых решений. Это будет точка С. Найдем координаты этой точки, решив систему, состоящую из уравнений первой и четвертой прямых:


Практикум по решению линейных задач математического программирования Практикум по решению линейных задач математического программирования Практикум по решению линейных задач математического программирования Практикум по решению линейных задач математического программированияПрактикум по решению линейных задач математического программирования Практикум по решению линейных задач математического программирования Практикум по решению линейных задач математического программирования.


Подставим координаты точки С в целевую функцию и найдем ее максимальное значение Практикум по решению линейных задач математического программированияПример. Построить линии уровня Практикум по решению линейных задач математического программирования и Практикум по решению линейных задач математического программирования для задачи линейного программирования:


Практикум по решению линейных задач математического программирования max (min)

Практикум по решению линейных задач математического программирования


Решение. Область допустимых решений – открытая область (рис. 6). Линия уровня Практикум по решению линейных задач математического программирования проходит через точку В. Функция Z имеет минимум в этой точке. Линию уровня Практикум по решению линейных задач математического программирования построить нельзя, так как нет точки выхода из области допустимых решений, это значит, что Практикум по решению линейных задач математического программирования.

Задания для самостоятельной работы.

Найти область решений системы неравенств:

а)Практикум по решению линейных задач математического программирования б)Практикум по решению линейных задач математического программирования


Решить графически задачу линейного программирования


Практикум по решению линейных задач математического программирования min

Практикум по решению линейных задач математического программирования


Составить экономико-математическую модель и решить графически задачу линейного программирования

Фирма выпускает изделия двух видов А и В. Изделия каждого вида обрабатывают на двух станках (I и II). Время обработки одного изделия каждого вида на станках, время работы станков за рабочую смену, прибыль фирмы от реализации одного изделия вида А и вида В занесены в таблицу:


Станки Время обработки одного изделия, мин. Время работы станка за смену, мин.

А В
I 10 20 1300
II 4 13 720
Прибыль от одного изделия, грн. 0,3 0,9

Изучение рынка сбыта показало, что ежедневный спрос на изделия вида В никогда не превышает спрос на изделия вида А более чем на 40 единиц, а спрос на изделия вида А не превышает 90 единиц в день.

Определить план производства изделий, обеспечивающий наибольшую прибыль.

Симплексный метод решения задач линейного программирования


Симплексный метод – это метод последовательного улучшения плана. Этим методом можно решать задачи линейного программирования с любым количеством переменных и ограничений.

Этот метод включает в себя три основные этапа:

Построение начального опорного плана.

Правило перехода к лучшему (точнее, нехудшему) решению.

Критерий проверки найденного решения на оптимальность.

При симплексном методе выполняются вычислительные процедуры (итерации) одного и того же типа в определенной последовательности до тех пор, пока не будет получен оптимальный план задачи или станет ясно, что его не существует.

1) Построение начального опорного плана.

Данную задачу линейного программирования необходимо сначала привести к каноническому виду; при этом правые части ограничений должны быть неотрицательными.

Признаком возможности построения начального опорного плана служит наличие в каждом ограничении-равенстве с неотрицательной правой частью базисной переменной.

Базисной называют плановую переменную, которая входит только в одно уравнение (а в другие не входит), и при этом имеет коэффициент, равный единице.

Пусть задача линейного программирования приведена к каноническому виду, и все уравнения системы ограничений имеют свою базисную переменную. Приравняв базисные переменные к соответствующим правым частям ограничений, а остальные переменные к нулю, получим опорное или базисное решение задачи.

Пример. Для данной задачи линейного программирования найти начальный опорный план (базисное решение).

Практикум по решению линейных задач математического программирования max

Практикум по решению линейных задач математического программирования


Решение. Изменим знаки второго и третьего неравенств на противоположные, умножив каждое из них на –1. Система ограничений теперь будет такой:


Практикум по решению линейных задач математического программирования


В каждом ограничении слева добавим положительную переменную Практикум по решению линейных задач математического программирования, соответственно запишем канонический вид задачи:


Практикум по решению линейных задач математического программирования max

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования.


Переменные Практикум по решению линейных задач математического программирования базисные. Приравниваем их к правым частям ограничений: Практикум по решению линейных задач математического программирования Все остальные переменные – свободные, приравниваем их к нулю: Практикум по решению линейных задач математического программирования

Запишем теперь начальный опорный план


Практикум по решению линейных задач математического программирования(0; 0; 0; 0; 16; 4; 0).


2) Составление симплексных таблиц. Критерий оптимальности.

Симплексный метод удобно применять, используя построение симплексных таблиц. Первая симплексная таблица, соответствующая начальному плану, имеет вид:


Базис

Практикум по решению линейных задач математического программирования

В

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

…

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования




Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

…

Практикум по решению линейных задач математического программирования


Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

…

Практикум по решению линейных задач математического программирования


Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

…

Практикум по решению линейных задач математического программирования


… … … … … … …

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

…

Практикум по решению линейных задач математического программирования


Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

Практикум по решению линейных задач математического программирования

…

Практикум по решению линейных задач математического программирования


Здесь приняты следующие обозначения.

Столбец «Базис» – это базисные переменные.

Столбец «Практикум по решению линейных задач математического программирования» – это коэффициенты при базисных переменных в целевой функции.

Столбец «В» – правые части ограничений;

Практикум по решению линейных задач математического программирования – коэффициенты при переменных в ограничениях;

Практикум по решению линейных задач математического программирования – коэффициенты при переменных в целевой функции.

Последняя строка в таблице (Практикум по решению линейных задач математического программирования) – это проверочная или оценочная строка.

Практикум по решению линейных задач математического программирования – значение целевой функции, соответствующее построенному начальному плану. Его находят так: каждый элемент столбца Практикум по решению линейных задач математического программирования умножают на соответствующий элемент столбца В и произведения складывают, т.е.


Практикум по решению линейных задач математического программирования.


Практикум по решению линейных задач математического программирования – называют оценками или симплексными разностями и находят так: элементы столбца Практикум по решению линейных задач математического программирования умножают на соответствующие элементы столбца Практикум по решению линейных задач математического программирования, складывают результаты и вычитают Практикум по решению линейных задач математического программирования.

Например,


Практикум по решению линейных задач математического программирования.


Оценки (Практикум по решению линейных задач математического программирования) базисных переменных всегда равны нулю.

Признак оптимальности опорного плана состоит в следующем:

Опорный план будет оптимальным тогда и только тогда, когда все оценки

Практикум по решению линейных задач математического программирования для задачи на max и

Практикум по решению линейных задач математического программирования для задачи на min.

Если критерии оптимальности не выполняются, то нужно перейти к нехудшему опорному плану, т.е. исключить из базиса некоторую переменную и ввести вместо нее новую из числа свободных переменных.

Переменная, которую нужно ввести в базис, соответствует той оценке Практикум по решению линейных задач математического программирования, которая не удовлетворяет условию оптимальности. Если таких оценок несколько, то среди них выбирают наибольшую по абсолютной величине и соответствующую ей переменную вводят в базис. Столбец с этой переменной называют разрешающим.

Для определения переменной, которую нужно вывести из базиса, поступают так: элементы столбца В делят только на положительные элементы разрешающего столбца и находят симплексные отношения Практикум по решению линейных задач математического программирования. Выбирают из Практикум по решению линейных задач математического программирования наименьшее. Оно называет ту переменную, которую нужно ввести в базис. Соответствующая строка таблицы называется разрешающей.

На пересечении разрешающего столбца и разрешающей строки находится разрешающий элемент.

Теперь начинаем заполнять следующую таблицу. Покажем этот процесс на конкретном примере.

Пример. Решить симплексным методом задачу линейного программирования.


Практикум по решению линейных задач математического программирования max

Практикум по решению линейных задач математического программирования


Решение. 1) Приводим задачу к каноническому виду, т.е. из ограничений неравенств делаем равенства.


Практикум по решению линейных задач математического программирования max

Практикум по решению линейных задач математического
    <div class=

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: