Навигация
3.1 Признаки оптимальности.
Теорема. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки 
неотрицательны, то такой план оптимален.
Теорема. Если исходная задача решается на минимум и для некоторого опорного плана все оценки неположительны, то такой план оптимален.
§4. Понятие двойственности.
Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья m видов в объемах
единиц 
. Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск n видов неосновной продукции. Обозначим через 
норму расхода сырья i-го вида на единицу j-й 
продукции, 
- цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величины задачи: 
— объемы выпуска j-й продукции, обеспечивающие предприятию максимум выручки.
Математическая модель задачи:
(1)
(2)
(3)
Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производства на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их 
.
Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:
1) общую стоимость отходов сырья покупающая организация стремится минимизировать;
2) предприятие согласно уступить отходы только по таким ценам, при которых оно получит за них выручку, не меньшую той, что могло бы получить, организовав собственное производство.
Эти требования формализуются в виде следующей ЗЛП.
Требование 1 покупающей организации – минимизация покупки: 
(4)
Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если 
, где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену.
Аналогичные рассуждения логично провести в отношении выпуска продукции каждого вида. Поэтому требование предприятия, реализующего отходы сырья, можно формализовать в виде сл. системы ограничений:
(5)
По смыслу задачи оценки не должны быть отрицательными:
(6)
Переменные 
называют двойственными оценками или объективно обусловленными оценками.
Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.
Между прямой и двойственной задачами можно установить следующую взаимосвязь:
1. Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.
2. Коэффициенты 
целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.
3. Свободные члены ограничений прямой задачи являются коэффициентами целевой функции двойственной.
4. Матрицы ограничений прямой и двойственной задач являются транспонированными друг к другу.
5. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа 
. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа 
.
Похожие работы
... во многих экономических задачах, приводит к линейной функции с линейными ограничениями, наложенными на неизвестные. 2. Области применения и ограничения использования линейного программирования для решения экономических задач Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление ...
... строки и каждого столбца таблицы (матрицы) определяют специальные числа, называемые потенциалами. С помощью этих потенциалов можно установить, нужно ли заполнять свободную клетку матрицы или ее нужно оставить незаполненной. Для решения задач методом потенциалов исходный план должен иметь количество заполненных клеток m + n – 1 (m - число строк, n - число столбцов). Если план не отвечает этим ...
... рулонов, при котором все поступающие специальные заявки будут выполнены при минимальных затратах бумаги. Графический метод решения задач линейного программирования 1. Область решений линейных неравенств. Пусть задано линейное неравенство с двумя переменными и (1) Если величины и рассматривать как координаты точки плоскости, то совокупность точек ...
... разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями. Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах ...
0 комментариев