Глава 9 теория двойственности

Глава 9 теория двойственности

Здесь матрица (ctj) — единичная, а все числа последней строки равны нулю . Теорема доказана.

В заключение мы хотим подчеркнуть еще раз то обстоятельство, что симплекс-метод всегда приводит к базисному решению.

Если не помнить этого обстоятельства, то можно прийти к курьезам. Один из таких случаев описан в литературе по линейному программированию и связан с рассмотренной нами ранее задачей о диете. Рассчитываемая диета должна была включать 77 видов пищи. Формулировка задачи в терминах линейного программирования включала 9 уравнений с 86 неизвестными, из которых 9 были дополнительными. Оптимальное решение, конечно, удовлетворяло всем требованиям задачи. Однако, поскольку симплекс-методдаеттолько базисное решение, оптимальная диета включала лишь 9 различных видов пищи (пшеничную муку, кукурузу, сгущенное молоко, растительное масло, сало, говяжью печень, капусту, картофель и шпинат). Ясно, что подобная диета не вполне отвечала бы требованиям вкуса и разнообразия пищи.

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