Варианты решений

1. Оптимальный план один: линия уровня и ОДР имеют одну общую точку.

2. Оптимальных планов множество: линия уровня проходит через сторону ОДР.

3. Целевая функция не ограничена: линия уровня, сколько бы ее не перемещали, не может занять разрешенного положения.

4. ОДР состоит из одной точки, в которой целевая функция достигает max и min значений.

5. Задача не имеет решения: область допустимых решений – пустое множество, т.е. система ограничений несовместна.

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

Симплексный метод – метод последовательного улучшения плана.

В алгебраических терминах симплексный метод предполагает:

– умение находить начальный опорный план;

– наличие признака оптимальности опорного плана;

– умение переходить к не худшему опорному плану.

П остроение начального опорного плана.

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

Предпочтительный вид.

Система ограничений имеет предпочтительный вид, если при не отрицательности правой части левая часть ограничения содержит переменную, коэффициент которой равен единице, и эта же переменная входит в другие ограничения с коэффициентом, равным нулю.

Базисный план.

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

Е сли система ограничений имеет вид, как на рисунке слева, то нужно задачу привести к каноническому виду, т.е. добавить к левым частям дополнительные переменные: x_n+i  0 (i=1,m).

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

X₀ = (0₁, 0₂, …, 0_n, b₁, b₂, …, b_m).

Т.е. базисными переменными будут дополнительные переменные. В целевую функцию дополнительные переменные входят с коэффициентами, равными нулю.

П усть система ограничений имеет вид, как на рисунке слева.

С ведем ее к каноническому виду вычитанием дополнительных переменных x_n+i  0 (i=1,m) из левой части.

Э та система не предпочтительного вида, потому что дополнительные переменные входят в нее с коэффициентами, равными –1, и базисный план является недопустимым. В таких случаях вводится искусственный базис. К левым частям ограничений равенств, не имеющих предпочтительного вида, добавляют искусственные переменные u_i (i=1,n). В целевую функцию эти переменные входят с коэффициентами М. В случае решения задачи на максимум коэффициенты берутся с минусом, при решении задачи на минимум – коэффициенты берутся с плюсом. На самом деле число М – это большое положительное число. Полученная задача называется М-задачей, ее система ограничений имеет предпочтительный вид и соответствует исходной.

М-задача. Система ограничений этой задачи имеет предпочтительный вид, ее начальный опорный план будет иметь вид X₀ = (0₁, 0₂, …, 0_n, b₁, b₂, …, b_m).

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

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

В ыразим базисные переменные x₁, x₂, …, x_m через свободные переменные (x_m+1, x_m+2, …, x_n) и подставим их в целевую функцию. После группировки подобных членов получим

Введем обозначения

₀ = c₁₁ + c₂₂ + … + c_m_m = С_БА_0;

_j = c₁_1j + c₂_2j + … + c_m_mj = С_БА_j;

С_Б = (с₁, с₂, …, с_m) – вектор коэффициентов целевой функции при базисных переменных;

A₀ = (₁, ₂, …, _m)^T – вектор-столбец свободных членов;

A_j = (_1j, _2j, …, _mj)^T – вектор-столбец коэффициентов при переменных x_j.

П оследняя строка называется индексной строкой; число ₀ – это значение целевой функции для начального опорного плана Х₀; _j называется оценками свободных переменных.

Задачу запишем в виде симплекс-таблицы

Критерии оптимальности опорного плана.

Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки _j не отрицательны, то такой опорный план оптимален.

Если исходная задача решается на минимум и для некоторого опорного плана все оценки _j не положительны, то такой план оптимален.

П ример

min Z = 2x₁ – x₂ + 3x₃ – 2x₄ + x₅;

x₂ + 0.5x₃ + 0.5x₅ = 1.5;

x₃ + x₄ = 2;

x₁ – 0.5x₃ + 0.5x₅ = 0.5.

₀ = С_БА₀ = (-1)*1.5 + (-2)*2 + 2*0.5 = -4.5;

₁ = C_БА₁ – С₁ = 2 – 2 = 0;

₂ = С_БА₂ – С₂ = -1 – (-1) = 0;

₃ = C_БА₃ – С₃ = -0.5 – 2 – 1 – 3 = -6.5;

₄ = С_БА₄ – С₄ = -2 – (-2) = 0;

₅ = C_БА₅ – С₅ = -0,5 + 1 – 1 = -0,5.

Задача на минимум, оценки _j должны быть не положительными, следовательно,

план X₀ = (0.5, 1.5, 0, 2, 0); Z(X₀) = -4.5.

Понятие двойственности и построение двойственных задач для симметричных задач линейного программирования. Принцип двойственности.

Понятие двойственности.

Прямая задача ; ; x_j  0 (j=1,n).

Двойственная задача ; _; y_i  0 (i=1,m).

По мат. модели одной из этих задач можно легко построить модель двойственной к ней задачи.

Правила построения двойственной задачи:

1. Если прямая задача на максимум, то двойственная к ней будет на минимум и наоборот.

2. Коэффициенты c_j целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

3. Свободные члены b_i ограничений прямой задачи являются коэффициентами целевой функции двойственной задачи.

4. Матрица ограничений двойственной задачи – это транспонированная матрица прямой задачи.

5. Если прямая задача на максимум, то система ограничений – неравенства вида (). Двойственная задача же задача будет на минимум и ее система ограничений будет в виде ().

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

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