Линейное программирование. Графический метод решения

Раздел математического программирования, в котором целевая функция и функции, входящие в систему ограничений, линейны относительно входящих в задачу неизвестных, называют линейным программированием (ЛП).

Общей задачей линейного программирования называют задачу

 

(1)

 

при следующих ограничениях:

 

;

(2)

 

;

(3)

 

;

(4)

 

;

(5)

 

,

(6)

 

где , , – заданные действительные числа.

Функцию (1) называют целевой, а условия (2)–(6) – ограничениями задачи.

Набор чисел , удовлетворяющих ограничениям задачи линейного программирования (ЗЛП), называется ее планом. План , при котором целевая функция достигает максимума (минимума), называется оптимальным.

Один из методов решения ЗЛП с двумя переменными – графический.

Алгоритм графического метода приведен в примере.

 

Пример 1. Решить графическим методом следующую задачу линейного программирования:

 

 

Решение

Задачу решаем в нижеуказанном порядке:

1. Строим область допустимых решений как общую часть полуплоскостей, соответствующих данным неравенствам.

Решением линейного неравенства с двумя неизвестными 9 x ₁ +
+ 4 x ₂ 18 является бесконечное множество пар значений этих неизвестных, удовлетворяющих данному неравенству. В системе координат x ₁ Ox ₂ неравенство определяет полуплоскость с граничной прямой 9 x ₁ + 4 x ₂ = 18. Чтобы найти эту полуплоскость, нужно сначала построить граничную прямую со следующими значениями:

 

x 1	x 2
	4,5

 

Затем необходимо взять какую-нибудь точку, не лежащую на данной прямой, например (0; 0). Если координаты этой точки удовлетворяют данному неравенству, то искомой будет полуплоскость, в которой находится взятая точка. В противном случае берется полуплоскость, которой взятая точка не принадлежит.

Итак, 9 × 0 + 4 × 0 < 18. Берем полуплоскость, в которой не лежит точка (0; 0) (рис. 1).

 

 

рис. 1

 

В системе координат х ₁ Ох ₂ неравенство –2 х ₁ + х ₂ £ 2 определяет полуплоскость с граничной прямой –2 х ₁ + х ₂ = 2.

Строим прямую со следующими значениями:

 

x 1	x 2
–1

 

При подстановке точки с координатами (0; 0) неравенство –2 × 0 + 0 £ 2 является верным.

Следовательно, берем полуплоскость с точкой (0; 0).

Неравенство x ₁ £ 4 определяет полуплоскость граничной прямой x ₁ = 4.

Чтобы определить искомую полуплоскость, возьмем точку (0; 0) и подставим ее координаты в неравенство 0 £ 4, которое является верным.

Следовательно, берем полуплоскость с точкой (0; 0).

Точки, удовлетворяющие ограничениям х ₁ ³ 0 и х ₂ ³ 0, находятся в координатной четверти I.

Для нахождения области допустимых решений полуплоскости, соответствующие данным неравенствам, строим в одной координатной плоскости.

Таким образом, областью допустимых решений будет многоугольник ABCD (рис. 2).

 

рис. 2

2. Строим вектор . Его координаты – коэффициенты целевой функции (2; –3). Так как вектор находим лишь для выяснения направления, то для большей наглядности можно построить вектор .

3. Строим прямую z = 0, т. е. 2 х ₁ – 3 х ₂ = 0, которая проходит перпендикулярно вектору , со следующими значениями:

 

х 1	х 2

 

Параллельным перемещением прямой z = 0 вдоль вектора находим точку D, в которой функция z достигает наибольшего значения, и точку C, в которой функция z достигает наименьшего значения.

4. Координаты точки D находим по графику D (4; 0).

Координаты точки С можно найти, решив систему уравнений

 

 

Итак, С (4; 10).

5. Находим z _max и z _min:

 

z _max = z (4; 0) = 2 × 4 – 3 × 0 = 8,

 

z _min = z (4; 10) = 2 × 4 – 3 × 10 = –22.

 

Ответ: z _max(4; 0) = 8; z _min(4; 10) = –22.

 

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

Так, на рис. 3 функция достигает минимума в точке A, а максимума – в любой точке отрезка DE; на рис. 4 максимум достигается в точке A, а минимума функция не имеет ; на рис. 5 функция не имеет ни максимума , ни минимума .

 

Рис. 3

 

 

Рис. 4

 

 

Рис. 5

Вопросы для самоконтроля

 

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

2. Определение невырожденного, вырожденного, опорного и оптимального планов.

3. Переход от задачи минимизации к задаче максимизации и наоборот.

4. Геометрическая интерпретация задачи линейного программирования.

5. Основные этапы графического метода решения задач линейного программирования в случае двух переменных.

6. Случаи, в которых выполняются следующие условия:

· оптимальный план единственный;

· оптимальных планов бесконечное множество;

· целевая функция не ограничена;

· задача не имеет решения;

· целевая функция достигает одновременно и максимального, и минимального значений.

Геометрическая интерпретация.

 

 

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

 

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

 

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

 

Рассмотрим три случая построения начального опорного плана.

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

Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательности правой части (b_i ³ 0) левая часть ограничения содержит переменную с коэффициентом, равным единице, а остальные ограничения – с коэффициентом, равным нулю.

Если каждоеограничение-равенство ЗЛП в каноническом виде содержит переменную, входящую в левую часть с коэффициентом, равным нулю (при неотрицательности правых частей), то говорят, что система ограничений представлена в предпочтительном виде. В этом случае начальный опорный план строится весьма просто (базисный с неотрицательными координатами). Предпочтительные переменные выбираются в качестве базисных, а все остальные – свободные. Свободные переменные приравниваются к нулю, а базисные переменные (БП) – к свободным членам.

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

.

Сведем задачу к каноническому виду. Для этого добавим к левым частям неравенств дополнительные переменные . Получим систему, эквивалентную исходной:

,

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

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

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

.

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

 

.

 

Теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные x_{n + i} входят в левую часть (при b_i ³ 0) с коэффициентами, равными –1. В этом случае вводится так называемый искусственный базис путем перехода к М-задаче. Ее рассмотрим в пункте 2.9.

 

Симплексные таблицы

 

Приведя модель ЗЛП к предпочтительному виду, ее заносят в так называемую симплексную таблицу (табл. 1).

Таблица 1

БП

сБ

А 0

x 1

…

xj

…

xn

xn +1

xn +2

…

xn + i

…

xn + m

c 1

…

cj

…

cn

cn +1

cn +2

…

cn + i

…

cn + m

xn +1

cn +1

bn +1

a 11

…

a 1 j

…

a 1 n

…

…

xn +2

cn +2

bn +2

a 21

…

a 2 j

…

a 2 n

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

xn + i

cn + i

bn + i

ai 1

…

aij

…

ain

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

xn + m

cn + m

bn + m

am 1

…

amj

…

amn

…

…

zj – cj

D0

D1

…

D j

…

D n

…

…

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

Применяются следующие обозначения:

· x ₁, …, x_j, …, x_n – свободные переменные;

· x_{n+ 1}, x_{n+ 2}, …, x_n+i, …, x_n+m – базисные (предпочтительные) переменные;

· c ₁, …, c_j, …, c_n – коэффициенты целевой функции при свободных переменных;

· с_Б = (c_{n+ 1}; c_{n+ 2}; …; c_n+i; …; c_n+m) – вектор коэффициентов целевой функции при базисных переменных;

· A ₀ = (b_{n+ 1}; b_{n+ 2}; …; b_n+i; …; b_n+m) ^Т – вектор-столбец свободных членов системы ограничений;

· A_j = (a _{1 j} ; a _{2 j} ; …; a_ij; …; a_mj) ^T – вектор-столбец коэффициентов при переменных х_j;

· D₀ = c_Б × А ₀ – значение целевой функции для начального опорного плана x ₀, т. е. D₀ = z (x ₀);

· D _j = c_Б × А_j – c_j – оценки свободных переменных;

· .

Последнюю строку (z_j – c_j) таблицы называют индексной строкой (строкой целевой функции или строкой оценок).

2.3. Признак оптимальности опорного плана

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

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

2.4. Переход к нехудшему опорному плану

Рассмотрим ЗЛП на максимум. Приведем ее к каноническому виду и занесем в симплексную таблицу.

Если все D _j ³ 0, то начальный опорный план x ₀ оптимален.

Если же существуют D _j < 0, то план неоптимален, при определенных условиях его можно улучшить.

С этой целью выбирают разрешающий элемент.

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

Вектор-столбец , для которого , называется разрешающим,а соответствующая переменная – перспективной.

Замечание. Если задача решается на минимум, то разрешающий столбец выбирается из условия .

Выбор разрешающей строки. Находят отношения . Они называются симплексными.

Среди симплексных отношений определяют наименьшее, т. е.

 

.

 

Если это условие выполняется при нескольких i, то в качестве i ₀ можно выбрать любое.

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

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

Переходим к новой таблице. Переменную соответствующую разрешающему столбцу, следует ввести в базис вместо переменной присутствующей в базисе, которая является неперспективной.

Замечание. Поскольку min z = –max (– z), задачу минимизации можно формально заменить задачей максимизации функции – z. Затем полученный максимум следует взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

2.5. Симплексные преобразования

Чтобы завершить шаг преобразований, ведущих к новому опорному плану, составляют таблицу по следующим правилам:

1. элементы строки i ₀ новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разрешающий элемент.

2. все элементы столбца j ₀ новой таблицы равны нулю, за исключением .

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

 

Рис. 6

 

Для этого в прежней таблице выделяют прямоугольник, вершинами которого служат нужные для вычисления элементы. Диагональ, содержащую разрешающий и искомый (a_ij) элементы новой таблицы, называют главной, а другую – побочной. Чтобы получить элемент новой симплексной таблицы, нужно из произведения угловых элементов главной диагонали вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент, выделенный рамкой:

 

.

 

Шаг симплексного метода, позволяющий перейти от одного опорного плана к другому, нехудшему, называется итерацией. Таким образом, симплексный метод является итеративным методом последовательного улучшения плана.

Контроль вычислений

 

Для контроля вычислений элементов индексной строки применяются формулы D₀ = c_Б × А ₀, D _j = с_б × А_j – c_j.

 

2.7. Альтернативный оптимум (признак бесконечности
множества оптимальных планов)

 

Теорема 3. Если в индексной строке последней симплексной таблицы, содержащей оптимальный план, имеется хотя бы одна нулевая оценка, соответствующая свободной переменной, то ЗЛП имеет бесконечное множество оптимальных планов.

Следствие. Если в индексной строке симплексной таблицы, содержащей оптимальный план, все оценки свободных переменных положительны, то найденный оптимальный план единственный.