Раздел 2. Решение прямой задачи линейного программирования симплекс-методом

При изучении данного раздела Вам предстоит:

1. Изучить четыре темы:

1. Алгоритм симплекс-метода;

2. Анализ симплекс-таблиц;

3. Интервалы устойчивости. Ценность ресурсов;

2. Ответить на вопросы рубежного теста к разделу 2.

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

2.1. Теоремы двойственности. Алгоритм симплекс-метода

Изучаемые вопросы:

• Теорема равновесия и следствия из нее;

• Критерий оптимальности и свойства оптимального плана;

• Общая схема симплекс-метода;

• Решение примера;

• Алгоритм симплекс-метода на примере задачи распределения ресурсов.

• Анализ оптимальной симплекс-таблицы

В линейном программировании доказываются две теоремы двойственности.

Теорема 1 (основная теорема двойственности).Пустьx_j,j = 1, 2,…,nобозначает допустимый план прямой задачи, аy_i,i = 1, 2,…,m– допустимый план двойственной задачи. Тогда выполняется неравенство:

, (2.1.1)

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

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

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

(2.1.2)

Следствия:

1. Если для некоторого ограничения прямой задачи в стандартной форме выполняется строгое неравенство

(2.1.3)

то значение двойственной переменной, соответствующей этому ограничению y_i = 0, т.е. теневая цена недефицитного ресурса равна 0.

2. Если оптимальное значение базисной переменной x _j> 0, то

, (2.1.4)

т.е. производство данной продукции рентабельно.

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

Критерий оптимальности. Если существуют такие допустимые решенияXиYпрямой и двойственной задач, для которых выполняется равенство целевых функцийZ =W, то эти решенияXиYявляются оптимальными решениями прямой и двойственной задач соответственно.

Заметим, что критерию оптимальности удовлетворяет базисное решение прямой задачи в примере 1.3.1, п.2.

x₁= 100,x₂= 50,s₁=0,s₂=0 и соответствующее ему решение двойственной задачиy₁=4,y₂= 200 является допустимым.

Из теорем двойственности следует, что оптимальные решения прямой и двойственной задач распределения ресурсов должны удовлетворять следующим свойствам:

1. все производства, входящие в оптимальный план прямой задачи должны быть рентабельными, т.е. для всех базисных переменных x_j приведенные стоимости Δ_j = 0;

2. все производства, не входящие в оптимальный план, должны быть неприбыльными; т.е. для всех небазисных переменных x_j приведенные стоимости Δ_j ≥ 0;

Иначе говоря, допустимый базисный план прямой задачи X– неоп-тимальный, если хотя бы для одной небазисной переменнойx_jвеличина Δ_j < 0, т.е. хотя бы одно небазисное производство прибыльно.

3. максимальное значение выручки в прямой задаче Z будет равно минимальной стоимости всех ресурсов в теневых ценах W, т.е. max Z = min W.

Симплекс-методсостоит в построении последовательности базисных решений прямой задачи, которая приводит к оптимальному базисному решению. Выбирают некоторым способом начальный базисный план прямой задачи и находят теневые цены, ему соответствующие. Если в этих ценах все производства – неприбыльные, т.е. теневые цены являются допустимыми, то начальный базисный план прямой задачи является оптимальным планом. Если же в этих ценах хотя бы одно небазисное производство прибыльно, то переменная одного прибыльного производства вводится в базисный план и для нового базисного плана повторяется все, что и для начального базисного плана прямой задачи. Так продолжается до тех пор, пока не будут найдены такие теневые цены, при которых все производства будут неприбыльными. Алгоритм симплекс-метода покажем на примере.