Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная

Каждой исходной задаче линейного программирования соответствует двойственная задача. Исходная задача называется прямой.

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

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

2. Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функций двойственных задач равны.

3. Критерий оптимальности. Пусть Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru — целевая функция исходной задачи, а Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru — целевая функция двойственной задачи; Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru — допустимое решение исходной задачи, а Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru — допустимое решение двойственной задачи. Если для этой пары двойственных задач выполняется равенство Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , то Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru и Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru являются оптимальными решениями соответствующих задач (справедливо и обратное утверждение).

Рассмотрим ЗЛП в общем виде. Построим задачу двойственную к исходной. При переходе к двойственно задаче, нужно соблюдать правила, которые указаны на рис. 1.9.

Правила построения двойственной задачи

Задача максимизации z Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru w x Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru u Задача минимизации
Ограничения Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Переменные
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
= Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Свободная
Переменные Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Ограничения
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Свободная Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru =

Рис. 1.9. Построение двойственной задачи

Пример 1

Задача максимизации       Задача минимизации
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   z w   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Ограничения   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Условия на переменные
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru = Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Сво- бод. Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru свободная
Условия на переменные   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Ограничения
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru свободная   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru = Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru

В матричном виде

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Ограничения   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Переменные
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru = Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Своб. Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Переменные   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Ограничения
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Своб. Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru = Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru   Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru ; Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru

Задача максимизации переходит в задачу минимизации, и наоборот.

Количество переменных двойственной задачи Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru равно количеству ограничений исходной задачи. Ограничения исходной задачи формируют условия на знак новых переменных.

Количество переменных исходной задачи Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru равно количеству ограничений исходной задачи. Если Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , тогда число ограничений двойственной задачи равно Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru . Знак исходных переменных формируют условия на знак новых ограничений.

Для нахождения допустимого плана Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru двойственной задачи нужно найти план, который удовлетворяет всем ограничениям двойственной задачи и условиям на переменные.

При этом дополнительно используются условия дополняющей нежесткости:

а). Если для допустимого плана Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru нестрогое неравенство в ограничениях исходной задачи выполняется как строгое, то есть Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru или Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , то соответствующая переменная допустимого плана двойственной задачи равна нулю Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

Если Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru . (1.19)

Например, если Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , тогда Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru (см. пример 1).

б). Если для допустимого плана некоторая переменная строго больше (меньше) нуля, Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , то соответствующее неравенство двойственной задачи выполняется как равенство для Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

Если Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru . (1.20)

Например, если Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , тогда Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

Используя эти условия, получаем систему линейных уравнений для нахождения Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

Задача 1. Небольшая фабрика изготовляет два вида удобрений. Продукция обоих видов поступает в оптовую продажу. Для производства удобрений используются два вида сырья A и B.

Максимально возможные суточные запасы сырья составляют 24 и 6 т соответственно. Расходы сырья A и B на 1 т на производство удобрения приведены в таблице.

Исходное сырье Расход сырья, т на тонну   Максимально возможный запас, т
  Удобрение 1 вида Удобрение 2 вида
А
В

Изучение рынка сбыта показало, что суточный спрос на удобрение 2 никогда не превышает спроса на удобрение 1 более чем на 1 т. Кроме того, установлено, что спрос на удобрение 1 никогда не превышает 2 т в сутки.

Оптовые цены одной тонны удобрения равны: 5 тыс. долларов для удобрения 1 и 4 тыс. долларов для удобрения 2.

Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

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

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

1. Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

2. Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

3. Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

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

Исходная задача является задачей максимизации, следовательно, двойственная будет задачей минимизации.

Исходная задача имеет 4 ограничения, следовательно, количество переменных двойственной задачи равно 4.

Количество переменных исходной задачи равно 2, следовательно двойственная задача будет иметь 2 ограничения.

Исходная задача Двойственная задача
Задача максимизации Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Задача минимизации Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru
Исходная задача Двойственная задача
Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru

1. Проверим план Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru на допустимость и оптимальность.

Проверка плана на допустимость. Очевидно, что план не является допустимым, так как нарушено условие неотрицательности переменных, Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

2. Проверим план Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

Проверка плана на допустимость.

а). Подставим в неравенства ограничений на ресурсы.

(1) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как строгое неравенство Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru по условию дополняющей нежесткости (1.19).

(2) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как строгое неравенство Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru по условию дополняющей нежесткости.

(3) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как равенство,

(4) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как равенство.

ВСЕ ограничения на ресурсы выполнены.

б) Проверим условия на переменные:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru строгое неравенство Þ соответствующее неравенство для Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru превратиться в равенство:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru ;

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru строгое неравенство Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ соответствующее неравенство для Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru превратиться в равенство:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

ВСЕ условия на переменные выполнены.

Все ограничения на ресурсы выполнены, и все условия на переменные выполнены Þ план Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru допустимый.

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

Имеем систему уравнений:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru

Одна из переменных отрицательна, Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , что не удовлетворяет условию двойственной задачи, следовательно, решение двойственной задачи не является допустимым.

Таким образом, решение исходной задачи Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru допустимо, но не оптимально. Оно не удовлетворяет критерию оптимальности.

3.Проверим план Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

Проверка плана на допустимость.

а). Подставим в неравенства ограничений на ресурсы.

(1) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как равенство;

(2) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как равенство;

(3) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как строгое неравенство Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru по условию дополняющей нежесткости.

(4) Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru выполняется как строгое неравенство Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru по условию дополняющей нежесткости.

ВСЕ ограничения на ресурсы выполнены.

б) Проверим условия на переменные:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru строгое неравенство Þ соответствующее неравенство для Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru превратиться в равенство:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru ;

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru строгое неравенство Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ соответствующее неравенство для Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru превратиться в равенство:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru .

ВСЕ условия на переменные выполнены.

Все ограничения на ресурсы выполнены, и все условия на переменные выполнены Þ план Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru допустимый.

Проверка плана на оптимальность.

Рассмотрим систему уравнений:

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru Þ Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru

Все условия на переменные и неравенства выполнены, следовательно, решение двойственной задачи является допустимым.

Проверим критерий оптимальности. Если Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , где Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru и Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru являются допустимыми планами исходной и двойственной задач соответственно, тогда эти планы являются оптимальными.

Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru , Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru

План Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru является оптимальным планом исходной задачи, план Линейного программирования. Каждой исходной задаче линейного программирования соответствует двойственная - student2.ru является оптимальным планом двойственной задачи.

Наши рекомендации