Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Пусть прямая задача имеет вид основной ЗЛП:

(3.31)

 

 

Двойственная к ней ЗЛП имеет вид:

; (3.32)

.

Предположим, что ЗЛП (3.31) имеет решение. Решения обеих задач могут быть записаны в виде (смотри доказательство теоремы 3.4):

= ; = ,

где = = (, …, )

матрица, обратная для базисной подматрицы . Матрица подматрицы .

Из следствия 1 к теореме 3.4:

, , (3.33)

 

откуда следует, что i-я компонента решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы , определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы () равна разности между левой и правой частями ограничений двойственной ЗЛП:

= . (3.34)

Пример 3.8.Решить следующую ЗЛП:

max (4Х1 + Х2 + 2Х3 + 3Х4);

Х1 +2Х2 + 3Х3 – Х5 + Х7 = 50;

–3Х23 + Х4 +2Х5 + 4Х7 = 10;

2 + Х5 + Х6 – 1/2 Х7 = 24;

.

 

Найти решение двойственной задачи.

Так как расширенная матрица

 

=

системы линейных уравнений ИЗ является К -матрицей, то ИЗ можно решить симплекс-методом. Результаты решения приведены в таблице:

 

        –3     –1   –1/2
= 230   –2            
              –3/2 11/4 1/4 –1/2 3/4 1/4 5/4 29/8 –1/8  
= 242         5/2 1/2 63/4  

 

На первой итерации получен оптимальный план ЗЛП (4.24).

= (1, 4, 2); = (38, 28, 6),

= (38, 6, 0, 28, 0, 0, 0); f () = 242.

Запишем ДЗ:

 

min(50Y1 + 10Y2 +24Y3); Y1 ≥ 4; 2Y1 – 3Y2 + 4Y3 ≥ 1; 3Y1 + Y2 ≥ 2.    
Y2 ≥ 3; –Y1 +2Y2 + Y3 ≥ 0; Y3 ≥ 0; Y1 + 4Y2 – 1/2 Y3 ≥ 0.  
не ограничены в знаке.  

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

Находим решение ДЗ по формуле 3.21.

= = (4, 3, 1) = (4, 3, 1/2)

или (3.33):

= (0 + 4, 0 + 3, + 0) = (4, 3, );

= 50´ 4 + 10´ 3 + 24 ´ = 242.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.