Реализация метода Искусственного Базиса

2.2 Положительность строки F

Проверяем на положительность элементы строки F. Если имеются отрицательные элементы (не считая b₀), выбираем среди отрицательных элементов строки F максимальный по модулю.

-a_0,l=min{-a_0,i }

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

b_k/a_k,l =min {b_i/a_i,l } при a_i,l>0, b_i>0

k - cтрока, для которой  это отношение минимально - ведущая.  Элемент a_k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис.

Пересчитываем симплекс-таблицу  по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2.

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

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

Правила преобразований симплексной таблицы

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

• вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  
• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l
• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l
• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,l×a_k,j/ a_k,l

 

 

 

 

 

 

2.1 Содержательная постановка  задачи

Для составления сплава используется три вида сырья: A1, B1 C1. Определить состав сырьевых материалов, обеспечивающий минимальную стоимость 1 кг. сплава (Табл. 11)

                                                                                                             Таблица 11

Компоненты сплава	Пределы содержания металла	Содержание компонентов  в сырье
		X1	X2
A1	4	1	1
A2	2	1	2
A3	10	1	2
Стоимость сырья		2	-1

 

 

 

 

 

 

 

 

 

 

2.2 Математическая модель задачи

Целевая функция:

Ограничения:

2.3 Решение  задачи вручную

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

x₁ + x₂≥4

x₁ + 2x₂≤2

x₁ + 2x₂≤10

 

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

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ = 4

1x₁ + 2x₂ + 0x₃ + 1x₄ + 0x₅ = 2

1x₁ + 2x₂ + 0x₃ + 0x₄ + 1x₅ = 10

 

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

1x₁ + 1x₂-1x₃ + 0x₄ + 0x₅ + 1x₆ = 4

1x₁ + 2x₂ + 0x₃ + 1x₄ + 0x₅ + 0x₆ = 2

1x₁ + 2x₂ + 0x₃ + 0x₄ + 1x₅ + 0x₆ = 10

 

 

 

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

F(X) = 2x₁-1x₂+Mx₆ → min

 

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

x₆ = 4-x₁-x₂+x₃ которые подставим в целевую функцию:

F(X) = (2-M)x₁+(-1-M)x₂+(M)x₃+(4M) → min

 

Матрица коэффициентов A = a(ij) этой системы уравнений имеет  вид:

 

 

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

x₆, x₄, x₅.

 

Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,2,10,4)

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

 

                                                                                                       Таблица 12

Базис	B	x1	x2	x3	x4	x5	x6
x6	4	1	1	-1	0	0	1
x4	2	1	2	0	1	0	0
x5	10	1	2	0	0	1	0
F(X0)	4M	-2+M	1+M	-M	0	0	0

 

 

 

 

 

Итерация №0.

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

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

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

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

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

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

                                                                                               Таблица 13

Базис	B	x1	x2	x3	x4	x5	x6	min
x6	4	1	1	-1	0	0	1	4
x4	2	1	2	0	1	0	0	1
x5	10	1	2	0	0	1	0	5
F(X1)	4M	-2+M	1+M	-M	0	0	0	0

 

 

 

 

 

 

 

 

 

 

 

 

 

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

                                                                               Таблица 14

Базис	B	x1	x2	x3	x4	x5	x6
x6	3	1/2	0	-1	-1/2	0	1
x2	1	1/2	1	0	1/2	0	0
x5	8	0	0	0	-1	1	0
F(X1)	-1+3M	-21/2+M	0	-M	-1/2-M	0	0

 

Итерация №1.

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                                         Таблица 15

Базис	B	x1	x2	x3	x4	x5	x6	min
x6	3	1/2	0	-1	-1/2	0	1	6
x2	1	1/2	1	0	1/2	0	0	2
x5	8	0	0	0	-1	1	0	-
F(X2)	-1+3M	-21/2+M	0	-M	-1/2-M	0	0	0

                                                                                                

 

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

                                                                                    Таблица 16

Базис	B	x1	x2	x3	x4	x5	x6
x6	2	0	-1	-1	-1	0	1
x1	2	1	2	0	1	0	0
x5	8	0	0	0	-1	1	0
F(X2)	4+2M	0	5-M	-M	2-M	0	0

 

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

Окончательный вариант  симплекс-таблицы (Табл. 17):

 

                                                                                       Таблица 17

 

 

Базис	B	x1	x2	x3	x4	x5	x6
x6	2	0	-1	-1	-1	0	1
x1	2	1	2	0	1	0	0
x5	8	0	0	0	-1	1	0
F(X3)	4+2M	0	5-M	-M	2-M	0	0