Автор: Пользователь скрыл имя, 20 Декабря 2011 в 14:20, задача
Работа содержит решенную задачу по симплекс-методу: Решить с помощью симплек-метода задачу двойственного программирования
Решить графически и симплекс-методом задачи линейного программирования. Записать задачу двойственную данной:
Определим максимальное значение целевой функции F(X) = x1 + x2 при следующих условиях-ограничений.
3x1 + x2≤9
x1 + 2x2≤6
Шаг:1
Избавимся от неравенств в ограничениях,
введя в ограничения 1, 2, 3 неотрицательные
балансовые переменные s1, s2, s3.
| 3 | x1 | + | x2 | + | s1 | = | 9 | (1) | |||||||||||
| x1 | + | 2 | x2 | + | s2 | = | 6 | (2) | |||||||||||
x1, x2, s1, s2 ≥ 0
Матрица коэффициентов
A = a(ij) этой системы уравнений имеет
вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,9,6)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | B | x1 | X2 | S1 | S2 |
| x3 | 9 | 3 | 1 | 1 | 0 |
| x4 | 6 | 1 | 2 | 0 | 1 |
| F(X0) | 0 | -1 | -1 | 0 | 0 |
Переходим к
основному алгоритму симплекс-
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (9 : 1 , 6 : 2 ) = 3
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | S1 | S2 | min |
| x3 | 9 | 3 | 1 | 1 | 0 | 9 |
| x4 | 6 | 1 | 2 | 0 | 1 | 3 |
| F(X1) | 0 | -1 | -1 | 0 | 0 | 0 |
4. Пересчет симплекс-таблицы.
Представим расчет каждого элемента в виде таблицы:
| B | x 1 | x 2 | S1 | S2 |
| 9-(6 • 1):2 | 3-(1 • 1):2 | 1-(2 • 1):2 | 1-(0 • 1):2 | 0-(1 • 1):2 |
| 6 : 2 | 1 : 2 | 2 : 2 | 0 : 2 | 1 : 2 |
| 0-(6 • -1):2 | -1-(1 • -1):2 | -1-(2 • -1):2 | 0-(0 • -1):2 | 0-(1 • -1):2 |
Получаем новую
симплекс-таблицу:
| Базис | B | x1 | x2 | S1 | S2 |
| x3 | 6 | 21/2 | 0 | 1 | -1/2 |
| x2 | 3 | 1/2 | 1 | 0 | 1/2 |
| F(X1) | 3 | -1/2 | 0 | 0 | 1/2 |
Итерация №1.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (6 : 21/2 , 3 : 1/2 ) = 22/5
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (21/2) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | S1 | S2 | min |
| x3 | 6 | 21/2 | 0 | 1 | -1/2 | 22/5 |
| x2 | 3 | 1/2 | 1 | 0 | 1/2 | 6 |
| F(X2) | 3 | -1/2 | 0 | 0 | 1/2 | 0 |
4. Пересчет симплекс-таблицы.
Представим расчет каждого элемента в виде таблицы:
| B | x 1 | x 2 | S1 | S2 |
| 6 : 21/2 | 21/2 : 21/2 | 0 : 21/2 | 1 : 21/2 | -1/2 : 21/2 |
| 3-(6 • 1/2):21/2 | 1/2-(21/2 • 1/2):21/2 | 1-(0 • 1/2):21/2 | 0-(1 • 1/2):21/2 | 1/2-(-1/2 • 1/2):21/2 |
| 3-(6 • -1/2):21/2 | -1/2-(21/2 • -1/2):21/2 | 0-(0 • -1/2):21/2 | 0-(1 • -1/2):21/2 | 1/2-(-1/2 • -1/2):21/2 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | S1 | S2 |
| x1 | 2,4 | 1 | 0 | 0,4 | -0,2 |
| x2 | 1,8 | 0 | 1 | -0,2 | 0,6 |
| F(X2) | 4,2 | 0 | 0 | 0,2 | 0,4 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный
вариант симплекс-таблицы:
| Базис | B | x1 | x2 | S1 | S2 |
| x1 | 2,4 | 1 | 0 | 0,4 | -0,2 |
| x2 | 1,8 | 0 | 1 | -0,2 | 0,6 |
| F(X3) | 4,2 | 0 | 0 | 0,2 | 0,4 |
Оптимальный план можно записать так:
x1 = 2,4
x2 = 1,8
F(X) = 1•2,4 + 1•1,8 =
4,2
Решим задачу графически