Решим задачу симплекс- методом

Решим прямую задачку линейного программирования симплексным способом, с внедрением симплексной таблицы.
Определим наибольшее значение мотивированной функции F(X) = 11x1+10x2 при последующих условиях-ограничений.
7x1+8x2≤50
6x1+3x2≤35
4x1+x2≤17
Для построения первого опорного плана систему неравенств приведем к системе уравнений методом введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве Решим задачу симплекс- методом смысла (≤) вводим базовую переменную x3. В 2-м неравенстве смысла (≤) вводим базовую переменную x4. В 3-м неравенстве смысла (≤) вводим базовую переменную x5.
7x1 + 8x2 + 1x3 + 0x4 + 0x5 = 50
6x1 + 3x2 + 0x3 + 1x4 + 0x5 = 35
4x1 + 1x2 + 0x3 + 0x4 + 1x5 = 17
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =


Базовые переменные Решим задачу симплекс- методом это переменные, которые входят исключительно в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базовых переменных: x3, x4, x5
Полагая, что свободные переменные равны 0, получим 1-ый опорный план:
X0 = (0,0,50,35,17)
Базовое решение именуется допустимым, если оно неотрицательно.

Базис B x1 x2 x3 x Решим задачу симплекс- методом4 x5
x3
x4
x5
F(X0) -11 -10


Перебегаем к основному методу симплекс-метода.
Итерация №0.
1. Проверка аспекта оптимальности.
Текущий опорный план неоптимален, потому что в индексной строке находятся отрицательные коэффициенты.
2. Определение новейшей базовой переменной.
В качестве ведущего выберем столбец, соответственный переменной x1, потому что это больший коэффициент по модулю.
3. Определение Решим задачу симплекс- методом новейшей свободной переменной.
Вычислим значения Di по строчкам как личное от деления: bi / ai1
и из их выберем меньшее:
min (50 : 7 , 35 : 6 , 17 : 4 ) = 41/4
Как следует, 3-ая строчка является ведущей.
Разрешающий элемент равен (4) и находится на скрещении ведущего столбца и ведущей строчки.

Базис B x1 x2 x3 x4 x5 min
x3 50/7
x4 35/6
x5 41/4
F(X1) -11 -10


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

B x1 x2 x3 x4 x5
50-(17 • 7):4 7-(4 • 7):4 8-(1 • 7):4 1-(0 • 7):4 0-(0 • 7):4 0-(1 • 7):4
35-(17 • 6):4 6-(4 • 6):4 3-(1 • 6):4 0-(0 • 6):4 1-(0 • 6):4 0-(1 • 6):4
17 : 4 4 : 4 1 : 4 0 : 4 0 : 4 1 : 4
0-(17 • -11):4 -11-(4 • -11):4 -10-(1 • -11):4 0-(0 • -11):4 0-(0 • -11):4 0-(1 • -11):4


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

Базис B x1 x2 x3 x4 x5
x3 81/4 25/4 -7/4
x4 19/2 3/2 -3/2
x1 17/4 1/4 1/4
F Решим задачу симплекс- методом(X1) 187/4 -29/4 11/4


Итерация №1.
1. Проверка аспекта оптимальности.
Текущий опорный план неоптимален, потому что в индексной строке находятся отрицательные коэффициенты.
2. Определение новейшей базовой переменной.
В качестве ведущего выберем столбец, соответственный переменной x2, потому что это больший коэффициент по модулю.
3. Определение новейшей свободной переменной.
Вычислим значения Di по строчкам как Решим задачу симплекс- методом личное от деления: bi / ai2
и из их выберем меньшее:
min (201/4 : 61/4 , 91/2 : 11/2 , 41/4 : 1/4 ) = 36/25
Как следует, 1-ая строчка является ведущей.
Разрешающий элемент равен (61/4) и находится на скрещении ведущего столбца и ведущей строчки.

Базис B x1 x2 x3 x4 x5 min
x3 81/4 61/4 -7/4 36/25
x4 19/2 3/2 -3/2 19/3
x1 17/4 1/4 1/4
F(X2) 187/4 -71/4 11/4


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

B x1 x2 x3 x4 x5
201/4 : 61/4 0 : 61/4 61/4 : 61/4 1 : 61/4 0 : 61/4 -13/4 : 61/4
91/2-(201/4 • 11/2):61/4 0-(0 • 11/2):61/4 11/2-(61/4• 11/2):61/4 0-(1 • 11/2):61/4 1-(0 • 11/2):61/4 -11/2-(-13/4 • 11/2):61/4
41/4-(201/4 •1/4):61/4 1-(0 •1/4):61/4 1/4-(61/4 •1/4):61/4 0-(1 •1/4):61/4 0-(0 •1/4):61/4 1/4-(-13/4• 1/4):61/4
463/4-(201/4 • -71/4):61/4 0-(0 • -71/4):61/4 -71/4-(61/4 • -71/4):61/4 0-(1 • -71/4):61/4 0-(0 • -71/4):61/4 23/4-(-13/4 • -71/4):61/4

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

Базис B x1 x2 x3 x4 x5
x2 81/25 4/25 -7/25
x4 116/25 -6/25 -27/25
x1 86/25 -1/25 8/25
F(X2) 1756/25 29/25 18/25


1. Проверка аспекта оптимальности.
Посреди значений индексной Решим задачу симплекс- методом строчки нет отрицательных. Потому эта таблица определяет лучший план задачки.
Окончательный вариант симплекс-таблицы:

Базис B x1 x2 x3 x4 x5
x2 81/25 4/25 -7/25
x4 116/25 -6/25 -27/25
x1 86/25 -1/25 8/25
F(X3) 1756/25 29/25 18/25


Лучший план можно записать так:
x1 = 311/25, x2 = 36/25
F(X) = 11•311/25 + 10•36/25 = 706/25


reshetchatie-stojki-zdanij-i-ih-raschet.html
reshetova-za-formirovanie-sistemnogo-mishleniya-v-obuchenii.html
reshim-zadachu-simpleks-metodom.html