Автор работы: Пользователь скрыл имя, 01 Ноября 2011 в 21:12, задача
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 2x1 + 3x2 при следующих условиях-ограничений.
Двойственный симплекс-метод.
Решим прямую задачу линейного программирования двойственным симплексным методом, с использованием симплексной таблицы.
Приведем систему
ограничений к системе
Определим минимальное значение целевой функции F(X) = 2x1 + 3x2 при следующих условиях-ограничений.
2x1 + x2≤10
- 2x1 + 3x2≤6
- 2x1 - 4x2≤-8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x3. В 2-м неравенстве смысла (≤) вводим базисную переменную x4. В 3-м неравенстве смысла (≤) вводим базисную переменную x5.
2x1 + 1x2 + 1x3 + 0x4 + 0x5 = 10
-2x1 + 3x2 + 0x3 + 1x4 + 0x5 = 6
-2x1-4x2 + 0x3 + 0x4 + 1x5 = -8
Матрица коэффициентов
A = a(ij) этой системы уравнений имеет
вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,10,6,-8)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 10 | 2 | 1 | 1 | 0 | 0 |
| x4 | 6 | -2 | 3 | 0 | 1 | 0 |
| x5 | -8 | -2 | -4 | 0 | 0 | 1 |
| F(X0) | 0 | -2 | -3 | 0 | 0 | 0 |
1. Проверка критерия оптимальности.
План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет 3-ая строка, а переменную x5 следует вывести из базиса.
3. Определение новой базисной переменной.
Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x2 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-4).
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 10 | 2 | 1 | 1 | 0 | 0 |
| x4 | 6 | -2 | 3 | 0 | 1 | 0 |
| x5 | -8 | -2 | -4 | 0 | 0 | 1 |
| F(X) | 0 | -2 | -3 | 0 | 0 | 0 |
| θ | 0 | -2 : (-2) = 1 | -3 : (-4) = 3/4 | - | - | - |
4. Пересчет симплекс-таблицы.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 8 | 11/2 | 0 | 1 | 0 | 1/4 |
| x4 | 0 | -31/2 | 0 | 0 | 1 | 3/4 |
| x2 | 2 | 1/2 | 1 | 0 | 0 | -1/4 |
| F(X0) | 6 | -1/2 | 0 | 0 | 0 | -3/4 |
Представим расчет каждого элемента в виде таблицы:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 10-(-8 • 1):-4 | 2-(-2 • 1):-4 | 1-(-4 • 1):-4 | 1-(0 • 1):-4 | 0-(0 • 1):-4 | 0-(1 • 1):-4 |
| 6-(-8 • 3):-4 | -2-(-2 • 3):-4 | 3-(-4 • 3):-4 | 0-(0 • 3):-4 | 1-(0 • 3):-4 | 0-(1 • 3):-4 |
| -8 : -4 | -2 : -4 | -4 : -4 | 0 : -4 | 0 : -4 | 1 : -4 |
| 0-(-8 • -3):-4 | -2-(-2 • -3):-4 | -3-(-4 • -3):-4 | 0-(0 • -3):-4 | 0-(0 • -3):-4 | 0-(1 • -3):-4 |
В базисном столбце все элементы положительные.
Переходим к
основному алгоритму симплекс-
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 8 | 11/2 | 0 | 1 | 0 | 1/4 |
| x4 | 0 | -31/2 | 0 | 0 | 1 | 3/4 |
| x2 | 2 | 1/2 | 1 | 0 | 0 | -1/4 |
| F(X1) | 6 | -1/2 | 0 | 0 | 0 | -3/4 |
Оптимальный план можно записать так:
x3 = 8
x4 = 0
x2 = 2
F(X) = 3•2 = 6
Решение было получено и оформлено с помощью сервиса:
Двойственный симплекс-метод
Вместе с этой задачей решают также:
Графический метод решения задач линейного программирования
Симплекс-метод
Двойственная задача линейного программирования
Метод Гомори
Транспортная задача