Учебная работа № 5392. «Контрольная Двойственная задача линейного программирования (задача)
Учебная работа № 5392. «Контрольная Двойственная задача линейного программирования (задача)
Содержание:
«Дана каноническая задача линейного программирования и ее оптимальное решение. Требуется
1. Построить двойственную задачу линейного программирования
2. На основе теорем двойственности найти оптимальное решение двойственной задачи.
f(x) = x1 — 3×2 — 2×3 max
3×1 + x2 — 2×3 — x4 = 13,
x1 — 3×2 + x3 = 1,
x1 + 2×2 + 3×3 + x5 = 11,
xj ?0, j = 1,…., 5.
x* = (7, 2, 0, 10, 0)
»
Выдержка из похожей работы
Построим задачу, двойственную данной,
если исходная задача имеет вид:
Прежде чем приступить
к построению двойственной задачи, нам
предстоит «причесать» данную систему
ограничений, ибо она состоит из двух
неравенств разного смысла,
Функция цели f
стремится к максимуму, поэтому смысл
обоих неравенств должен быть «≤»,
Умножив обе части первого неравенства
на -1, придем к задаче, для которой может
быть построена симметричная двойственная
задача,
Задача
1,
Задача 1 содержит
три неизвестных и два ограничения,
поэтому в двойственной должны быть,
напротив, две переменные, например y1
и
y2,
и три ограничения,
Задача
2,
записывается следующим образом:
Основные теоремы теории двойственности
Вернёмся к задачам
1 и 2, При их решении мы, в частности,
получили
,
Оптимальные значения функций цели
совпали, Случайно ли это? Ответ на этот
вопрос даёт первая теорема двойственности,
которую приведём без доказательства,
Теорема 1,
Если одна из взимно-двойственных задач
имеет оптимальный план, то другая также
имеет оптимальный план, При этом
соответствующие им оптимальные значения
функций цели
и
равны
между собой,
Познакомимся ещё
с одной интересной и полезной теоремой,
Она позволяет найти оптимальное решение
двойственной задачи, не решая её!
Называется эта теорема второй основной
теоремой двойственности, Прежде чем её
сформулировать, проделаем следующие
преобразования: ограничения
взаимно-двойственных задач запишем в
форме уравнений, К левой части каждого
неравенства в задаче 1 прибавим
вспомогательную неотрицательную
переменную, что поможет восстановить
нарушенный баланс:
(1)
Неотрицательные
«довески» позволили уравнять левые и
правые части ограничений,
Точно также поступим
и в отношении системы ограничений задачи
2, Только здесь неотрицательные
вспомогательные переменные придётся
вычитать из левых частей неравенств:
(2)
Системы линейных
уравнений (1) и (2) содержат по m
+ n
неизвестных, В первой из них n
основных и
m вспомогательных,
а во второй – наоборот: m
основных и
n
вспомогательных