Метод больших штрафов

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

Решим прямую задачу линейного программирования симплексным М-методом, с использованием симплексной таблицы. Определим максимальное значение целевой функции F(X) = 2x1+x2+3x3 при следующих условиях-ограничений (см. также M-задача).
x1+2x2+x3≤1000
3x1+5x2+2x3≤1500
x1≥100
x2≥100
x3≥200
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 = 200
Введем искусственные переменные x.
1x1 + 2x2 + 1x3 + 1x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1000
3x1 + 5x2 + 2x3 + 0x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 = 1500
1x1 + 0x2 + 0x3 + 0x4 + 0x5-1x6 + 0x7 + 0x8 + 1x9 + 0x10 + 0x11 = 100
0x1 + 1x2 + 0x3 + 0x4 + 0x5 + 0x6-1x7 + 0x8 + 0x9 + 1x10 + 0x11 = 100
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7-1x8 + 0x9 + 0x10 + 1x11 = 200
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = 2x1+x2+3x3 - Mx9 - Mx10 - Mx11 => max
За использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается.
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса.
Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения.
Из уравнений выражаем искусственные переменные:
 x9 = 100-x1+x6
 x10 = 100-x2+x7
 x11 = 200-x3+x8
которые подставим в целевую функцию:
F(X) = 2x1 + x2 + 3x3 - M(100-x1+x6) - M(100-x2+x7) - M(200-x3+x8) => max
или
F(X) = (2+1M)x1+(1+1M)x2+(3+1M)x3+(-1M)x6+(-1M)x7+(-1M)x8+(-400M) => max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:


1

2

1

1

0

0

0

0

0

0

0

3

5

2

0

1

0

0

0

0

0

0

1

0

0

0

0

-1

0

0

1

0

0

0

1

0

0

0

0

-1

0

0

1

0

0

0

1

0

0

0

0

-1

0

0

1

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x9, x10, x11,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,1000,1500,0,0,0,100,100,200)

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

0

x4

1000

1

2

1

1

0

0

0

0

0

0

0


x5

1500

3

5

2

0

1

0

0

0

0

0

0


x9

100

1

0

0

0

0

-1

0

0

1

0

0


x10

100

0

1

0

0

0

0

-1

0

0

1

0


x11

200

0

0

1

0

0

0

0

-1

0

0

1

Индексная строка

F(X0)

-400M

-2-1M

-1-1M

-3-1M

0

0

1M

1M

1M

0

0

0

Иногда такую таблицу представляют с дополнительной строкой для М.

ПланБазисВx1x2x3x4x5x6x7x8x9x10x11
0x4100012110000000
 x5150035201000000
 x910010000-100100
 x10100010000-10010
 x112000010000-1001
Индексная строкаF(X0)0-2-1-300000000
M -400-1-1-100111000

Переходим к основному алгоритму симплекс-метода.

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

min

1

x4

1000

1

2

1

1

0

0

0

0

0

0

0

1000


x5

1500

3

5

2

0

1

0

0

0

0

0

0

750


x9

100

1

0

0

0

0

-1

0

0

1

0

0

0


x10

100

0

1

0

0

0

0

-1

0

0

1

0

0


x11

200

0

0

1

0

0

0

0

-1

0

0

1

200

Индексная строка

F(X1)

-400M

-2-1M

-1-1M

-3-1M

0

0

1M

1M

1M

0

0

0

0

Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 5-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 1 войдет переменная x3
Строка, соответствующая переменной x3  в плане 1, получена в результате деления всех элементов строки x11 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3  плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3  и столбец x3 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

















































200 / 1 = 200

0 / 1 = 0

0 / 1 = 0

1 / 1 = 1

0 / 1 = 0

0 / 1 = 0

0 / 1 = 0

0 / 1 = 0

-1 / 1 = -1

0 / 1 = 0

0 / 1 = 0

1 / 1 = 1













План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

min

2

x4

800

1

2

0

1

0

0

0

1

0

0

-1

800


x5

1100

3

5

0

0

1

0

0

2

0

0

-2

366.67


x9

100

1

0

0

0

0

-1

0

0

1

0

0

100


x10

100

0

1

0

0

0

0

-1

0

0

1

0

0


x3

200

0

0

1

0

0

0

0

-1

0

0

1

0

Индексная строка

F(X2)

600-200M

-2-1M

-1-1M

0

0

0

1M

1M

-3

0

0

3+1M

0

Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 2 войдет переменная x1
Строка, соответствующая переменной x1  в плане 2, получена в результате деления всех элементов строки x9 плана 1 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1  и столбец x1 .
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

























100 / 1 = 100

1 / 1 = 1

0 / 1 = 0

0 / 1 = 0

0 / 1 = 0

0 / 1 = 0

-1 / 1 = -1

0 / 1 = 0

0 / 1 = 0

1 / 1 = 1

0 / 1 = 0

0 / 1 = 0





































План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

min

3

x4

700

0

2

0

1

0

1

0

1

-1

0

-1

350


x5

800

0

5

0

0

1

3

0

2

-3

0

-2

160


x1

100

1

0

0

0

0

-1

0

0

1

0

0

0


x10

100

0

1

0

0

0

0

-1

0

0

1

0

100


x3

200

0

0

1

0

0

0

0

-1

0

0

1

0

Индексная строка

F(X3)

800-100M

0

-1-1M

0

0

0

-2

1M

-3

2+1M

0

3+1M

0

Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 4-ая строка является ведущей
Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 3 войдет переменная x2
Строка, соответствующая переменной x2  в плане 3, получена в результате деления всех элементов строки x10 плана 2 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x2 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x2  и столбец x2 .
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

min

4

x4

500

0

0

0

1

0

1

2

1

-1

-2

-1

500


x5

300

0

0

0

0

1

3

5

2

-3

-5

-2

150


x1

100

1

0

0

0

0

-1

0

0

1

0

0

0


x2

100

0

1

0

0

0

0

-1

0

0

1

0

0


x3

200

0

0

1

0

0

0

0

-1

0

0

1

0

Индексная строка

F(X4)

900

0

0

0

0

0

-2

-1

-3

2+1M

1+1M

3+1M

0

Итерация №3.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x8, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления

и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 2 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x в план 4 войдет переменная x8
Строка, соответствующая переменной x8  в плане 4, получена в результате деления всех элементов строки x5 плана 3 на разрешающий элемент РЭ=2
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x8  плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x8  и столбец x8 .
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

B

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11













300 / 2 = 150

0 / 2 = 0

0 / 2 = 0

0 / 2 = 0

0 / 2 = 0

1 / 2 = 0.5

3 / 2 = 1.5

5 / 2 = 2.5

2 / 2 = 1

-3 / 2 = -1.5

-5 / 2 = -2.5

-2 / 2 = -1

















































Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:

План

Базис

В

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

5

x4

350

0

0

0

1

-0.5

-0.5

-0.5

0

0.5

0.5

0


x8

150

0

0

0

0

0.5

1.5

2.5

1

-1.5

-2.5

-1


x1

100

1

0

0

0

0

-1

0

0

1

0

0


x2

100

0

1

0

0

0

0

-1

0

0

1

0


x3

350

0

0

1

0

0.5

1.5

2.5

0

-1.5

-2.5

0

Индексная строка

F(X5)

1350

0

0

0

0

1.5

2.5

6.5

0

-2.5+1M

-6.5+1M

1M

Оптимальный план можно записать так:
x4 = 350
x8 = 150
x1 = 100
x2 = 100
x3 = 350
F(X) = 2*100 + 1*100 + 3*350 = 1350
загрузка...