Практикум по решению линейных задач математического программирования
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
°пример, элемент найдем из прямоугольника
=
Или элемент = из прямоугольника
Оценки для новой таблицы можно находить по этому же правилу.
В целом, решение данной задачи симплексным методом в виде таблиц будет иметь вид
БазисВ2300000181310006016210100160501001050213000010230000таб. 10310103030112001105,535010010021300001715200030таб. 2
БазисВ2300002310103005002150135010010501200309121002030таб. 326100,20,60001000,40,21034010,40,20003000,61,80124000,80,600таб. 4
Оценочная строка четвертой таблицы показывает, что получен оптимальный план, так как все .
это значения из столбца В, т.е. , , , .
Свободные (небазисные) переменные .
Итак, = (6; 4; 0; 0; 1; 3),
= = 24.
Примечание: При переходе от таблицы к таблице для контроля сравнивают , которое должно быть не меньше предыдущего для задачи на максимум и не больше предыдущего для задачи на минимум.
При использовании симплексного метода возможны следующие случаи.
1) Если в оценочной строке симплекс-таблицы оценка = 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план.
2) Если при переходе от одного опорного плана к другому в разрешающем столбце нет положительных элементов, то это означает, что целевая функция ЗЛП является неограниченной и оптимальных планов не существует.
Задания для самостоятельной работы.
Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:
а) max
б) min
Понятие двойственности
1) Симметричные двойственные задачи
Рассмотрим задачу производственного планирования. Пусть предприятие имеет m видов ресурсов объемом единиц. Эти ресурсы должны быть использованы для выпуска n видов продукции. Пусть норма потребления i-го вида ресурса на производство единицы j-ой продукции; цена реализации j-ой продукции; объем производства j-ой продукции, обеспечивающий предприятию максимальную выручку.
План производства следует составить из условия максимизации общей стоимости продукции при ограничениях на использовании ресурсов
,
Или в краткой форме записи математическая модель задачи имеет вид:
(1)
, (2)
, (3)
Задачу (1) (3) называют исходной.
По исходным данным задачи (1) (3) сформируем другую экономическую задачу.
Предположим, что предприятию разрешено на его усмотрение реализовать все указанные ресурсы. Необходимо установить цены на них , , пользуясь следующими соображениями:
- покупатель стремится минимизировать их общую стоимость;
- предприятие согласно продать по ценам, дающим прибыль не меньшую, чем выручка, которую оно может получить от реализации изготовленной продукции.
Эти требования можно записать в виде следующей ЗЛП:
,
Или в краткой форме записи:
(4)
, (5)
, (6)
Полученную задачу (4) (6) называют двойственной. Переменные называются двойственными оценками, или теневыми ценами.
Задачи (1) (3) и (4) (6) называют парой взаимно двойственных симметричных задач, т.к. они обладают следующими свойствами:
- Если в одной задаче ищется максимум целевой функции, то в другой минимум.
- Коэффициенты при переменных в целевой функции одной задачи являются правыми частями ограничений другой задачи и, наоборот.
- В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла: если задача на max, то все неравенства содержат знаки
, если на min, то все неравенства содержат знаки .
- Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
- Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи.
- Условие неотрицательности переменных сохраняется в обеих задачах.
Примечание: Понятие прямой и двойственной задач условно.
2) Построение модели двойственной задачи
Используя свойства (16), покажем на конкретном примере построение двойственной задачи.
Пример. Пусть исходная задача имеет вид:
,
Нужно составить к ней двойственную.
Решение. Запишем расширенную матрицу системы ограничений и транспонируем ее.
11221251122134АТ=11113А =511323121111212431min231max
Теперь запишем двойственную задачу по АТ с переменными , .
, .
Пример. К заданной задаче записать двойственную:
Решение. Так как задача на min, то все неравенства должны иметь знаки . С этой целью второе ограничение умножим на (1); при этом знак неравенства изменится на противоположный. Теперь задача будет иметь вид:
,
Запишем матрицы А и АТ.
111125А =235АТ=13252min15max
Двойственная задача:
, .
3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задач
Рассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции П1, П2, П3. Для этого оно располагает объемами ресурсов 3-х видов Р1, Р2, Р3. Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:
Пj
РiП1П2П3Объем
Р1421180Р2311210Р3125244Цена
101412
Требуется: