Общая задача линейного программирования. Двойственность в задачах линейного программирования. Анализ решения задач линейного программирования.




Лабораторная работа № 6.

Цель работы:

1) ознакомиться с теорией двойственности;

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

Теоретические сведения

Каждой задаче линейной оптимизации можно поставить в соответствие задачу, называемую двойственной к ней.

Пусть дана общая задача линейной оптимизации (исходная задача):

произвольного знака при .

Двойственная к ней задача имеет вид:

произвольного знака при .

Двойственная задача строится по следующим правилам:

1) упорядочивается запись исходной задачи, т.е. если целевая функция задачи максимизируется, то ограничения неравенства должны быть вида £, если минимизируется — то вида ³. Выполнение этих условий достигается умножением соответствующих ограничений на (-1);

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

3) каждой переменной двойственной задачи соответствует i -е ограничение исходной задачи, и, наоборот, каждой переменной прямой задачи соответствует j -e ограничение двойственной задачи;

4) матрица из коэффициентов при неизвестных двойственной задачи образуется транспонированием матрицы, составленной из коэффициентов при неизвестных системы ограничений исходной задачи;

5) если на j -ю переменную исходной задачи наложено условие неотрицательности, то
j-e ограничение двойственной задачи будет неравенством, в противном случае j- e ограничение будет равенством; аналогично связаны между собой ограничения исходной задачи и переменные двойственной.

Дадим экономическую интерпретацию пары двойственных задач.

Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами которые могут использоваться для выпуска п видов продукции. Пусть также известны стоимость единицы j -го вида продукции и норма потребления i -го ресурса на производство единицы j -й продукции — аij.

Требуется определить объем производства продукции каждого вида , максимизирующий суммарную стоимость

При этом расход ресурсов не должен превышать их наличия:

Все неизвестные по своему экономическому смыслу неотрицательны:

По исходным данным сформулируем другую экономическую задачу (двойственную).

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

Математическая модель задачи имеет вид

Здесь — общая оценка ресурсов. Каждое j -е ограничение из системы представляет собой неравенство, левая часть которого равна оценке всех ресурсов, расходуемых на производство единицы j- го вида продукции, а правая — стоимости единицы этой продукции.

Порядок выполнения работы

1 Ознакомиться с теоретическими сведениями.

2 - Построить двойственную задачу к заданной (прямой) задаче (номер задачи выбирает преподаватель).

- Решить одну из пары двойственных задач и по найденному решению найти решение второй задачи.

- Объяснить смысл всех переменных участвующих в решении задачи.

- Указать наиболее дефицитный и избыточный ресурс, если он имеется.

Содержание отчета:

1 Тема и цель работы.

2 Условия задач.

3 Ход решения, результаты.

4 Выводы по работе.

Список задач

№ вар. Составить задачу, двойственную к указанной. № вар.
I Z = 2x1 ‑ x2 + x3 ‑3x4 +x5 max x1,3 ³ 0 Z = 7x1 + 6x2 + 3x3 –x4 min x2,3 ³ 0 II
III Z = 2x1 ‑ x2 + x3 + x4 ‑ 2x5 max x1,2,4 ³ 0 Z = x1 + 2x2 + 3x3 +x4 max x4 ³ 0 IV
V Z = x1 + x2 + x3 max x1,2 ³ 0 Z = x1 + 2x2 + 3x3 +4x4 +5x5 min x1,2 ³ 0; x5 £ 0 VI
VII Z = x1 ‑ x2 ‑ 2x3 -3x4 min x1,2,3 ³ 0 Z = x1 ‑ 10x2 + 2x3 ‑ x4 +7x5 max x1,3 ³ 0 VIII
IX Z = 7x1 + 6x2 + 3x3 ‑ x4 max x2,3 ³ 0 Z = x2 ‑ x3 +x4 min x1,3 ³ 0 X
XI XII
XIII VX
XV XVI


Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-11-19 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: