Пример решения задачи ЛП симплекс методом

 

Пусть имеется некоторый материал в виде стандартных листов, которые надо раскроить таким образом, что бы получить не менее 80 деталей первого типа и не менее 40 второго. Известно 4 способа раскроя листа, для которых результаты раскроя представлены в таблице:

 

Cn
P	3(1)	2(1)	1(1)	0(1)
1(2)	6(2)	9(2)	13(2)

 

Требуется получить необходимое число деталей при минимальном расходе листов материала. Обозначим через x_j количество листов раскраиваемых j-ым столбцом. Целевая функция в данном случае:

 

Z = x₁ + x₂+ x₃ + x₄

 

При этом должны выполняться следующие условия:

3 x₁ + 2 x₂ + x₃ ≥ 80

x₁ + 6x₂ + 2x₃ + 13 x₄ ≥ 40

 

" x_j ≥ 0, j=1,n

 

Для применения СМ, прежде всего, задачу требуется привести к стандартному виду.

3 x₁ + 2 x₂ + x₃ - x₅ = 80

(4)

x₁+ 6x₂ + 9x₃ + 13x₄ – x₆ = 40

 

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

 

- x₅ = 80

- x₆ =40

x₁ =…= x₄ =0

 

недопустимо ввиду не отрицательности переменной. Так как данное решение не допустимо, задачу необходимо решать в 2 этапа.

 

1 этап:

 

Решение вспомогательной задачи: приведем исходную задачу к К В:

 

3 x₁ + 2 x₂ + x₃ - x₅ + x₇ = 80

x₁+ 6x₂ + 9x₃ + 13x₄ – x₆ + x₈= 40

 

Для этого введем дополнительные переменные x₇ , x₈ . соответственно формулируем и решаем данную задачу с целевой функцией, которая должна быть минимизирована, помня, что ее решение будет и решением основной, при условии W=0.

Здесь легко отыскиваются исходные значения:

 

x₇ = 80, x₈ = 40, x₁ =…= x₆ = 0, W = 120

 

Применим С А и прежде всего проверим полученное решение на оптимальность.

Рассмотрим целевую функцию W = x₇ + x₈ , в которой переменные x_7, x₈ выразим через остальные W = x₇ + x₈ = 80 - 3 x₁ - 2 x₂ - x₃ + x₅ + 40 - x₁- 6x₂ - 9x₃ - 13x₄ + x₆ = 120 - 4 x₁ - 8 x₂ - 10 x₃ -13 x₄+ x₅ + x₆

Присутствие отрицательных коэффициентов указывает на не оптимальность полученного решения, так как максимальное по модулю отрицательное значение коэффициента имеет переменная x₄ , что в соответствии с рассмотренным ранее критерием именно ей будем давать положительное приращение (x₃ = x₄).

Теперь рассмотрим, до какой величины можно увеличить x₄ , и какая при этом переменная обнулится.

x₇ = 80

x₈ = 40 -13 x₄

 

Вводя положительную переменную x₄ из исходной системы, для нашего решения имеем: таким образом видим, что x₄ можно увеличить до значения 40/13, при этом x₈ обратится в 0 и получим новое решение:

 

x₁ = x₂ = x₃ = 0, x₄ = 40/13, x₅ = x₆ = 0, x₇ = 80, x₈ = 0, W = 80+40/13

 

Проверим полученное решение на оптимальность, для этого выразим целевую функцию. Так как x₈ = 0 выражаем только x₇ .

 

W = x₇ + x₈ = -3 x₁ - 2 x₂ - x₃ + x₅ - x₈

 

Видим, что решение не оптимально, и так как максимально отрицательный коэффициент имеет переменная x₁ , то именно ей надо дать положительное приращение. Определим, до какого значения можно увеличить x₁ , и какая при этом переменная обратится в 0 (x₄ и x₇ – не нулевое значение).

x₇ = 80 - 3 x₁

x₄ = (40 – x₁)/13

 

x₁ может расти до 80/3 при этом первой обращается в 0 x₇ . получаем:

 

x₁ = 80/3

x₄ = 40/39

x₂ = x₃ = x₅ = x₆ = x₇ = x₈ = 0 (оптимальное решение)

W = x₇ = x₈ = 0

 

Так как целевая функция не содержит отрицательных коэффициентов и ее минимум есть 0, то найденное оптимальное решение может рассматриваться как исходное решение для выполнения 2 этапа.

2 этап:

3 x₁ + 2 x₂ + x₃ - x₅ = 80

x₁+ 6x₂ + 9x₃ + 13x₄ – x₆ = 40

 

исходное решение:

x₁ = 80/3

x₄ = 40/39

x₂ = x₃ = x₅ = x₆ = x₇ = x₈ = 0

W = x₇ = x₈ = 0

 

Имея допустимое базисное решение, полученное на первом этапе решения, начинаем решение основной задачи.

2 этап:

 

Прежде всего, проверим оптимальность полученного решения, для этого выразим x₁ и x_4. Получаем из (4):

 

x₁ = (80 - 2x₂ - x₃ + x₅) / 3

x₄ = (40 - x₁- 6x₂ - 9x₃ + x₆) / 13

 

Целевая функция: Z= x₁+ x₂+ x₃+x₄ = (1080 - 3 x₂ + 12x₁ + 3 x₆) / 39

Вывод:

· Полученное решение не оптимально.

· Следует дать приращение переменной x₂ . Для определения того, на сколько увеличивать x_2, выразим наши нулевые переменные x₁ и x₄ через x₂ получим:

 

x₁=(80-2 x₂)/3

x₄=(40-16 x₂)/39

 

x₁ выражаем через x₂. Отсюда получаем, что x₂ может увеличиваться до 2,5, при этом x₄ превращается в 0.

 

x₁ = 25, x₂ =2,5, x₃ = x₆ =0 целевая функция: Z=27,5

 

Проверим данное решение на оптимальность, для этого выразим целевую функцию через переменные: Z= x₁ + x₂ + x₃ +x₄ = (440+2x₃+3x₄+x₅+5x₆ )/16

 

Вывод:

Данное решение задачи является оптимальным и единственным. Таким образом, оптимальный способ раскроя листов (см задачу) состоит в следующем: 25 кроить 1-ым способом, 2,5 – вторым, в результате потребуется 27,5 листов.

 

Недостатки С М (метода решения, основанного на геометрической интерпретации задачи ЛП):

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

· Сложность использования вычислительных средств для решения задачи. Алгоритмы, ориентированные на применение вычислительных средств, должны характеризоваться по возможности простейшими операциями (+,- и т.д.). Здесь же при обработке каждого решения, необходимо решать достаточно сложные системы уравнения, что сложно формируется на ЭВМ. Таким образом, можем сделать вывод, что для решения задач большой размерности, где необходимо применение ЭВМ, необходимы иные подходы, следовательно, другая интерпретация задачи и критерий оптимальности.

· Особенно сложен С М для решения целочисленных задач.