Автор работы: Пользователь скрыл имя, 28 Ноября 2013 в 22:03, контрольная работа
Задача № 1. Решить задачу графически и симплекс-методом.
Задача № 2. Цех выпускает три вида столярных изделий с использованием трёх видов сырья, расход которого на единицу каждого вида изделий приведён в таблице. Запасы сырья каждого вида на планируемый период составляют 200, 320 и 400 единиц соответственно. План выпуска изделий каждого вида за этот период составляет 10, 20, 15 единиц. Сколько единиц изделий каждого вида необходимо выпускать для получения максимальной прибыли и выполнения плана, если прибыль, получаемая от реализации одного изделия каждого вида, составляет 6 у.е., 12 у.е. и 15 у.е.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x7, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai7
и из них выберем наименьшее:
min (383/4 : 45/8 , 83/4 : 1/8 , 221/2 : 23/4 , - , - , 233/4 : 1/8 ) = 82/11
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (23/4) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
min |
x4 |
383/4 |
0 |
0 |
0 |
1 |
-3/8 |
0 |
45/8 |
-1/4 |
0 |
-45/8 |
1/4 |
0 |
814/37 |
|
x9 |
83/4 |
0 |
0 |
0 |
0 |
1/8 |
0 |
1/8 |
3/4 |
1 |
-1/8 |
-3/4 |
-1 |
70 |
x6 |
221/2 |
0 |
0 |
0 |
0 |
-11/4 |
1 |
23/4 |
-21/2 |
0 |
-23/4 |
21/2 |
0 |
82/11 |
|
x1 |
10 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
- |
x2 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
- |
x3 |
233/4 |
0 |
0 |
1 |
0 |
1/8 |
0 |
1/8 |
3/4 |
0 |
-1/8 |
-3/4 |
0 |
190 |
F(X5) |
6561/4 |
0 |
0 |
0 |
0 |
17/8 |
0 |
-41/8 |
-3/4 |
0 |
41/8+M |
3/4+M |
M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x6 в план 5 войдет переменная x7.
Строка, соответствующая переменной x7 в плане 5, получена в результате деления всех элементов строки x6 плана 4 на разрешающий элемент РЭ=23/4
На месте разрешающего элемента в плане 5 получаем 1.
В остальных клетках столбца x7 плана 5 записываем нули.
Таким образом, в новом плане 5 заполнены строка x7 и столбец x7.
Все остальные элементы нового плана 5, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x4 |
10/11 |
0 |
0 |
0 |
1 |
18/11 |
-115/22 |
0 |
321/22 |
0 |
0 |
-321/22 |
0 |
x9 |
78/11 |
0 |
0 |
0 |
0 |
2/11 |
-1/22 |
0 |
19/22 |
1 |
0 |
-19/22 |
-1 |
x7 |
82/11 |
0 |
0 |
0 |
0 |
-5/11 |
4/11 |
1 |
-10/11 |
0 |
-1 |
10/11 |
0 |
x1 |
182/11 |
1 |
0 |
0 |
0 |
-5/11 |
4/11 |
0 |
-10/11 |
0 |
0 |
10/11 |
0 |
x2 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
x3 |
228/11 |
0 |
0 |
1 |
0 |
2/11 |
-1/22 |
0 |
19/22 |
0 |
0 |
-19/22 |
0 |
F(X5) |
690 |
0 |
0 |
0 |
0 |
0 |
11/2 |
0 |
-41/2 |
0 |
M |
41/2+M |
M |
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x8, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai8
и из них выберем наименьшее:
min (10/11 : 321/22 , 78/11 : 19/22 , - , - , - , 228/11 : 19/22 ) = 20/87
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (321/22) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
min |
x4 |
10/11 |
0 |
0 |
0 |
1 |
18/11 |
-115/22 |
0 |
321/22 |
0 |
0 |
-321/22 |
0 |
20/87 |
|
x9 |
78/11 |
0 |
0 |
0 |
0 |
2/11 |
-1/22 |
0 |
19/22 |
1 |
0 |
-19/22 |
-1 |
818/19 |
|
x7 |
82/11 |
0 |
0 |
0 |
0 |
-5/11 |
4/11 |
1 |
-10/11 |
0 |
-1 |
10/11 |
0 |
- |
x1 |
182/11 |
1 |
0 |
0 |
0 |
-5/11 |
4/11 |
0 |
-10/11 |
0 |
0 |
10/11 |
0 |
- |
x2 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
- |
x3 |
228/11 |
0 |
0 |
1 |
0 |
2/11 |
-1/22 |
0 |
19/22 |
0 |
0 |
-19/22 |
0 |
266/19 |
|
F(X6) |
690 |
0 |
0 |
0 |
0 |
0 |
11/2 |
0 |
-41/2 |
0 |
M |
41/2+M |
M |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 6 войдет переменная x8.
Строка, соответствующая переменной x8 в плане 6, получена в результате деления всех элементов строки x4 плана 5 на разрешающий элемент РЭ=321/22
На месте разрешающего элемента в плане 6 получаем 1.
В остальных клетках столбца x8 плана 6 записываем нули.
Таким образом, в новом плане 6 заполнены строка x8 и столбец x8.
Все остальные элементы нового плана 6, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x8 |
20/87 |
0 |
0 |
0 |
22/87 |
38/87 |
-37/87 |
0 |
1 |
0 |
0 |
-1 |
0 |
x9 |
746/87 |
0 |
0 |
0 |
-19/87 |
-17/87 |
28/87 |
0 |
0 |
1 |
0 |
0 |
-1 |
x7 |
834/87 |
0 |
0 |
0 |
20/87 |
-5/87 |
-2/87 |
1 |
0 |
0 |
-1 |
0 |
0 |
x1 |
1834/87 |
1 |
0 |
0 |
20/87 |
-5/87 |
-2/87 |
0 |
0 |
0 |
0 |
0 |
0 |
x2 |
2020/87 |
0 |
1 |
0 |
22/87 |
38/87 |
-37/87 |
0 |
0 |
0 |
0 |
0 |
0 |
x3 |
2246/87 |
0 |
0 |
1 |
-19/87 |
-17/87 |
28/87 |
0 |
0 |
0 |
0 |
0 |
0 |
F(X6) |
6911/29 |
0 |
0 |
0 |
14/29 |
128/29 |
-12/29 |
0 |
0 |
0 |
M |
M |
M |
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x6, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai6
и из них выберем наименьшее:
min (- , 746/87 : 28/87 , - , - , - , 2246/87 : 28/87 ) = 2311/28
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (28/87) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
min |
x8 |
20/87 |
0 |
0 |
0 |
22/87 |
38/87 |
-37/87 |
0 |
1 |
0 |
0 |
-1 |
0 |
- |
x9 |
746/87 |
0 |
0 |
0 |
-19/87 |
-17/87 |
28/87 |
0 |
0 |
1 |
0 |
0 |
-1 |
2311/28 |
|
x7 |
834/87 |
0 |
0 |
0 |
20/87 |
-5/87 |
-2/87 |
1 |
0 |
0 |
-1 |
0 |
0 |
- |
x1 |
1834/87 |
1 |
0 |
0 |
20/87 |
-5/87 |
-2/87 |
0 |
0 |
0 |
0 |
0 |
0 |
- |
x2 |
2020/87 |
0 |
1 |
0 |
22/87 |
38/87 |
-37/87 |
0 |
0 |
0 |
0 |
0 |
0 |
- |
x3 |
2246/87 |
0 |
0 |
1 |
-19/87 |
-17/87 |
28/87 |
0 |
0 |
0 |
0 |
0 |
0 |
70 |
F(X7) |
6911/29 |
0 |
0 |
0 |
14/29 |
128/29 |
-12/29 |
0 |
0 |
0 |
M |
M |
M |
0 |
Информация о работе Контрольная работа по "Методам оптимальных решений"