Автор работы: Пользователь скрыл имя, 28 Ноября 2013 в 22:03, контрольная работа
Задача № 1. Решить задачу графически и симплекс-методом.
Задача № 2. Цех выпускает три вида столярных изделий с использованием трёх видов сырья, расход которого на единицу каждого вида изделий приведён в таблице. Запасы сырья каждого вида на планируемый период составляют 200, 320 и 400 единиц соответственно. План выпуска изделий каждого вида за этот период составляет 10, 20, 15 единиц. Сколько единиц изделий каждого вида необходимо выпускать для получения максимальной прибыли и выполнения плана, если прибыль, получаемая от реализации одного изделия каждого вида, составляет 6 у.е., 12 у.е. и 15 у.е.
Из уравнений выражаем искусственные переменные:
x10 = 10-x1+x7
x11 = 20-x2+x8
x12 = 15-x3+x9
которые подставим в целевую функцию:
F(X) = 6x1 + 12x2 + 15x3 - M(10-x1+x7) - M(20-x2+x8) - M(15-x3+x9) → max
или
F(X) = (6+M)x1+(12+M)x2+(15+M)x3+(-M)
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
5 |
2 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
6 |
8 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
5 |
10 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Экономический смысл дополнительных переменных: дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.
Решим систему уравнений относительно базисных переменных:
x4, x5, x6, x10, x11, x12,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,200,320,400,0,0,0,10,
Базисное решение называется допустимым, если оно неотрицательно.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x4 |
200 |
5 |
2 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
x5 |
320 |
1 |
6 |
8 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
x6 |
400 |
4 |
5 |
10 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
x10 |
10 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
x11 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
x12 |
15 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
F(X0) |
-45M |
-6-M |
-12-M |
-15-M |
0 |
0 |
0 |
M |
M |
M |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (200 : 3 , 320 : 8 , 400 : 10 , - , - , 15 : 1 ) = 15
Следовательно, 6-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
min |
x4 |
200 |
5 |
2 |
3 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
662/3 |
|
x5 |
320 |
1 |
6 |
8 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
40 |
x6 |
400 |
4 |
5 |
10 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
40 |
x10 |
10 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
- |
x11 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
- |
x12 |
15 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
15 |
F(X1) |
-45M |
-6-M |
-12-M |
-15-M |
0 |
0 |
0 |
M |
M |
M |
0 |
0 |
0 |
0 |
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x12 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x12 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x3 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Получаем новую симплекс-
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
|
x4 |
155 |
5 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
-3 |
x5 |
200 |
1 |
6 |
0 |
0 |
1 |
0 |
0 |
0 |
8 |
0 |
0 |
-8 |
x6 |
250 |
4 |
5 |
0 |
0 |
0 |
1 |
0 |
0 |
10 |
0 |
0 |
-10 |
x10 |
10 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
x11 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
x3 |
15 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
F(X1) |
225-30M |
-6-M |
-12-M |
0 |
0 |
0 |
0 |
M |
M |
-15 |
0 |
0 |
15+M |
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален,
так как в индексной строке
находятся отрицательные
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (155 : 2 , 200 : 6 , 250 : 5 , - , 20 : 1 , - ) = 20
Следовательно, 5-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
x11 |
x12 |
min |
x4 |
155 |
5 |
2 |
0 |
1 |
0 |
0 |
0 |
0 |
3 |
0 |
0 |
-3 |
771/2 |
|
x5 |
200 |
1 |
6 |
0 |
0 |
1 |
0 |
0 |
0 |
8 |
0 |
0 |
-8 |
331/3 |
|
x6 |
250 |
4 |
5 |
0 |
0 |
0 |
1 |
0 |
0 |
10 |
0 |
0 |
-10 |
50 |
x10 |
10 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
0 |
- |
x11 |
20 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
0 |
20 |
x3 |
15 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
1 |
- |
F(X2) |
225-30M |
-6-M |
-12-M |
0 |
0 |
0 |
0 |
M |
M |
-15 |
0 |
0 |
15+M |
0 |
Информация о работе Контрольная работа по "Методам оптимальных решений"