Автор: Пользователь скрыл имя, 13 Сентября 2013 в 12:34, контрольная работа
В данной работе решаются задачи линейного программирования симплексным методом, с использованием симплексной таблицы.
Вариант № 9
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 5x1 + 3x2 + 2x3 + x4 при следующих условиях-ограничений.
2x1 + x2 + x3 + 3x4≤300
x1 + 2x3 + x4≤100
x1 + 2x2 + x3≤400
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x5. В 2-м неравенстве смысла (≤) вводим базисную переменную x6. В 3-м неравенстве смысла (≤) вводим базисную переменную x7.
2x1 + 1x2 + 1x3 + 3x4 + 1x5 + 0x6 + 0x7 = 300
1x1 + 0x2 + 2x3 + 1x4 + 0x5 + 1x6 + 0x7 = 100
1x1 + 2x2 + 1x3 + 0x4 + 0x5 + 0x6 + 1x7 = 400
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
2 |
1 |
1 |
3 |
1 |
0 |
0 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
1 |
2 |
1 |
0 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x5, x6, x7,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,300,100,400)
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x5 |
300 |
2 |
1 |
1 |
3 |
1 |
0 |
0 |
x6 |
100 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
x7 |
400 |
1 |
2 |
1 |
0 |
0 |
0 |
1 |
F(X0) |
0 |
-5 |
-3 |
-2 |
-1 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (300 : 2 , 100 : 1 , 400 : 1 ) = 100
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
min |
x5 |
300 |
2 |
1 |
1 |
3 |
1 |
0 |
0 |
150 |
x6 |
100 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
100 |
x7 |
400 |
1 |
2 |
1 |
0 |
0 |
0 |
1 |
400 |
F(X1) |
0 |
-5 |
-3 |
-2 |
-1 |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 1 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
|
300-(100 • 2):1 |
2-(1 • 2):1 |
1-(0 • 2):1 |
1-(2 • 2):1 |
3-(1 • 2):1 |
1-(0 • 2):1 |
0-(1 • 2):1 |
0-(0 • 2):1 |
100 : 1 |
1 : 1 |
0 : 1 |
2 : 1 |
1 : 1 |
0 : 1 |
1 : 1 |
0 : 1 |
400-(100 • 1):1 |
1-(1 • 1):1 |
2-(0 • 1):1 |
1-(2 • 1):1 |
0-(1 • 1):1 |
0-(0 • 1):1 |
0-(1 • 1):1 |
1-(0 • 1):1 |
0-(100 • -5):1 |
-5-(1 • -5):1 |
-3-(0 • -5):1 |
-2-(2 • -5):1 |
-1-(1 • -5):1 |
0-(0 • -5):1 |
0-(1 • -5):1 |
0-(0 • -5):1 |
Получаем новую симплекс-
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x5 |
100 |
0 |
1 |
-3 |
1 |
1 |
-2 |
0 |
x1 |
100 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
x7 |
300 |
0 |
2 |
-1 |
-1 |
0 |
-1 |
1 |
F(X1) |
500 |
0 |
-3 |
8 |
4 |
0 |
5 |
0 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (100 : 1 , - , 300 : 2 ) = 100
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
min |
x5 |
100 |
0 |
1 |
-3 |
1 |
1 |
-2 |
0 |
100 |
x1 |
100 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
- |
x7 |
300 |
0 |
2 |
-1 |
-1 |
0 |
-1 |
1 |
150 |
F(X2) |
500 |
0 |
-3 |
8 |
4 |
0 |
5 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
|
100 : 1 |
0 : 1 |
1 : 1 |
-3 : 1 |
1 : 1 |
1 : 1 |
-2 : 1 |
0 : 1 |
100-(100 • 0):1 |
1-(0 • 0):1 |
0-(1 • 0):1 |
2-(-3 • 0):1 |
1-(1 • 0):1 |
0-(1 • 0):1 |
1-(-2 • 0):1 |
0-(0 • 0):1 |
300-(100 • 2):1 |
0-(0 • 2):1 |
2-(1 • 2):1 |
-1-(-3 • 2):1 |
-1-(1 • 2):1 |
0-(1 • 2):1 |
-1-(-2 • 2):1 |
1-(0 • 2):1 |
500-(100 • -3):1 |
0-(0 • -3):1 |
-3-(1 • -3):1 |
8-(-3 • -3):1 |
4-(1 • -3):1 |
0-(1 • -3):1 |
5-(-2 • -3):1 |
0-(0 • -3):1 |
Получаем новую симплекс-
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x2 |
100 |
0 |
1 |
-3 |
1 |
1 |
-2 |
0 |
x1 |
100 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
x7 |
100 |
0 |
0 |
5 |
-3 |
-2 |
3 |
1 |
F(X2) |
800 |
0 |
0 |
-1 |
7 |
3 |
-1 |
0 |