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

↑

▷ Содержание

⇐ ПредыдущаяСтр 7 из 15Следующая ⇒

Доказано, что оптимальное решение задачи линейного программи­рования связано с угловыми точками многогранника решений, поэтому возникает мысль о следующем пути решения задачи линейного програм­мирования с любым числом переменных. Найти каким-нибудь способом все угловые точки многогранника планов (а их = , если каждый план определяется системой m-линейно независимых векторов, содержащихся в данной системе из n векторов Ā₁, Ā₂ ,..., Ā_n) и сравнить в них значения целевой функции. Но найти оптимальный план, перебирая все опорные планы задачи трудно, поэтому необходимо иметь схему, по­зволяющую переходить к не худшему опорному плану и иметь признак того, что лучших крайних точек, чем данная крайняя точка нет. В этом и состоит идея наиболее широко применяемого в настоящее время сим­плексного метода (метода последовательного улучшения плана).

Итак, симплексный метод предполагает: умение находить начальный опорный план, наличие признака оптимальности (неоптимальности) опорного плана, умение переходить к нехудшему опорному плану.

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

1. Пусть задача линейного программирования представлена целевой функцией Z=c₁х₁ +с₂х₂ +...+с_nх_n = с_jх_j и системой ограничений, заданной в каноническом виде

Говорят, что ограничение задачи линейного программирования имеет предпочтительный вид, если в _i ³ 0 и левая часть этого ограничения содержит переменную с коэффициентом 1, а в остальные ограничения – равенства она входит с коэффициентом равным 0.

Пример 7.

Первое и второе ограничения имеют предпочтительный вид, а третье – нет.

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

Пример 8.

а) предпочтительными, т. е. базисными переменными являются х₂, х₃, х₄, а свободными – х₁ и х₅ х₁ = 0, х₅ = 0, а х₂ = 10, х₃ = 0, х₄ = 2. Тогда начальный опорный план =(0; 10; 80; 32; 0) – угловая точка (согласно теореме 1).

б) пусть система ограничений имеет вид  в _i; в _i ³ 0    (i = ) в задаче линейного программирования на max (задача об использовании сырья). Сведем задачу к каноническому виду, для этого добавим к левым частям неравенств дополнительные переменные х_{n + i} ³ 0 (i = ), тогда получим систему равенств  в _i; в _i ³ 0 (i = ), которая будет иметь предпочтительный вид и, следовательно, начальный опорный план будет = (0,...0, в₁, в₂,…, в_m) (так как в этой системе все дополнительные переменные будут базисными, а в целевую функцию дополнительные переменные входят с коэффициентом равным 0), то Z = c₁x₁ + c₂x₂ + … c_nx_n + 0×x_n+1 + …0×x_n+m.

в) в задачах линейного программирования на min (задача о составлении ра­циона) система ограничений имеет вид  в _i; в _i ³ 0, (i = ). Если мы сведем эту задачу к каноническому виду, то надо из каждого неравенства (из левой части) вычесть дополнительные переменные х_{n+ i} ³ 0 (i = ). Получим систему  в _i; в _i ³ 0, (i = ), однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные х_{n + i} входят в левую часть с коэффициентами (– 1). В этом случае вводится так называемый искусственный базис: к левым частям ограничений равенств, не имеющих предпочтительного вида, добавляют искусственные переменные w _i.

В целевую функцию переменные w _i вводят с коэффициентом М в случае решения задачи на min и с коэффициентом (– M) для задачи на max, где М – большое положительное число. Полученная задача называ­ется М-задачей, которая соответствует исходной. Она всегда имеет пред­почтительный вид.

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

max(min) Z = ,  

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

                            max (min) = – (+) ,

                   в _i,(i = ),

                     х_j ³ 0, (j = ), w _i ³ 0, (i = ).

Эта система ограничений имеет предпочтительный вид, ее начальный опорный план  = (0,...0, в₁, в₂, …, в_m). Если некоторые из уравнений исходной системы ограничений имеют предпочтительный вид, то в них не следует вводить искусственные переменные. Итак, если в оптимальном плане  = (х₁, x₂,.., x_n, w₁, w₂,.., w_m) М-задачи все искусственные переменные w_I = 0 (i = ), то план = (х₁, x₂,.., х_n) является оптимальным планом исходной задачи. Можно сказать, что если в результате применения симплексного метода к М-задаче получен оптимальный план, в котором все искусственные переменные w_I = 0, то его первые n-компоненты дают оптимальный план исходной задачи. Если же в оптимальном плане М-задачи хотя бы одна из w_i ¹ 0, то исходная задача не имеет допустимых планов, т. е. ее условия не совместны.

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

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

Итак, любую задачу линейного программирования можно предста­вить в предпочтительном виде: max(min) Z = ,

                       x_i + , B_i ³ 0, (i = ),

                      х_j ³ 0, (j = ).

Рассмотрим эту задачу для n = 4, m = 2 (и распространим ее для общего случая): Z = c₁x₁ + c₂x₂ + c₃x₃ + c₄x₄.

Выразим базисные переменные (БП) х₁, х₂ через свободные х₃ и х₄

  x₁ = ,

  x₂ =     и подставим их в целевую функцию

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

,

где = (с₁; с₂; …; с_m) – вектор коэффициентов целевой функции при базисных переменных,  = (B₁; B₂;..; B_m) – вектор свободных членов; =  – вектор коэффициентов при переменных х _j.

С учетом этих равенств целевая функция примет вид:

max(min)Z=  где ; .

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

Таблица 17

БП	СБ	В	х1   х2 … xi … xm xm+1   …    xj … xn
			c1   c2 … ci … cm  cm+1   …    cj … cn
x1 x2 . . . xm	c1 c2 . . . cm	B1 B2 . . . Bm	1     0   …   0 … 0 1, m+1   … 1, j … 1n 0     1  …   0 … 0 2, m+1   … 2, j … 2,n ……………………………………………………………..   0     0 … 0 …  1 m, m+1  … m, j … mn
Z j – c j		ΔO	0 …  0 … 0 … 0  Δm+1          Δ j            Δn

Последнюю строку называют индексной строкой, число  – значение целевой функции для начального опорного плана , т. е. Δ_O = Z() = , числа  – называются оценками свободных переменных.

Теорема.

Пусть исходная задача решается на max. Если для некоторого опорного плана все оценки Δ_j (j = ) не отрицательны (больше или равны 0), то такой план оптимален.

Доказательство: Так как Z = Δ_O и Δ_j ³ 0, то Z достигает max, когда = 0, а это возможно, если х_m+1 = 0, х_m+2 = 0,..., хn = 0, т. е. опорный план (В₁, В₂, …, В_m, 0, …, 0) – оптимален.

Теорема.

Если исходная задача решается на min и для некоторого опорного плана все оценки Δ_j (j = ) не положительны (меньше или равны 0), то такой план оптимален.

Пример 9. Решить задачу линейного программирования.

=>

Система ограничений задачи имеет предпочтительный вид: базисом являются переменные х₂,х₄,х₁. Заносим условие задачи в симплексную таблицу (табл. 18):

Таблица 18

Заполним индексную строку (Z _j – с _j): ,

Δ_O = – 1 × 1,5 – 2 × 2 + 2 × 0,5 = – 4,5,

Δ₁ = – 1× 0 – 2 × 0 + 2 × 1 – 2 = 0,

Δ₂ = – 1× 1 – 2×0 + 2×0 – (–1) = 0,

Δ₃ = – 1× 0,5 – 2 + 2 × (– 0,5) – 3= – 6,5,

Δ₄ = – 1× 0 – 2×1 + 2×0 – (– 2) = 0,

Δ₅ = – 1× 0,5 – 2 × 0 + 2 × 0,5 – 1 = – 0,5.

Начальный опорный план  = (0,5; 1,5; 0;2; 0), Z () = – 4,5. Так как все оценки индексной строки Δ _j не положительны, а задача на min, то план  – оптимален х* = (0.5: 1.5: 0: 2: 0); Z (х*) = – 4,5.

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

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

 (i = ),                    (5)

ее начальный опорный план  = (В₁, В₂, …, В_m, 0, …, 0). Значение целевой функции Z() =  = Δ_O.

Рассмотрим задачу на mах: если все Δ _j ³ 0, то опорный план опти­мален. Пусть существует j_O, для которого Δj_O < 0. Вектор столбец , для которого Δj_O < 0, называется разрешающим, а соответствующая пе­ременная x_jo – перспективной. Попытаемся, не изменяя нулевых значений свободных переменных х_m+1, х_m+2, …, х_n, кроме x_jo увеличить значение целевой функции Z за счет увеличения переменной x_jo > 0. Однако увеличивать x_jo надо осторожно, так как выбор  влияет на значения х₁,..., х_m, которые должны быть ³ 0. Имеем: х₁ ³ 0, х₂ ³ 0,..., х_m ³ 0, х_m+1 = 0,..., x_jo-1 = 0, x_jo > 0, x_jo+1 = 0,..., x_n = 0 и из (5) имеем

 x _i = B _I –   – (i = ).                                (6)

При значительном увеличении  может случиться, что для некоторого i соответствующее B _I < , значит получим х_i < 0, что недопустимо. В случае, если  (i = ), такого нарушения не произойдет.

Итак, x_jo можно увеличивать до тех пор, пока B _i – x_jo ³ 0, не на­рушая общности, можно считать > 0, тогда  £ . Найдем среди отношений  наименьшее. Пусть оно называется наименьшим симплексным отношением и обозначается Q.

x_jo = min  =  = Q,

(если это условие выполняется при нескольких i, то в качестве i _O можно выбрать любое) Cтроку  называют разрешающей, элемент  – разрешающим. Переменная , присутствующая в базисе, является неперспективной и ее выводят из базиса:

x_m+1 = 0, …, = 0, = Q,

 = 0, …, x_n = 0, а из равенства (6) находим: x₁ = B₁ – Q, …,

= – Q,  = 0, = – Q, …,

x_m = Q.

Новый базис будет состоять из переменных х₁, , , ,..., x_m, а соответствующий ему опорный план примет вид, X₁ = (B₁ – Q; B₂ – Q; …; – Q; 0; – Q; …; Q; 0; …; Q; 0; …; 0).

В результате преобразований получен новый опорный план , в котором переменная  заменена на , причем Z(X₁) = Δ₀ – Δ_j0Q = Z(X₀) – Δ_j0Q, но Δ_j0 < 0, поэтому Z(X₁) ³ Z(X₀), то есть новый план  не хуже начального .

Практика показывает, что в случае решения задачи на max число шагов уменьшается, если разрешающий столбец выбрать по правилу max (Δ_j £ 0), т. е. в базис вводить переменную, которой соответствует max по абсолютной величине оценки.

В случае задачи на min разрешающий столбец нужно выбирать по правилу mах Δ_j (Δ_j > 0).

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

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

Симплексные преобразования нового базиса выполняются по правилу:

1. Элементы строки i _O новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разре­шающий элемент: , , (j = ).

2. Элементы разрешающего столбца j₀ новой таблицы равны 0, за исключением = 1.

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

4. По 3 пункту вычисляются и элементы индексной строки.

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

Пример 10. Найти max Z = 14х₁ – 5х₂ + 2х₃ – х₄ + 8х₅, если

Решение.

Так как задача имеет предпочтительный вид, то занесем ее условия в симплексную табл. 19 (итерация 0).

Таблица 19

0 итерация: исходная задача на max, поэтому начальный опорный план . Он неоптимальный, так как Δ₁ < 0, Δ₅ < 0.

1 итерация:

1) выбираем разрешающий элемент из условия: max {|Δ₁|, |Δ₅|} = m a x (4; 1) = 4 – это соответствует 1 столбцу, поэтому его выбираем за разрешающий то есть X₁ будем вводить в базис. Для определения разрешающей строки находим минимальное симплексное отношение:

= =

итак, 1 – строка разрешающая =>элемент а₁₁ = 1 – разрешающий;

2) переменную х₂ выведем из базиса, а х₁ введем в базис;

3) разрешающую строку делим на разрешающий элемент;

4) элементы разрешающего столбца заполняем нулями;

5) остальные элементы пересчитываем по правилу прямоугольника и делим на разрешающий элемент.

Делаем контрольные проверки:

14 – 5 + 2×16 – 1× 40 = 62; 14 – 10 – 5 + 5 = 4;

14 + 0 + 0 – 14 = 0;      0 + 2 + 0 – 2 = 0;

0 + 0 – 1 + 1 = 0;      – 14 + 16 + 1 – 8 = – 5 < 0.

Так как существует отрицательная оценка ∆₅ = – 5, план  = (5; 0; 16; 40; 0) не оптимальный, Z(x₁) = 62 > Z () = 42.

2 итерация:

1) разрешающий столбец 5, переменную. х₅,будем вводить в базис.

2) определяем разрешающую строку: min симплексное отношение  =  = 2 соответствует 2-ой строке, значит переменную х₃ выводим из базиса. Разрешающий элемент а₂₅ = 8;

3) разрешающую строку делим на 8;

4) в разрешающем столбце проставляем нули;

5) остальные элементы пересчитываем;

6) делаем контрольные проверки, так же как и в итерации 1, так как все D_j ³ 0, опорный план  – оптимален

Ответ:  = (7; 0; 0; 42; 2), Z() = 72.

Пример 11. Решить М-задачу линейного программирования:

Найти: min Z = 3x₁ + 2х₂ + 3х₃, если

Решение:

Сведем задачу к каноническому виду и введем искусственные переменные  и :

Занесем условие М-задачи в симплексную таблицу (индексную строку записываем в две строки: в первой – слагаемые без М, во второй – слагаемые с М) (табл. 20).

Таблица 20

№		БП	СБ		В	х1	х2	х3	х4	х5	х6	w1	w2	Q
						3	2	3	0	0	0	M	M
0		х4 w1 w2	0 М М		2 8 1	2 3 0	1 [8] 0	1 2 1	1 0 0	0 – 1 0	0 0 – 1	0 1 0	0 0 1	2/1 = 2 8/8 = [1]
					0	– 3	– 2	– 3	0	0	0	0	0
					9M	3M	[8M]	3M	0	– M	– M	0	0
1	х4 х2 w2			0 2 М	1 1 1	13/8 3/8 0	0 1 0	3/4 1/4 [1]	1 0 0	1/8 – 1/8 0	0 0 – 1	– – –	0 0 1	1/ 1/ 1/1=[1]
					2	– 9/4	0	– 7/2	0	– 1/4	0	–	0
					М	0	0	[M]	0	0	-М	–	0

Окончание табл. 20

Примечание: по мере вывода из базиса искусственных переменных соответствующие им столбцы можно опускать.

Так как все D_j ≤ 0, то план оптимален,

Ответ:  = (0; 3/4; 1; 1/4; 0; 0), Z() = 9/2.

Замечания:

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

2. Если в индексной строке симплексной таблицы задачи линейного программирования на max содержится отрицательная оценка D_j < 0, а в соответствующем столбце переменной х_j. нет ни одного положительного элемента, то целевая функция на множестве допустимых планов задачи не ограничена сверху.

Если же задача линейного программирования на min и в индексной строке содержится положительная оценка D_j > 0, а в столбце переменной х_j нет ни одного положительного элемента, то на множестве допустимых планов целевая функция не ограничена снизу.

С экономической точки зрения неограниченность целевой функции задачи линейного програм­мирования говорит только об одном; разработанная модель недоста­точно точна (бессмысленно говорить о бесконечной прибыли). Типичными ошибками, приводящими к построению моделей такого рода, являются:

а) неполный учет ограничений, которые являются существенными в данной задаче;

б) небрежные оценки параметров, которые участвуют в ограничениях.

Задания для самостоятельной работы

Задание 1. Для изготовления двух видов продукции P₁ и P₂ используют три вида сырья (S₁, S₂, S₃).

На изготовление единицы продукции P₁ используют сырье      S₁ – a₁ (ед.), S₂ – a₂ (ед.), S₃ - a₃ (ед.). На изготовление единицы продукции P₂ используют сырье S₁ – b₁ (ед.), S₂ – b₂ (ед.), S₃ – b₃ (ед.). Запасы сырья S₁ составляют не более чем k₁, сырья S₂ – не более чем k₂, сырья S₃ – не более чем k₃.

Прибыль от единицы продукции P₁ составляет a руб., от P₂ составляет b руб.

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

Данные для выполнения задания соответствующего варианта представлены в табл. 21.

Таблица 21

Окончание табл. 21

Заданеи 2. Задана каноническая модель задачи линейного программирования.

Z = CX, AX = A₀, X ³ 0, A = (a_ij)_{3 х 5}.

Требуется найти max Z М- методом.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

  12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.  

23.

24.

25.

26.

27.

28.  

29.

30.  

Познавательные статьи:



Алгоритмические операторы Matlab

Конструирование и порядок расчёта дорожной одежды

Исследования учёных: почему помогают молитвы?

Почему терпят неудачу многие предприниматели?