Математические методы

Симплекс-таблица Т(q), соответствует  допустимому базису КЗЛП β(q)), получаемому  на q-й итерации. Столбец N(β(q)) содержит номера базисных столбцов (в той  последовательности, в которой они  входят в базис), столбец b(β(q)) —компоненты  вектора ограничений относительно текущего базиса β(q), A(β(q)) — компоненты матрицы задачи относительно текущего базиса β(q). Наконец, в строке а0(β(q)) находятся текущие оценки столбцов, а ячейка b0(β(q)) содержит значение целевой  функции, достигаемое для текущего плана.

Безусловно, следует добавить, что табличная модификация симплекс-метода имеет важное практическое значение не столько как удобная форма  организации ручного счета, сколько  как основа для реализации данного  алгоритма в рамках программного обеспечения ЭВМ.

 

Глава 2. Практическая часть

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

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

Поскольку в правой части  присутствуют отрицательные значения, умножим соответствующие строки на (-1).

Определим максимальное значение целевой функции F(X) = 2x₁ + x₂ + 2x₃ + 4x₄ при следующих условиях-ограничений.

x₁ + 2x₂ - x₃ + 5x₄≥22

- 2x₁ + 2x₂ + 3x₃ - 6x₄≥12

2x₁ - 2x₃ - 7x₄≤6

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

1x₁ + 2x₂-1x₃ + 5x₄-1x₅ + 0x₆ + 0x₇ = 22

-2x₁ + 2x₂ + 3x₃-6x₄ + 0x₅-1x₆ + 0x₇ = 12

2x₁ + 0x₂-2x₃-7x₄ + 0x₅ + 0x₆ + 1x₇ = 6

Введем искусственные  переменные x: в 1-м равенстве вводим переменную x₈; в 2-м равенстве вводим переменную x₉;

1x₁ + 2x₂-1x₃ + 5x₄-1x₅ + 0x₆ + 0x₇ + 1x₈ + 0x₉ = 22

-2x₁ + 2x₂ + 3x₃-6x₄ + 0x₅-1x₆ + 0x₇ + 0x₈ + 1x₉ = 12

2x₁ + 0x₂-2x₃-7x₄ + 0x₅ + 0x₆ + 1x₇ + 0x₈ + 0x₉ = 6

Для постановки задачи на максимум целевую функцию запишем так:

F(X) = 2x₁+x₂+2x₃+4x₄ - Mx₈ - Mx₉ → max

Из уравнений выражаем искусственные переменные:

x₈ = 22-x₁-2x₂+x₃-5x₄+x₅

x₉ = 12+2x₁-2x₂-3x₃+6x₄+x₆

которые подставим в целевую  функцию:

F(X) = (2-M)x₁+(1+4M)x₂+(2+2M)x₃+(4-M)x₄+(-M)x₅+(-M)x₆+(-34M) → max

Таблица 1 - Матрица коэффициентов A = a(ij) этой системы уравнений

1	2	-1	5	-1	0	0	1	0
-2	2	3	-6	0	-1	0	0	1
2	0	-2	-7	0	0	1	0	0

 

Решим систему уравнений  относительно базисных переменных:

x₈, x₉, x₇,

Полагая, что свободные  переменные равны 0, получим первый опорный план:

X1 = (0,0,0,0,0,0,6,22,12)

Таблица 2 – Исходная симплекс- таблица

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x8	22	1	2	-1	5	-1	0	0	1	0
x9	12	-2	2	3	-6	0	-1	0	0	1
x7	6	2	0	-2	-7	0	0	1	0	0
F(X0)	-34M	-2+M	-1-4M	-2-2M	-4+M	M	M	0	0	0

 

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

Итерация №0.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

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

Следовательно, 2-ая строка является ведущей.

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

Таблица 3 - Исходная симплекс-таблица  с обозначенными ведущими строкой  и столбцом

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x8	22	1	2	-1	5	-1	0	0	1	0	11
x9	12	-2	2	3	-6	0	-1	0	0	1	6
x7	6	2	0	-2	-7	0	0	1	0	0	-
F(X1)	-34M	-2+M	-1-4M	-2-2M	-4+M	M	M	0	0	0	0

 

Получаем новую симплекс-таблицу:

Таблица 4 – Симплекс-таблица, полученная после вычислений

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x8	10	3	0	-4	11	-1	1	0	1	-1
x2	6	-1	1	11/2	-3	0	-1/2	0	0	1/2
x7	6	2	0	-2	-7	0	0	1	0	0
F(X1)	6-10M	-3-3M	0	-1/2+4M	-7-11M	M	-1/2-M	0	0	1/2+2M

 

Итерация №1.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i4

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

Следовательно, 1-ая строка является ведущей.

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

Таблица 5 – Симплекс таблица  с обозначенными ведущими строкой  и столбцом

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x8	10	3	0	-4	11	-1	1	0	1	-1	10/11
x2	6	-1	1	11/2	-3	0	-1/2	0	0	1/2	-
x7	6	2	0	-2	-7	0	0	1	0	0	-
F(X2)	6-10M	-3-3M	0	-1/2+4M	-7-11M	M	-1/2-M	0	0	1/2+2M	0

 

Получаем новую симплекс-таблицу:

Таблица 6 – Симплекс-таблица, полученная после вычислений

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9
x4	10/11	3/11	0	-4/11	1	-1/11	1/11	0	1/11	-1/11
x2	88/11	-2/11	1	9/22	0	-3/11	-5/22	0	3/11	5/22
x7	124/11	310/11	0	-46/11	0	-7/11	7/11	1	7/11	-7/11
F(X2)	124/11	-11/11	0	-31/22	0	-7/11	3/22	0	7/11+M	-3/22+M

 

 

 

Итерация №2.

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

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

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3

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

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (⁹/₂₂) и находится на пересечении ведущего столбца и ведущей строки.

Таблица 7 – Симплекс таблица  с обозначенными ведущими строкой  и столбцом

Базис	B	x1	x2	x3	x4	x5	x6	x7	x8	x9	min
x4	10/11	3/11	0	-4/11	1	-1/11	1/11	0	1/11	-1/11	-
x2	88/11	-2/11	1	9/22	0	-3/11	-5/22	0	3/11	5/22	211/3
x7	124/11	310/11	0	-46/11	0	-7/11	7/11	1	7/11	-7/11	-
F(X3)	124/11	-11/11	0	-31/22	0	-7/11	3/22	0	7/11+M	-3/22+M	0