Метод ветвей и границ решение задач целочисленного программирования

4 столбец {4}- 4*7=28 – max

Ведущий элемент 

 

1 столбец {9(min)}- 9*2=18

3 столбец {18, }- 18* -max

Ведущий элемент 

2 столбец {-4,5; (min)} (max)

Ответ: { }

F(x)=2*0+3*16,5+4*21+7*0=133,5

F(x)=133,5

Проверим  наш симплекс- метод в программе Microsoft Excel.

Переход к КЗЛП. 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄ → max при ограничениях: 
x₁ - 2x₂ + 2x₃ + x₄ <= 9 
2x₂ - x₃ + 3x₄ <= 12 
Для приведения ЗЛП к канонической форме необходимо: 
В 1-м неравенстве смысла ( <= ) вводим базисную переменную x₅. В 2-м неравенстве смысла ( <= ) вводим базисную переменную x₆.  
1x₁-2x₂ + 2x₃ + 1x₄ + 1x₅ + 0x₆ = 9 
0x₁ + 2x₂-1x₃ + 3x₄ + 0x₅ + 1x₆ = 12 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄ 
Переход к СЗЛП. 
Расширенная матрица системы ограничений-равенств данной задачи:

1 -2 2 1 1 0 9 0 2 -1 3 0 1 12

 
Поскольку в системе имеется единичная  матрица, то в качестве базисных переменных принимаем X = (1,6). 
Соответствующие уравнения имеют вид: 
x₁ - 2x₂ + 2x₃ + x₄ + x₅ = 9 
2x₂ - x₃ + 3x₄ + x₆ = 12 
Выразим базисные переменные через остальные: 
x₁ = 2x₂ - 2x₃ - x₄ - x₅+9 
x₆ = - 2x₂ + x₃ - 3x₄+12 
Подставим их в целевую функцию: 
F(X) = 2( 2x₂ - 2x₃ - x₄ - x₅+9) + 3x₂ + 4x₃ + 7x₄ 
или 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄+18 → max 
Система неравенств: 
2x₂ - 2x₃ - x₄ - x₅+9 >= 0 
- 2x₂ + x₃ - 3x₄+12 >= 0 
Приводим систему неравенств к следующему виду: 
- 2x₂ + 2x₃ + x₄ + x₅ <= 9 
2x₂ - x₃ + 3x₄ <= 12 
F(X) = 2x₁ + 3x₂ + 4x₃ + 7x₄+18 → max 
Упростим систему. 
- 2x₁ + 2x₂ + x₃ + x₄ <= 9 
2x₁ - x₂ + 3x₃ <= 12 
F(X) = 3x₁ + 4x₂ + 7x₃+18 → max 
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. 
Определим максимальное значение целевой функции F(X) = 3x₁ + 4x₂ + 7x₃+18 при следующих условиях-ограничений. 
При вычислениях значение Fc = 18 временно не учитываем. 
- 2x₁ + 2x₂ + x₃ + x₄ <= 9 
2x₁ - x₂ + 3x₃ <= 12 
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). 
В 1-м неравенстве смысла ( <= ) вводим базисную переменную x₅. В 2-м неравенстве смысла ( <= ) вводим базисную переменную x₆.  
-2x₁ + 2x₂ + 1x₃ + 1x₄ + 1x₅ + 0x₆ = 9 
2x₁-1x₂ + 3x₃ + 0x₄ + 0x₅ + 1x₆ = 12 
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =	-2 2 1 1 1 0 2 -1 3 0 0 1

 
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. 
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана. 
Решим систему уравнений относительно базисных переменных: 
x₅, x₆, 
Полагая, что свободные переменные равны 0, получим первый опорный план: 
X1 = (0,0,0,0,9,12) 
Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6
x5	9	-2	2	1	1	1	0
x6	12	2	-1	3	0	0	1
F(X0)	0	-3	-4	-7	0	0	0

 
Переходим к основному алгоритму  симплекс-метода. 
Итерация №0. 
1. Проверка критерия оптимальности. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
2. Определение новой базисной переменной. 
В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю. 
3. Определение новой свободной переменной. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 
и из них выберем наименьшее: 
min (9 : 1 , 12 : 3 ) = 4 
Следовательно, 2-ая строка является ведущей. 
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x5	9	-2	2	1	1	1	0	9
x6	12	2	-1	3	0	0	1	4
F(X1)	0	-3	-4	-7	0	0	0	0

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

B	x 1	x 2	x 3	x 4	x 5	x 6
9-(12 • 1):3	-2-(2 • 1):3	2-(-1 • 1):3	1-(3 • 1):3	1-(0 • 1):3	1-(0 • 1):3	0-(1 • 1):3
12 : 3	2 : 3	-1 : 3	3 : 3	0 : 3	0 : 3	1 : 3
0-(12 • -7):3	-3-(2 • -7):3	-4-(-1 • -7):3	-7-(3 • -7):3	0-(0 • -7):3	0-(0 • -7):3	0-(1 • -7):3

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

Базис	B	x1	x2	x3	x4	x5	x6
x5	5	-22/3	21/3	0	1	1	-1/3
x3	4	2/3	-1/3	1	0	0	1/3
F(X1)	28	12/3	-61/3	0	0	0	21/3

 
Итерация №1. 
1. Проверка критерия оптимальности. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
2. Определение новой базисной переменной. 
В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю. 
3. Определение новой свободной переменной. 
Вычислим значения D_i по строкам как частное от деления: b_i / a_i2 
и из них выберем наименьшее: 
min (5 : 2¹/₃ , - ) = 2¹/₇ 
Следовательно, 1-ая строка является ведущей. 
Разрешающий элемент равен (2¹/₃) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x5	5	-22/3		0	1	1	-1/3
x3	4	2/3	-1/3	1	0	0	1/3	-
F(X2)	28	12/3		0	0	0	21/3	0

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

B	x 1	x 2	x 3	x 4	x 5	x 6
5 : 21/3	-22/3 : 21/3	21/3 : 21/3	0 : 21/3	1 : 21/3	1 : 21/3	-1/3 : 21/3
4-(5 • -1/3):21/3	2/3-(-22/3 • -1/3):21/3	-1/3-(21/3 • -1/3):21/3	1-(0 • -1/3):21/3	0-(1 • -1/3):21/3	0-(1 • -1/3):21/3	1/3-(-1/3 • -1/3):21/3
28-(5 • -61/3):21/3	12/3-(-22/3 • -61/3):21/3	-61/3-(21/3 • -61/3):21/3	0-(0 • -61/3):21/3	0-(1 • -61/3):21/3	0-(1 • -61/3):21/3	21/3-(-1/3 • -61/3):21/3

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

Базис	B	x1	x2	x3	x4	x5	x6
x2	21/7	-11/7	1	0	3/7	3/7	-1/7
x3	45/7	2/7	0	1	1/7	1/7	2/7
F(X2)	414/7	-54/7	0	0	25/7	25/7	13/7