Симплекс-метод
Решение задач графически и симплекс-методом. Экономическое толкование полученных решений. Решение двойственной задачи для оптимальной системы оценок ресурсов. Определение дефицитных и недефицитных ресурсов. Обоснование эффективности оптимального плана.
Рубрика | Экономико-математическое моделирование |
Вид | контрольная работа |
Язык | русский |
Дата добавления | 13.09.2015 |
Размер файла | 226,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (44/5) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
min |
|
x10 |
2 |
0 |
0 |
-1 |
1/5 |
0 |
0 |
0 |
4/5 |
0 |
1 |
-1/5 |
0 |
0 |
-4/5 |
21/2 |
|
x6 |
1 |
0 |
0 |
0 |
-1/5 |
0 |
1 |
0 |
1/5 |
0 |
0 |
1/5 |
0 |
-1 |
-1/5 |
5 |
|
x12 |
4 |
0 |
0 |
0 |
1/5 |
-1 |
0 |
0 |
44/5 |
0 |
0 |
-1/5 |
1 |
0 |
-44/5 |
5/6 |
|
x1 |
1 |
1 |
0 |
0 |
-1/5 |
0 |
0 |
0 |
1/5 |
0 |
0 |
1/5 |
0 |
0 |
-1/5 |
5 |
|
x7 |
3 |
0 |
0 |
0 |
1/5 |
0 |
0 |
1 |
-1/5 |
0 |
0 |
-1/5 |
0 |
0 |
1/5 |
- |
|
x2 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
0 |
1 |
- |
|
x9 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
-1 |
4 |
|
F(X4) |
7-6M |
0 |
0 |
M |
-12/5-2/5M |
M |
0 |
0 |
22/5-53/5M |
0 |
0 |
12/5+12/5M |
0 |
M |
-22/5+63/5M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x12 в план 4 войдет переменная x8.
Строка, соответствующая переменной x8 в плане 4, получена в результате деления всех элементов строки x12 плана 3 на разрешающий элемент РЭ=44/5
На месте разрешающего элемента в плане 4 получаем 1.
В остальных клетках столбца x8 плана 4 записываем нули.
Таким образом, в новом плане 4 заполнены строка x8 и столбец x8.
Все остальные элементы нового плана 4, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
2-(4 * 4/5):44/5 |
0-(0 * 4/5):44/5 |
0-(0 * 4/5):44/5 |
-1-(0 * 4/5):44/5 |
1/5-(1/5 * 4/5):44/5 |
0-(-1 * 4/5):44/5 |
0-(0 * 4/5):44/5 |
0-(0 * 4/5):44/5 |
|
1-(4 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
-1/5-(1/5 * 1/5):44/5 |
0-(-1 * 1/5):44/5 |
1-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
|
4 : 44/5 |
0 : 44/5 |
0 : 44/5 |
0 : 44/5 |
1/5 : 44/5 |
-1 : 44/5 |
0 : 44/5 |
0 : 44/5 |
|
1-(4 * 1/5):44/5 |
1-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
-1/5-(1/5 * 1/5):44/5 |
0-(-1 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
|
3-(4 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
1/5-(1/5 * -1/5):44/5 |
0-(-1 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
1-(0 * -1/5):44/5 |
|
0-(4 * -1):44/5 |
0-(0 * -1):44/5 |
1-(0 * -1):44/5 |
0-(0 * -1):44/5 |
0-(1/5 * -1):44/5 |
0-(-1 * -1):44/5 |
0-(0 * -1):44/5 |
0-(0 * -1):44/5 |
|
4-(4 * 1):44/5 |
0-(0 * 1):44/5 |
0-(0 * 1):44/5 |
0-(0 * 1):44/5 |
0-(1/5 * 1):44/5 |
0-(-1 * 1):44/5 |
0-(0 * 1):44/5 |
0-(0 * 1):44/5 |
|
(-22/5+63/5M)-(4 * (22/5-53/5M)):44/5 |
(0)-(0 * (22/5-53/5M)):44/5 |
(0)-(0 * (22/5-53/5M)):44/5 |
(M)-(0 * (22/5-53/5M)):44/5 |
(-12/5-2/5M)-(1/5 * (22/5-53/5M)):44/5 |
(M)-(-1 * (22/5-53/5M)):44/5 |
(0)-(0 * (22/5-53/5M)):44/5 |
(0)-(0 * (22/5-53/5M)):44/5 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
4/5-(44/5 * 4/5):44/5 |
0-(0 * 4/5):44/5 |
1-(0 * 4/5):44/5 |
-1/5-(-1/5 * 4/5):44/5 |
0-(1 * 4/5):44/5 |
0-(0 * 4/5):44/5 |
-4/5-(-44/5 * 4/5):44/5 |
|
1/5-(44/5 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
1/5-(-1/5 * 1/5):44/5 |
0-(1 * 1/5):44/5 |
-1-(0 * 1/5):44/5 |
-1/5-(-44/5 * 1/5):44/5 |
|
44/5 : 44/5 |
0 : 44/5 |
0 : 44/5 |
-1/5 : 44/5 |
1 : 44/5 |
0 : 44/5 |
-44/5 : 44/5 |
|
1/5-(44/5 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
1/5-(-1/5 * 1/5):44/5 |
0-(1 * 1/5):44/5 |
0-(0 * 1/5):44/5 |
-1/5-(-44/5 * 1/5):44/5 |
|
-1/5-(44/5 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
-1/5-(-1/5 * -1/5):44/5 |
0-(1 * -1/5):44/5 |
0-(0 * -1/5):44/5 |
1/5-(-44/5 * -1/5):44/5 |
|
-1-(44/5 * -1):44/5 |
0-(0 * -1):44/5 |
0-(0 * -1):44/5 |
0-(-1/5 * -1):44/5 |
0-(1 * -1):44/5 |
0-(0 * -1):44/5 |
1-(-44/5 * -1):44/5 |
|
1-(44/5 * 1):44/5 |
1-(0 * 1):44/5 |
0-(0 * 1):44/5 |
0-(-1/5 * 1):44/5 |
0-(1 * 1):44/5 |
0-(0 * 1):44/5 |
-1-(-44/5 * 1):44/5 |
|
(22/5-53/5M)-(44/5 * (22/5-53/5M)):44/5 |
(0)-(0 * (22/5-53/5M)):44/5 |
(0)-(0 * (22/5-53/5M)):44/5 |
(12/5+12/5M)-(-1/5 * (22/5-53/5M)):44/5 |
(0)-(1 * (22/5-53/5M)):44/5 |
(M)-(0 * (22/5-53/5M)):44/5 |
(-22/5+63/5M)-(-44/5 * (22/5-53/5M)):44/5 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x10 |
4/3 |
0 |
0 |
-1 |
1/6 |
1/6 |
0 |
0 |
0 |
0 |
1 |
-1/6 |
-1/6 |
0 |
0 |
|
x6 |
5/6 |
0 |
0 |
0 |
-5/24 |
1/24 |
1 |
0 |
0 |
0 |
0 |
5/24 |
-1/24 |
-1 |
0 |
|
x8 |
5/6 |
0 |
0 |
0 |
1/24 |
-5/24 |
0 |
0 |
1 |
0 |
0 |
-1/24 |
5/24 |
0 |
-1 |
|
x1 |
5/6 |
1 |
0 |
0 |
-5/24 |
1/24 |
0 |
0 |
0 |
0 |
0 |
5/24 |
-1/24 |
0 |
0 |
|
x7 |
19/6 |
0 |
0 |
0 |
5/24 |
-1/24 |
0 |
1 |
0 |
0 |
0 |
-5/24 |
1/24 |
0 |
0 |
|
x2 |
5/6 |
0 |
1 |
0 |
1/24 |
-5/24 |
0 |
0 |
0 |
0 |
0 |
-1/24 |
5/24 |
0 |
0 |
|
x9 |
19/6 |
0 |
0 |
0 |
-1/24 |
5/24 |
0 |
0 |
0 |
1 |
0 |
1/24 |
-5/24 |
0 |
0 |
|
F(X4) |
5-11/3M |
0 |
0 |
M |
-11/2-M |
1/2-M |
0 |
0 |
0 |
0 |
0 |
11/2+11/6M |
-1/2+11/6M |
M |
M |
Итерация №4.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai4
и из них выберем наименьшее:
min (11/3 : 1/6 , - , 5/6 : 1/24 , - , 31/6 : 5/24 , 5/6 : 1/24 , - ) = 8
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (1/6) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
min |
|
x10 |
11/3 |
0 |
0 |
-1 |
1/6 |
1/6 |
0 |
0 |
0 |
0 |
1 |
-1/6 |
-1/6 |
0 |
0 |
8 |
|
x6 |
5/6 |
0 |
0 |
0 |
-5/24 |
1/24 |
1 |
0 |
0 |
0 |
0 |
5/24 |
-1/24 |
-1 |
0 |
- |
|
x8 |
5/6 |
0 |
0 |
0 |
1/24 |
-5/24 |
0 |
0 |
1 |
0 |
0 |
-1/24 |
5/24 |
0 |
-1 |
20 |
|
x1 |
5/6 |
1 |
0 |
0 |
-5/24 |
1/24 |
0 |
0 |
0 |
0 |
0 |
5/24 |
-1/24 |
0 |
0 |
- |
|
x7 |
31/6 |
0 |
0 |
0 |
5/24 |
-1/24 |
0 |
1 |
0 |
0 |
0 |
-5/24 |
1/24 |
0 |
0 |
151/5 |
|
x2 |
5/6 |
0 |
1 |
0 |
1/24 |
-5/24 |
0 |
0 |
0 |
0 |
0 |
-1/24 |
5/24 |
0 |
0 |
20 |
|
x9 |
31/6 |
0 |
0 |
0 |
-1/24 |
5/24 |
0 |
0 |
0 |
1 |
0 |
1/24 |
-5/24 |
0 |
0 |
- |
|
F(X5) |
5-11/3M |
0 |
0 |
M |
-11/2-M |
1/2-M |
0 |
0 |
0 |
0 |
0 |
11/2+11/6M |
-1/2+11/6M |
M |
M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x10 в план 5 войдет переменная x4.
Строка, соответствующая переменной x4 в плане 5, получена в результате деления всех элементов строки x10 плана 4 на разрешающий элемент РЭ=1/6
На месте разрешающего элемента в плане 5 получаем 1.
В остальных клетках столбца x4 плана 5 записываем нули.
Таким образом, в новом плане 5 заполнены строка x4 и столбец x4.
Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
11/3 : 1/6 |
0 : 1/6 |
0 : 1/6 |
-1 : 1/6 |
1/6 : 1/6 |
1/6 : 1/6 |
0 : 1/6 |
0 : 1/6 |
|
5/6-(11/3 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(-1 * -5/24):1/6 |
-5/24-(1/6 * -5/24):1/6 |
1/24-(1/6 * -5/24):1/6 |
1-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
|
5/6-(11/3 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(-1 * 1/24):1/6 |
1/24-(1/6 * 1/24):1/6 |
-5/24-(1/6 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
|
5/6-(11/3 * -5/24):1/6 |
1-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(-1 * -5/24):1/6 |
-5/24-(1/6 * -5/24):1/6 |
1/24-(1/6 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
|
31/6-(11/3 * 5/24):1/6 |
0-(0 * 5/24):1/6 |
0-(0 * 5/24):1/6 |
0-(-1 * 5/24):1/6 |
5/24-(1/6 * 5/24):1/6 |
-1/24-(1/6 * 5/24):1/6 |
0-(0 * 5/24):1/6 |
1-(0 * 5/24):1/6 |
|
5/6-(11/3 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
1-(0 * 1/24):1/6 |
0-(-1 * 1/24):1/6 |
1/24-(1/6 * 1/24):1/6 |
-5/24-(1/6 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
|
31/6-(11/3 * -1/24):1/6 |
0-(0 * -1/24):1/6 |
0-(0 * -1/24):1/6 |
0-(-1 * -1/24):1/6 |
-1/24-(1/6 * -1/24):1/6 |
5/24-(1/6 * -1/24):1/6 |
0-(0 * -1/24):1/6 |
0-(0 * -1/24):1/6 |
|
(M)-(11/3*(-11/2-M)):1/6 |
(0)-(0 * (-11/2-M)):1/6 |
(0)-(0 * (-11/2-M)):1/6 |
(M)-(-1 * (-11/2-M)):1/6 |
(-11/2-M)-(1/6 * (-11/2-M)):1/6 |
(1/2-M)-(1/6 * (-11/2-M)):1/6 |
(0)-(0 * (-11/2-M)):1/6 |
(0)-(0 * (-11/2-M)):1/6 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
0 : 1/6 |
0 : 1/6 |
1 : 1/6 |
-1/6 : 1/6 |
-1/6 : 1/6 |
0 : 1/6 |
0 : 1/6 |
|
0-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(1 * -5/24):1/6 |
5/24-(-1/6 * -5/24):1/6 |
-1/24-(-1/6 * -5/24):1/6 |
-1-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
|
1-(0 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(1 * 1/24):1/6 |
-1/24-(-1/6 * 1/24):1/6 |
5/24-(-1/6 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
-1-(0 * 1/24):1/6 |
|
0-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(1 * -5/24):1/6 |
5/24-(-1/6 * -5/24):1/6 |
-1/24-(-1/6 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
0-(0 * -5/24):1/6 |
|
0-(0 * 5/24):1/6 |
0-(0 * 5/24):1/6 |
0-(1 * 5/24):1/6 |
-5/24-(-1/6 * 5/24):1/6 |
1/24-(-1/6 * 5/24):1/6 |
0-(0 * 5/24):1/6 |
0-(0 * 5/24):1/6 |
|
0-(0 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(1 * 1/24):1/6 |
-1/24-(-1/6 * 1/24):1/6 |
5/24-(-1/6 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
0-(0 * 1/24):1/6 |
|
0-(0 * -1/24):1/6 |
1-(0 * -1/24):1/6 |
0-(1 * -1/24):1/6 |
1/24-(-1/6 * -1/24):1/6 |
-5/24-(-1/6 * -1/24):1/6 |
0-(0 * -1/24):1/6 |
0-(0 * -1/24):1/6 |
|
(0)-(0 * (-11/2-M)):1/6 |
(0)-(0 * (-11/2-M)):1/6 |
(0)-(1 * (-11/2-M)):1/6 |
(11/2+11/6M)-(-1/6 * (-11/2-M)):1/6 |
(-1/2+11/6M)-(-1/6 * (-11/2-M)):1/6 |
(M)-(0 * (-11/2-M)):1/6 |
(M)-(0 * (-11/2-M)):1/6 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x4 |
8 |
0 |
0 |
-6 |
1 |
1 |
0 |
0 |
0 |
0 |
6 |
-1 |
-1 |
0 |
0 |
|
x6 |
5/2 |
0 |
0 |
-5/4 |
0 |
1/4 |
1 |
0 |
0 |
0 |
5/4 |
0 |
-1/4 |
-1 |
0 |
|
x8 |
1/2 |
0 |
0 |
1/4 |
0 |
-1/4 |
0 |
0 |
1 |
0 |
-1/4 |
0 |
1/4 |
0 |
-1 |
|
x1 |
5/2 |
1 |
0 |
-5/4 |
0 |
1/4 |
0 |
0 |
0 |
0 |
5/4 |
0 |
-1/4 |
0 |
0 |
|
x7 |
3/2 |
0 |
0 |
5/4 |
0 |
-1/4 |
0 |
1 |
0 |
0 |
-5/4 |
0 |
1/4 |
0 |
0 |
|
x2 |
1/2 |
0 |
1 |
1/4 |
0 |
-1/4 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
1/4 |
0 |
0 |
|
x9 |
7/2 |
0 |
0 |
-1/4 |
0 |
1/4 |
0 |
0 |
0 |
1 |
1/4 |
0 |
-1/4 |
0 |
0 |
|
F(X5) |
17 |
0 |
0 |
-9 |
0 |
2 |
0 |
0 |
0 |
0 |
9+M |
M |
-2+M |
M |
M |
Итерация №5.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (- , - , 1/2 : 1/4 , - , 11/2 : 11/4 , 1/2 : 1/4 , - ) = 11/5
Следовательно, 5-ая строка является ведущей.
Разрешающий элемент равен (11/4) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
min |
|
x4 |
8 |
0 |
0 |
-6 |
1 |
1 |
0 |
0 |
0 |
0 |
6 |
-1 |
-1 |
0 |
0 |
- |
|
x6 |
21/2 |
0 |
0 |
-11/4 |
0 |
1/4 |
1 |
0 |
0 |
0 |
11/4 |
0 |
-1/4 |
-1 |
0 |
- |
|
x8 |
1/2 |
0 |
0 |
1/4 |
0 |
-1/4 |
0 |
0 |
1 |
0 |
-1/4 |
0 |
1/4 |
0 |
-1 |
2 |
|
x1 |
21/2 |
1 |
0 |
-11/4 |
0 |
1/4 |
0 |
0 |
0 |
0 |
11/4 |
0 |
-1/4 |
0 |
0 |
- |
|
x7 |
11/2 |
0 |
0 |
11/4 |
0 |
-1/4 |
0 |
1 |
0 |
0 |
-11/4 |
0 |
1/4 |
0 |
0 |
11/5 |
|
x2 |
1/2 |
0 |
1 |
1/4 |
0 |
-1/4 |
0 |
0 |
0 |
0 |
-1/4 |
0 |
1/4 |
0 |
0 |
2 |
|
x9 |
31/2 |
0 |
0 |
-1/4 |
0 |
1/4 |
0 |
0 |
0 |
1 |
1/4 |
0 |
-1/4 |
0 |
0 |
- |
|
F(X6) |
17 |
0 |
0 |
-9 |
0 |
2 |
0 |
0 |
0 |
0 |
9+M |
M |
-2+M |
M |
M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x7 в план 6 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 6, получена в результате деления всех элементов строки x7 плана 5 на разрешающий элемент РЭ=11/4
На месте разрешающего элемента в плане 6 получаем 1.
В остальных клетках столбца x3 плана 6 записываем нули.
Таким образом, в новом плане 6 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 6, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
8-(11/2 * -6):11/4 |
0-(0 * -6):11/4 |
0-(0 * -6):11/4 |
-6-(11/4 * -6):11/4 |
1-(0 * -6):11/4 |
1-(-1/4 * -6):11/4 |
0-(0 * -6):11/4 |
0-(1 * -6):11/4 |
|
21/2-(11/2 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
-11/4-(11/4 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
1/4-(-1/4 * -11/4):11/4 |
1-(0 * -11/4):11/4 |
0-(1 * -11/4):11/4 |
|
1/2-(11/2 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
1/4-(11/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
-1/4-(-1/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
0-(1 * 1/4):11/4 |
|
21/2-(11/2 * -11/4):11/4 |
1-(0 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
-11/4-(11/4 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
1/4-(-1/4 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
0-(1 * -11/4):11/4 |
|
11/2 : 11/4 |
0 : 11/4 |
0 : 11/4 |
11/4 : 11/4 |
0 : 11/4 |
-1/4 : 11/4 |
0 : 11/4 |
1 : 11/4 |
|
1/2-(11/2 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
1-(0 * 1/4):11/4 |
1/4-(11/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
-1/4-(-1/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
0-(1 * 1/4):11/4 |
|
31/2-(11/2 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
-1/4-(11/4 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
1/4-(-1/4 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
0-(1 * -1/4):11/4 |
|
(M)-(11/2 * (-9)):11/4 |
(0)-(0 * (-9)):11/4 |
(0)-(0 * (-9)):11/4 |
(-9)-(11/4 * (-9)):11/4 |
(0)-(0 * (-9)):11/4 |
(2)-(-1/4 * (-9)):11/4 |
(0)-(0 * (-9)):11/4 |
(0)-(1 * (-9)):11/4 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
0-(0 * -6):11/4 |
0-(0 * -6):11/4 |
6-(-11/4 * -6):11/4 |
-1-(0 * -6):11/4 |
-1-(1/4 * -6):11/4 |
0-(0 * -6):11/4 |
0-(0 * -6):11/4 |
|
0-(0 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
11/4-(-11/4 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
-1/4-(1/4 * -11/4):11/4 |
-1-(0 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
|
1-(0 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
-1/4-(-11/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
1/4-(1/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
-1-(0 * 1/4):11/4 |
|
0-(0 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
11/4-(-11/4 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
-1/4-(1/4 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
0-(0 * -11/4):11/4 |
|
0 : 11/4 |
0 : 11/4 |
-11/4 : 11/4 |
0 : 11/4 |
1/4 : 11/4 |
0 : 11/4 |
0 : 11/4 |
|
0-(0 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
-1/4-(-11/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
1/4-(1/4 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
0-(0 * 1/4):11/4 |
|
0-(0 * -1/4):11/4 |
1-(0 * -1/4):11/4 |
1/4-(-11/4 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
-1/4-(1/4 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
0-(0 * -1/4):11/4 |
|
(0)-(0 * (-9)):11/4 |
(0)-(0 * (-9)):11/4 |
(9+M)-(-11/4 * (-9)):11/4 |
(M)-(0 * (-9)):11/4 |
(-2+M)-(1/4 * (-9)):11/4 |
(M)-(0 * (-9)):11/4 |
(M)-(0 * (-9)):11/4 |
Получаем новую симплекс-таблицу:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x4 |
76/5 |
0 |
0 |
0 |
1 |
-1/5 |
0 |
24/5 |
0 |
0 |
0 |
-1 |
1/5 |
0 |
0 |
|
x6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
x8 |
1/5 |
0 |
0 |
0 |
0 |
-1/5 |
0 |
-1/5 |
1 |
0 |
0 |
0 |
1/5 |
0 |
-1 |
|
x1 |
4 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x3 |
6/5 |
0 |
0 |
1 |
0 |
-1/5 |
0 |
4/5 |
0 |
0 |
-1 |
0 |
1/5 |
0 |
0 |
|
x2 |
1/5 |
0 |
1 |
0 |
0 |
-1/5 |
0 |
-1/5 |
0 |
0 |
0 |
0 |
1/5 |
0 |
0 |
|
x9 |
19/5 |
0 |
0 |
0 |
0 |
1/5 |
0 |
1/5 |
0 |
1 |
0 |
0 |
-1/5 |
0 |
0 |
|
F(X6) |
274/5 |
0 |
0 |
0 |
0 |
1/5 |
0 |
71/5 |
0 |
0 |
M |
M |
-1/5+M |
M |
M |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
x13 |
x14 |
|
x4 |
76/5 |
0 |
0 |
0 |
1 |
-1/5 |
0 |
24/5 |
0 |
0 |
0 |
-1 |
1/5 |
0 |
0 |
|
x6 |
4 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
x8 |
1/5 |
0 |
0 |
0 |
0 |
-1/5 |
0 |
-1/5 |
1 |
0 |
0 |
0 |
1/5 |
0 |
-1 |
|
x1 |
4 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
x3 |
6/5 |
0 |
0 |
1 |
0 |
-1/5 |
0 |
4/5 |
0 |
0 |
-1 |
0 |
1/5 |
0 |
0 |
|
x2 |
1/5 |
0 |
1 |
0 |
0 |
-1/5 |
0 |
-1/5 |
0 |
0 |
0 |
0 |
1/5 |
0 |
0 |
|
x9 |
19/5 |
0 |
0 |
0 |
0 |
1/5 |
0 |
1/5 |
0 |
1 |
0 |
0 |
-1/5 |
0 |
0 |
|
F(X7) |
274/5 |
0 |
0 |
0 |
0 |
1/5 |
0 |
71/5 |
0 |
0 |
M |
M |
-1/5+M |
M |
M |
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
x1 = 4
x2 = 1/5
F(X) = 7*4 -1*1/5 = 274/5
Построим двойственную задачу по следующим правилам.
1. Количество переменных в двойственной задаче равно количеству неравенств в исходной.
2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной.
3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи.
Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется.
Расширенная матрица A.
-1 |
-1 |
-3 |
|
-5 |
-1 |
-5 |
|
-1 |
-5 |
-5 |
|
-1 |
0 |
0 |
|
1 |
0 |
4 |
|
0 |
-1 |
0 |
|
0 |
1 |
4 |
|
7 |
-1 |
0 |
Транспонированная матрица AT.
-1 |
-5 |
-1 |
-1 |
1 |
0 |
0 |
7 |
|
-1 |
-1 |
-5 |
0 |
0 |
-1 |
1 |
-1 |
|
-3 |
-5 |
-5 |
0 |
4 |
0 |
4 |
0 |
Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной.
Неравенства, соединенные стрелочками (-), называются сопряженными.
- y1 - 5y2 - y3 - y4 + y5?7
- y1 - y2 - 5y3 - y6 + y7?-1
- 3y1 - 5y2 - 5y3 + 4y5 + 4y7 > min
y1 ? 0
y2 ? 0
y3 ? 0
y4 ? 0
y5 ? 0
y6 ? 0
y7 ? 0
Исходная задача I |
Двойственная задача II |
||
x1 ? 0 |
- |
- y1 - 5y2 - y3 - y4 + y5?7 |
|
x2 ? 0 |
- |
- y1 - y2 - 5y3 - y6 + y7?-1 |
|
7x1 - x2 > max |
- |
- 3y1 - 5y2 - 5y3 + 4y5 + 4y7 > min |
|
- x1 - x2?-3 |
- |
y1 ? 0 |
|
- 5x1 - x2?-5 |
- |
y2 ? 0 |
|
- x1 - 5x2?-5 |
- |
y3 ? 0 |
|
- x1?0 |
- |
y4 ? 0 |
|
x1?4 |
- |
y5 ? 0 |
|
- x2?0 |
- |
y6 ? 0 |
|
x2?4 |
- |
y7 ? 0 |
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.
A = (A4, A6, A8, A1, A3, A2, A9) =
0 |
0 |
0 |
1 |
-1 |
1 |
0 |
|
-1 |
0 |
0 |
5 |
0 |
1 |
0 |
|
0 |
0 |
0 |
1 |
0 |
5 |
0 |
|
0 |
-1 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
Определив обратную матрицу D = А-1 через алгебраические дополнения, получим:
А-1 =
0 |
-1 |
1/5 |
0 |
24/5 |
0 |
0 |
|
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
|
0 |
0 |
1/5 |
0 |
-1/5 |
-1 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
-1 |
0 |
1/5 |
0 |
4/5 |
0 |
0 |
|
0 |
0 |
1/5 |
0 |
-1/5 |
0 |
0 |
|
0 |
0 |
-1/5 |
0 |
1/5 |
0 |
1 |
Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных.
Тогда Y = C*A-1 =
(0, 0, 0, 7, 0, -1, 0) x
0 |
-1 |
1/5 |
0 |
24/5 |
0 |
0 |
|
0 |
0 |
0 |
-1 |
1 |
0 |
0 |
|
0 |
0 |
1/5 |
0 |
-1/5 |
-1 |
0 |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
-1 |
0 |
1/5 |
0 |
4/5 |
0 |
0 |
|
0 |
0 |
1/5 |
0 |
-1/5 |
0 |
0 |
|
0 |
0 |
-1/5 |
0 |
1/5 |
0 |
1 |
= (0;0;-1/5;0;36/5;0;0)
Оптимальный план двойственной задачи равен:
y1 = 0
y2 = 0
y3 = -1/5
y4 = 0
y5 = 71/5
y6 = 0
y7 = 0
Z(Y) = 3*0+5*0+5*(-1/5)+0*0+4*71/5+0*0+4*0 = 274/5
Критерий оптимальности полученного решения. Если существуют такие допустимые решения X и Y прямой и двойственной задач, для которых выполняется равенство целевых функций F(x) = Z(y), то эти решения X и Y являются оптимальными решениями прямой и двойственной задач соответственно.
Определение дефицитных и недефицитных (избыточных) ресурсов. Вторая теорема двойственности.
Подставим оптимальный план прямой задачи в систему ограниченной математической модели:
1*4 + 1*1/5 = 41/5 > 3
5*4 + 1*1/5 = 201/5 > 5
1*4 + 5*1/5 = 5 = 5
1*4 + 0*1/5 = 4 > 0
1*4 + 0*1/5 = 4 = 4
0*4 + 1*1/5 = 1/5 > 0
0*4 + 1*1/5 = 1/5 < 4
1-ое ограничение выполняется как строгое неравенство, т.е. ресурс 1-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y1 = 0.
Неиспользованный экономический резерв ресурса 1 составляет 11/5 (3-41/5).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y2 = 0.
Неиспользованный экономический резерв ресурса 2 составляет 151/5 (5-201/5).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
3-ое ограничение прямой задачи выполняется как равенство. Это означает, что 3-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y3 ? 0).
4-ое ограничение выполняется как строгое неравенство, т.е. ресурс 4-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y4 = 0.
Неиспользованный экономический резерв ресурса 4 составляет 4 (0-4).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
5-ое ограничение прямой задачи выполняется как равенство. Это означает, что 5-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y5 ? 0).
6-ое ограничение выполняется как строгое неравенство, т.е. ресурс 6-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y6 = 0.
Неиспользованный экономический резерв ресурса 6 составляет 1/5 (0-1/5).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
7-ое ограничение выполняется как строгое неравенство, т.е. ресурс 7-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y7 = 0.
Неиспользованный экономический резерв ресурса 7 составляет 34/5 (4-1/5).
Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).
Двойственные оценки отражают сравнительную дефицитность различных видов ресурсов в отношении принятого в задаче показателя эффективности. Оценки показывают, какие ресурсы являются более дефицитными, (они будут иметь самые высокие оценки), какие менее дефицитными и какие совсем недефицитны (избыточны) - они будут равны нулю.
Обоснование эффективности оптимального плана.
При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:
1*0 + 5*0 + 1*(-1/5) + 1*0 + 1*71/5 + 0*0 + 0*0 = 7 = 7
1*0 + 1*0 + 5*(-1/5) + 0*0 + 0*71/5 + 1*0 + 1*0 = -1 = -1
1-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый продукт экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).
2-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 2-ый продукт экономически выгодно производить, а его использование предусмотрено оптимальным планом прямой задачи (x2>0).
ВОПРОС № 2. ТРАНСПОРТНАЯ ЗАДАЧА
a. Сформулировать постановку задачи
b. Найти начальный опорный план методом «северо-западного угла, методом «минимального элемента», методом «двойного предпочтения»
c. Найти оптимальный план методом потенциалов
Сформулировать постановку задачи
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1 |
2 |
3 |
4 |
Запасы |
||
1 |
3 |
2 |
4 |
1 |
50 |
|
2 |
2 |
3 |
1 |
5 |
40 |
|
3 |
3 |
2 |
7 |
4 |
20 |
|
Потребности |
30 |
25 |
35 |
20 |
Проверим необходимое и достаточное условие разрешимости задачи.
?a = 50 + 40 + 20 = 110
?b = 30 + 25 + 35 + 20 = 110
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
4 |
Запасы |
||
1 |
3 |
2 |
4 |
1 |
50 |
|
2 |
2 |
3 |
1 |
5 |
40 |
|
3 |
3 |
2 |
7 |
4 |
20 |
|
Потребности |
30 |
25 |
35 |
20 |
Метод северо-западного угла
Этап I. Поиск первого опорного плана.
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
План начинается заполняться с верхнего левого угла.
Искомый элемент равен 3
Для этого элемента запасы равны 50, потребности 30. Поскольку минимальным является 30, то вычитаем его.
x11 = min(50,30) = 30.
3 |
2 |
4 |
1 |
50 - 30 = 20 |
|
x |
3 |
1 |
5 |
40 |
|
x |
2 |
7 |
4 |
20 |
|
30 - 30 = 0 |
25 |
35 |
20 |
0 |
Искомый элемент равен 2
Для этого элемента запасы равны 20, потребности 25. Поскольку минимальным является 20, то вычитаем его.
x12 = min(20,25) = 20.
3 |
2 |
x |
x |
20 - 20 = 0 |
|
x |
3 |
1 |
5 |
40 |
|
x |
2 |
7 |
4 |
20 |
|
0 |
25 - 20 = 5 |
35 |
20 |
0 |
Искомый элемент равен 3
Для этого элемента запасы равны 40, потребности 5. Поскольку минимальным является 5, то вычитаем его.
x22 = min(40,5) = 5.
3 |
2 |
x |
x |
0 |
|
x |
3 |
1 |
5 |
40 - 5 = 35 |
|
x |
x |
7 |
4 |
20 |
|
0 |
5 - 5 = 0 |
35 |
20 |
0 |
Искомый элемент равен 1
Для этого элемента запасы равны 35, потребности 35. Поскольку минимальным является 35, то вычитаем его.
x23 = min(35,35) = 35.
3 |
2 |
x |
x |
0 |
|
x |
3 |
1 |
x |
35 - 35 = 0 |
|
x |
x |
x |
4 |
20 |
|
0 |
0 |
35 - 35 = 0 |
20 |
0 |
Искомый элемент равен 4
Для этого элемента запасы равны 20, потребности 20. Поскольку минимальным является 20, то вычитаем его.
x34 = min(20,20) = 20.
3 |
2 |
x |
x |
0 |
|
x |
3 |
1 |
x |
0 |
|
x |
x |
x |
4 |
20 - 20 = 0 |
|
0 |
0 |
0 |
20 - 20 = 0 |
0 |
1 |
2 |
3 |
4 |
Запасы |
||
1 |
3[30] |
2[20] |
4 |
1 |
50 |
|
2 |
2 |
3[5] |
1[35] |
5 |
40 |
|
3 |
3 |
2 |
7 |
4[20] |
20 |
|
Потребности |
30 |
25 |
35 |
20 |
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 6. Следовательно, опорный план является вырожденным.
Подобные документы
Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.
контрольная работа [398,2 K], добавлен 15.08.2012Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.
курсовая работа [458,6 K], добавлен 10.12.2013Математическая теория оптимального принятия решений. Табличный симплекс-метод. Составление и решение двойственной задачи линейного программирования. Математическая модель транспортной задачи. Анализ целесообразности производства продукции на предприятии.
контрольная работа [467,8 K], добавлен 13.06.2012Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.
курсовая работа [54,1 K], добавлен 05.03.2010- Примеры использования графического и симплексного методов в решении задач линейного программирования
Экономико-математическая модель получения максимальной прибыли, её решение графическим методом. Алгоритм решения задачи линейного программирования симплекс-методом. Составление двойственной задачи и её графическое решение. Решение платёжной матрицы.
контрольная работа [367,5 K], добавлен 11.05.2014 Исследование задачи оптимизации ресурсов при планировании товарооборота торгового предприятия в общем виде. Формирование математической модели задачи. Решение симплекс-методом. Свободные члены системы ограничений и определение главных требований к ним.
курсовая работа [68,6 K], добавлен 21.06.2011Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.
реферат [193,4 K], добавлен 28.12.2008Решение задачи линейного программирования симплекс-методом. План перевозок при минимальных затратах на них. Определение оптимального значения изменения численности работников. Решение матричной игры двух лиц с применением чистой и смешанной стратегий.
контрольная работа [152,3 K], добавлен 16.05.2013Расчет задачи линейного программирования вручную симплекс методом и машинным способом в Ms Excel с применением электронной таблицы. Сравнение полученных результатов с ручным решением. Математическая модель двойственной задачи с пояснениями результатов.
контрольная работа [1,4 M], добавлен 31.03.2012Характеристика направлений перевозок и флота. Расчет нормативов работы судов на схемах движения. Составление математической модели задачи. Нахождение оптимального плана работы флота и оптимальных схем движения судов, построение симплекс таблицы.
курсовая работа [1,4 M], добавлен 24.10.2012