Стандартная форма записи задачи линейного программирования

Общий вид задачи линейного программирования.

Найти значения переменных x₁, x₂, x₃, ... , x_n, при которых максимума или минимума max (min) достигает целевая функция.

z = c₁x₁ + c₂x₂ + ... + c_nx_n

Если для переменных x1, x2, ... , xn выполняются ограничения

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

Матричная форма записи задачи линейного программирования получится, если мы введем такие матрицы:

пример.

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

Нужно определить оптимальные объемы производства изделия каждого вида.

Решение

Пусть изделий 1^го вида изготавливается x₁ штук, а 2^го вида – x₂ штук.

Прибыль: max z = 2x₁ + 3x₂.

Ограничения:

Итак, max z = 2x₁ + 3x₂;

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

max (min) z = c₁x₁ + c₂x₂;

Чтобы решить графически нужно выполнить следующее:

1) построить многоугольник допустимых решений

2) если при некоторых значениях x₁, x₂ целевая функция z = a, то прямая c₁x₁ + c₂x₂ = a будет перпендикулярна нормаль вектору

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

Продолжаем рассматривать начатый выше пример.

max z = 2x₁ + 3x₂;

Решение

(1)

пробная точка O (0, 0): выполняется.

O (0, 0) лежит в полуплоскости

(2)

O (0, 0): выполняется.

(3)

O (0, 0): выполняется.

z = 2x₁ + 3x₂;

Двигаем до точки А.

А – опорное решение

Найдем координаты точки А.

Прибыль:

Симплекс-метод

Очевидно, что оптимальное решение достигается в вершине многоугольника допустимых решений. При решении задачи линейного программирования симплекс-методом осуществляется последовательный переход от некоторой произвольно выбранной начальной вершины (обычно начало координат) к смежным вершинам до той поры, пока не будет найдено оптимальное решение. Симплекс-метод применяется только в стандартной форме записи задачи линейного программирования.

Стандартная форма записи задачи линейного программирования

1) Если в ограничении есть знак ≤, то мы прибавляем к левой части остаточную переменную

x₁ – 2x₂ ≤ 5; x₁ – 2x₂ + s₁ = 5; s₁ – остаточная переменная s₁ ≥ 0;

2x₁ + 3x₂ ≥ 10; 2x₁ + 3x₂ – s₂ = 10; s₂ – избыточная переменная s₂ ≥ 0.

2) max z = (– a) Û min (– z) = a.

Решение, полученное занулением n – m переменных называется базисным. Переменные не равные нулю называются базисными переменными, а равные нулю – небазисными.

шаг 0 начальное решение (x_i = 0).

z – строка оценок;

“С” ´ столб – (оценка в верхней строчке);

X_опт = 0·120 + 0·300 + 0·600 – 0 = 0;

x₁: 0·2 + 0·3 + 0·8 – 2 = – 2 и т.д.

шаг 1

Если в строке нет отрицательных, то оптимальное решение получено. Столбец, в котором стоит наибольшая по модулю отрицательная оценка является разрешающим. Переменная этого столбца вводится в базис. x₂ – разрешающая; x₂ вводится в базис.

шаг 2

Находим отношение элементов столбца X_опт к положительным элементам разрешающего столбца. Строка, в которой отношение наименьшее является разрешающей, соответствующая переменная выводится из базиса.

s₂ выводится из базиса, разрешающая.

На пересечении разрешающей строки и разрешающего столбца стоит главный элемент.

шаг 3

Пересчитываем коэффициенты таблицы с помощью преобразований Гаусса.

базис	С	Xопт						r
x1	x2	s1	s2	s3
s1
x2
s3
z
s1
x2
x1
z
s2
x2
x1
z

Особые случаи применения симплекс-метода

1. Вырождение решение

Одна из базисных переменных на некотором этапе равна 0. Графически это означает избыточное ограничение.

пример. max z = 3x₁ + 9x₂.

Б	С	Xопт					r
x1	x2	s1	s2
s1							2;
s2							2;
z			– 3	– 9
s1			– 1			– 2
x2
z

x₂ = 2; s₁ = 0; x₁ = s₂ = 0; z = 18.

2. Альтернативное решение

пример. max z = 2x₁ + 4x₂.

АВ – множество решений

Б	С	Xопт					r
x1	x2	s1	s2
s1
s2
z			– 2	– 4
x2
s2
z
x2						– 1
x1					– 1
z

Используем формулу: x = a·α + b·(1 – α); α Î [0; 1]

3. Неограниченное решение

пример. max z = 2x₁ + x₂.

max z = ∞

Столбец x₂ не содержит положительных, значит сразу можно сделать вывод о неограниченности максимума.

max z = ∞