Автор: Пользователь скрыл имя, 13 Сентября 2013 в 12:34, контрольная работа
В данной работе решаются задачи линейного программирования симплексным методом, с использованием симплексной таблицы.
Итерация №2.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai6
и из них выберем наименьшее:
min (- , 100 : 1 , 100 : 3 ) = 331/3
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
min |
x2 |
100 |
0 |
1 |
-3 |
1 |
1 |
-2 |
0 |
- |
x1 |
100 |
1 |
0 |
2 |
1 |
0 |
1 |
0 |
100 |
x7 |
100 |
0 |
0 |
5 |
-3 |
-2 |
3 |
1 |
331/3 |
|
F(X3) |
800 |
0 |
0 |
-1 |
7 |
3 |
-1 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 3 войдет переменная x6.
Строка, соответствующая переменной x6 в плане 3, получена в результате деления всех элементов строки x7 плана 2 на разрешающий элемент РЭ=3
На месте разрешающего элемента в плане 3 получаем 1.
В остальных клетках столбца x6 плана 3 записываем нули.
Таким образом, в новом плане 3 заполнены строка x6 и столбец x6.
Все остальные элементы нового плана 3, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
|
100-(100 • -2):3 |
0-(0 • -2):3 |
1-(0 • -2):3 |
-3-(5 • -2):3 |
1-(-3 • -2):3 |
1-(-2 • -2):3 |
-2-(3 • -2):3 |
0-(1 • -2):3 |
100-(100 • 1):3 |
1-(0 • 1):3 |
0-(0 • 1):3 |
2-(5 • 1):3 |
1-(-3 • 1):3 |
0-(-2 • 1):3 |
1-(3 • 1):3 |
0-(1 • 1):3 |
100 : 3 |
0 : 3 |
0 : 3 |
5 : 3 |
-3 : 3 |
-2 : 3 |
3 : 3 |
1 : 3 |
800-(100 • -1):3 |
0-(0 • -1):3 |
0-(0 • -1):3 |
-1-(5 • -1):3 |
7-(-3 • -1):3 |
3-(-2 • -1):3 |
-1-(3 • -1):3 |
0-(1 • -1):3 |
Получаем новую симплекс-
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x2 |
1662/3 |
0 |
1 |
1/3 |
-1 |
-1/3 |
0 |
2/3 |
|
x1 |
662/3 |
1 |
0 |
1/3 |
2 |
2/3 |
0 |
-1/3 |
|
x6 |
331/3 |
0 |
0 |
12/3 |
-1 |
-2/3 |
1 |
1/3 |
|
F(X3) |
8331/3 |
0 |
0 |
2/3 |
6 |
21/3 |
0 |
1/3 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
x2 |
1662/3 |
0 |
1 |
1/3 |
-1 |
-1/3 |
0 |
2/3 |
|
x1 |
662/3 |
1 |
0 |
1/3 |
2 |
2/3 |
0 |
-1/3 |
|
x6 |
331/3 |
0 |
0 |
12/3 |
-1 |
-2/3 |
1 |
1/3 |
|
F(X4) |
8331/3 |
0 |
0 |
2/3 |
6 |
21/3 |
0 |
1/3 |
Оптимальный план можно записать так:
x2 = 1662/3
x1 = 662/3
F(X) = 3•1662/3 + 5•662/3 = 8331/3
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x6. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 331/3
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.
Значение 2/3> 0 в столбце x3 означает, что использование x3 - не выгодно.
Значение 6> 0 в столбце x4 означает, что использование x4 - не выгодно.
Значение 21/3 в столбце x5 означает, что теневая цена (двойственная оценка) равна 21/3.
Значение 1/3 в столбце x7 означает, что теневая цена (двойственная оценка) равна 1/3.