Анализ экономических задач симплексным методом

Страница 3

Пусть исходная ЗЛП имеет вид

(1)

(2)

(3)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

(4)

(5)

, , (6)

Задача (4)-(6) имеет предпочтительный план. Её начальный опорный план имеет вид

Если некоторые из уравнений (2) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

(7)

М-задачи (4)-(6) все искусственные переменные , то план является оптимальным планом исходной задачи (1)-(3).

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

Решение исходной задачи симплексным методом путем введения искусственных переменных называется сим­плексным методом с искусственным базисом.

Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в кото­ром все искусственные переменные , то его первые n компоненты дают оптимальный план исходной задачи.

Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.

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. Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа . Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа .

6. Число ограничений прямой задачи равно числу пере­менных двойственной, а число ограничений двойствен­ной — числу переменных прямой.

7. Все переменные в обеих задачах неотрицательны.

Теорема. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т.е.

(7) – основное неравенство теории двойственности.

Теорема. (критерий оптимальности Канторовича)

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