Автор работы: Пользователь скрыл имя, 22 Мая 2013 в 14:34, контрольная работа
Проанализируем решение задачи с помощью свойств двойственных оценок:
1. Наибольшее изменение выручки произойдет, если изменить объем третьего ресурса ( ), а изменение второго ресурса не приведет к изменению целевой функции ( ).
2. Оценки положительны. Это означает, что при реализации оптимального плана соответствующие ресурсы расходуются полностью. Т.к. , это означает, что в оптимальном решении второй ресурс расходуется не полностью.
Задача №2 …………………………………………………………………… 4
Задача №3 ………………………………………………………………….. 5
Задача №4 ………………………………………………………………….. 8
Задача №5 …………………………………………………………………… 12
Задача №6 …………………………………………………………………. 15
Задача №7 …………………………………………………………………... 17
Содержание:
Задача №1 |
………………………………………………………………….. |
3 |
Задача №2 |
…………………………………………………………………… |
4 |
Задача №3 |
………………………………………………………………….. |
5 |
Задача №4 |
………………………………………………………………….. |
8 |
Задача №5 |
…………………………………………………………………… |
12 |
Задача №6 |
…………………………………………………………………. |
15 |
Задача №7 |
…………………………………………………………………... |
17 |
Задача № 1.
Если одна из пары двойственных задач имеет оптимальный план, то и другая имеет оптимальный план и значение целевых функций задач равны между собой.
Задача № 2.
Найти два опорных решения системы уравнений
В системе - базисные переменные, а остальные – свободные. Исходное опорное решение: , или
Чтобы найти следующее опорное решение, выполним одно преобразование однократного замещения.
Составим таблицу Гаусса:
Базис |
||||||||
|
|
7 |
1 |
3 |
-1 |
0 |
2 |
0 |
- |
2 |
0 |
-2 |
4 |
1 |
0 |
0 |
2/4=0,5 min | |
10 |
0 |
-4 |
3 |
0 |
8 |
1 |
10/3=3,3 | |
15/2 |
1 |
5/2 |
0 |
1/4 |
2 |
0 |
||
1/2 |
0 |
-1/2 |
1 |
1/4 |
0 |
0 |
||
17/2 |
0 |
-5/2 |
0 |
-3/4 |
8 |
1 |
Т.о., второе опорное решение: .
Задача № 3.
Шаг 0 |
||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x4 |
6 |
2 |
0 |
3 |
1 |
0 |
x2 |
4 |
0 |
1 |
-1 |
0 |
0 |
x5 |
2 |
3 |
0 |
1 |
0 |
1 |
ИС |
4 |
-2 |
0 |
-2 |
0 |
0 |
Шаг 1 |
||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x4 |
14/3 |
0 |
0 |
7/3 |
1 |
-2/3 |
x2 |
4 |
0 |
1 |
-1 |
0 |
0 |
x1 |
2/3 |
1 |
0 |
1/3 |
0 |
1/3 |
ИС |
16/3 |
0 |
0 |
-4/3 |
0 |
2/3 |
Шаг 2 |
||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x3 |
2 |
0 |
0 |
1 |
3/7 |
-2/7 |
x2 |
6 |
0 |
1 |
0 |
3/7 |
-2/7 |
x1 |
0 |
1 |
0 |
0 |
-1/7 |
3/7 |
ИС |
8 |
0 |
0 |
0 |
4/7 |
2/7 |
Составим к данной задаче двойственную:
|
Шаг 0 |
||||||||||||||
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
z1 |
2 |
2 |
0 |
3 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
z2 |
1 |
0 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
z3 |
1 |
3 |
-1 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
z4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
z5 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
ИС |
-4M |
-6M+6 |
4 |
-5M+2 |
M |
M |
M |
M |
M |
0 |
0 |
0 |
0 |
0 |
Шаг 1 |
||||||||||||||
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
z1 |
2 |
0 |
0 |
3 |
-1 |
0 |
0 |
2 |
0 |
1 |
0 |
0 |
-2 |
0 |
z2 |
1 |
0 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
z3 |
1 |
0 |
-1 |
1 |
0 |
0 |
-1 |
3 |
0 |
0 |
0 |
1 |
-3 |
0 |
y1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
z5 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
ИС |
-4M |
0 |
4 |
-5M+2 |
M |
M |
M |
-5M+6 |
M |
0 |
0 |
0 |
6M-6 |
0 |
Шаг 2 |
||||||||||||||
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
z1 |
2 |
0 |
0 |
0 |
-1 |
0 |
0 |
2 |
3 |
1 |
0 |
0 |
-2 |
-3 |
z2 |
1 |
0 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
z3 |
1 |
0 |
-1 |
0 |
0 |
0 |
-1 |
3 |
1 |
0 |
0 |
1 |
-3 |
-1 |
y1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
y3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
ИС |
-4M |
0 |
4 |
0 |
M |
M |
M |
-5M+6 |
-4M+2 |
0 |
0 |
0 |
6M-6 |
5M-2 |
Шаг 3 |
||||||||||||||
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
z1 |
4/3 |
0 |
2/3 |
0 |
-1 |
0 |
2/3 |
0 |
7/3 |
1 |
0 |
-2/3 |
0 |
-7/3 |
z2 |
1 |
0 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
y7 |
1/3 |
0 |
-1/3 |
0 |
0 |
0 |
-1/3 |
1 |
1/3 |
0 |
0 |
1/3 |
-1 |
-1/3 |
y1 |
1/3 |
1 |
-1/3 |
0 |
0 |
0 |
-1/3 |
0 |
1/3 |
0 |
0 |
1/3 |
0 |
-1/3 |
y3 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
ИС |
-7/3M-2 |
0 |
-5/3M+6 |
0 |
M |
M |
-2/3M+2 |
0 |
-7/3M |
0 |
0 |
5/3M-2 |
M |
10/3M |
Шаг 4 |
||||||||||||||
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
y8 |
4/7 |
0 |
2/7 |
0 |
-3/7 |
0 |
2/7 |
0 |
1 |
3/7 |
0 |
-2/7 |
0 |
-1 |
z2 |
1 |
0 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
y7 |
1/7 |
0 |
-3/7 |
0 |
1/7 |
0 |
-3/7 |
1 |
0 |
-1/7 |
0 |
3/7 |
-1 |
0 |
y1 |
1/7 |
1 |
-3/7 |
0 |
1/7 |
0 |
-3/7 |
0 |
0 |
-1/7 |
0 |
3/7 |
0 |
0 |
y3 |
4/7 |
0 |
2/7 |
1 |
-3/7 |
0 |
2/7 |
0 |
0 |
3/7 |
0 |
-2/7 |
0 |
0 |
ИС |
-M-2 |
0 |
-M+6 |
0 |
0 |
M |
2 |
0 |
0 |
M |
0 |
M-2 |
M |
M |
Шаг 5 |
||||||||||||||
Базис |
БП |
y 1 |
y 2 |
y 3 |
y 4 |
y 5 |
y 6 |
y 7 |
y 8 |
z 1 |
z 2 |
z 3 |
z 4 |
z 5 |
y8 |
2/7 |
0 |
0 |
0 |
-3/7 |
2/7 |
2/7 |
0 |
1 |
3/7 |
-2/7 |
-2/7 |
0 |
-1 |
y2 |
1 |
0 |
1 |
0 |
0 |
-1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
y7 |
4/7 |
0 |
0 |
0 |
1/7 |
-3/7 |
-3/7 |
1 |
0 |
-1/7 |
3/7 |
3/7 |
-1 |
0 |
y1 |
4/7 |
1 |
0 |
0 |
1/7 |
-3/7 |
-3/7 |
0 |
0 |
-1/7 |
3/7 |
3/7 |
0 |
0 |
y3 |
2/7 |
0 |
0 |
1 |
-3/7 |
2/7 |
2/7 |
0 |
0 |
3/7 |
-2/7 |
-2/7 |
0 |
0 |
ИС |
-8 |
0 |
0 |
0 |
0 |
6 |
2 |
0 |
0 |
M |
M-6 |
M-2 |
M |
M |
Оптимальный план двойственной задачи: имеется бесконечное множество оптимальних планов,
Задача № 4.
А)Составим математическую модель задачи.
Пусть - соответствующие объемы выпускаемой продукции. Тогда выручка от реализации продукции
Достигает максимума при таких значениях , которые удовлетворяют условиям ограниченности расхода ресурсов:
Двойственная задача:
Б) Запишем решение исходной задачи.
Шаг 0 |
|||||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
x 8 |
x5 |
250 |
1 |
6 |
0 |
2 |
1 |
0 |
0 |
0 |
x6 |
300 |
3 |
2 |
3 |
4 |
0 |
1 |
0 |
0 |
x7 |
240 |
1 |
0 |
5 |
1 |
0 |
0 |
1 |
0 |
x8 |
350 |
4 |
5 |
2 |
3 |
0 |
0 |
0 |
1 |
ИС |
0 |
-3 |
-5 |
-7 |
-3 |
0 |
0 |
0 |
0 |
Шаг 1 |
|||||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
x 8 |
x5 |
250 |
1 |
6 |
0 |
2 |
1 |
0 |
0 |
0 |
x6 |
156 |
12/5 |
2 |
0 |
17/5 |
0 |
1 |
-3/5 |
0 |
x3 |
48 |
1/5 |
0 |
1 |
1/5 |
0 |
0 |
1/5 |
0 |
x8 |
254 |
18/5 |
5 |
0 |
13/5 |
0 |
0 |
-2/5 |
1 |
ИС |
336 |
-8/5 |
-5 |
0 |
-8/5 |
0 |
0 |
7/5 |
0 |
Шаг 2 |
|||||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
x 8 |
x2 |
125/3 |
1/6 |
1 |
0 |
1/3 |
1/6 |
0 |
0 |
0 |
x6 |
218/3 |
31/15 |
0 |
0 |
41/15 |
-1/3 |
1 |
-3/5 |
0 |
x3 |
48 |
1/5 |
0 |
1 |
1/5 |
0 |
0 |
1/5 |
0 |
x8 |
137/3 |
83/30 |
0 |
0 |
14/15 |
-5/6 |
0 |
-2/5 |
1 |
ИС |
1633/3 |
-23/30 |
0 |
0 |
1/15 |
5/6 |
0 |
7/5 |
0 |
Шаг 3 |
|||||||||
Базис |
БП |
x 1 |
x 2 |
x 3 |
x 4 |
x 5 |
x 6 |
x 7 |
x 8 |
x2 |
3230/83 |
0 |
1 |
0 |
23/83 |
18/83 |
0 |
2/83 |
-5/83 |
x6 |
3200/83 |
0 |
0 |
0 |
169/83 |
24/83 |
1 |
-25/83 |
-62/83 |
x3 |
3710/83 |
0 |
0 |
1 |
11/83 |
5/83 |
0 |
19/83 |
-6/83 |
x1 |
1370/83 |
1 |
0 |
0 |
28/83 |
-25/83 |
0 |
-12/83 |
30/83 |
ИС |
46230/83 |
0 |
0 |
0 |
27/83 |
50/83 |
0 |
107/83 |
23/83 |
Отчет о решении исходной и двойственной задач с помощью ППП QM for Windows по модулюLinear Programming имеет следующий вид:
В последнем столбце этого отчета указаны значения переменных в оптимальном решении: , а также значение целевой функции 556,988.
В)Оптимальное решение двойственной задачи будет
Г) проанализируем решение задачи с помощью свойств двойственных оценок:
Д) При продаже 100 единиц 3-го ресурса его количество станет равным 140. При этом .
Следовательно, , т.е. целевая функция в оптимальном плане уменьшится на 128,92.
Задача № 5.
Решим задачу с помощью ППП QMforWindowsпомодулю Transportation
(untitled) Solution | |||||
Destination 1 |
Destination 2 |
Destination 3 |
Destination 4 |
Destination 5 | |
Iteration 1 |
|||||
Source 1 |
(7) |
10 |
(7) |
200 |
(-2) |
Source 2 |
180 |
(-4) |
20 |
(-4) |
(-7) |
Source 3 |
(7) |
50 |
150 |
(-1) |
(-6) |
Source 4 |
(10) |
90 |
(7) |
(5) |
200 |
Dummy |
30 |
(-9) |
(-3) |
(-8) |
(-8) |
Iteration 2 |
|||||
Source 1 |
(-2) |
10 |
(7) |
200 |
(-2) |
Source 2 |
200 |
(5) |
(9) |
(5) |
(2) |
Source 3 |
(-2) |
30 |
170 |
(-1) |
(-6) |
Source 4 |
(1) |
90 |
(7) |
(5) |
200 |
Dummy |
10 |
20 |
(6) |
(1) |
(1) |
Iteration 3 |
|||||
Source 1 |
(-2) |
10 |
(1) |
200 |
(-2) |
Source 2 |
200 |
(5) |
(3) |
(5) |
(2) |
Source 3 |
(4) |
(6) |
170 |
(5) |
30 |
Source 4 |
(1) |
120 |
(1) |
(5) |
170 |
Dummy |
10 |
20 |
(0) |
(1) |
(1) |
Iteration 4 |
|||||
Source 1 |
10 |
(0) |
(1) |
200 |
(-2) |
Source 2 |
200 |
(3) |
(1) |
(3) |
(0) |
Source 3 |
(6) |
(6) |
170 |
(5) |
30 |
Source 4 |
(3) |
120 |
(1) |
(5) |
170 |
Dummy |
(2) |
30 |
(0) |
(1) |
(1) |
Iteration 5 |
|||||
Source 1 |
10 |
(2) |
(3) |
200 |
(0) |
Source 2 |
200 |
(5) |
(3) |
(3) |
(2) |
Source 3 |
(4) |
(6) |
170 |
(3) |
30 |
Source 4 |
(1) |
120 |
(1) |
(3) |
170 |
Dummy |
(0) |
30 |
(0) |
(-1) |
(1) |
Iteration 6 |
|||||
Source 1 |
10 |
(2) |
(3) |
170 |
30 |
Source 2 |
200 |
(5) |
(3) |
(3) |
(2) |
Source 3 |
(4) |
(6) |
170 |
(3) |
30 |
Source 4 |
(1) |
150 |
(1) |
(3) |
140 |
Dummy |
(1) |
(1) |
(1) |
30 |
(2) |
Created by POM-QM for Windows
Задача № 6.
По сетевому графику вычислить ранний и поздний сроки свершения событий, определить критический путь и его длину, найти свободный и полный резерв времени работ.
Определим ранние сроки наступления событий:
Теперь выполним расчеты в обратном направлении и найдем поздние сроки наступления событий:
Рассчитаем резервы времени события:
Критическими событиями (не имеющими резервов) являются 1, 2, 4, 6, 7. Они составляют критический путь. Продолжительность критического пути равна 80.
Найдем временные характеристики работ:
Некритические работы |
Продолжительность |
Общий резерв |
Свободный резерв |
1-3 |
15 |
27-0-15=12 |
15-0-15=0 |
1-4 |
25 |
39-0-25=14 |
39-0-25=14 |
3-4 |
12 |
39-27-12=0 |
39-15-12=2 |
3-6 |
29 |
60-27-29=4 |
60-15-29=16 |
2-5 |
27 |
63-20-27=16 |
53-20-27=6 |
5-7 |
17 |
80-63-17=0 |
80-53-17=10 |
Задача № 7.
Построим область решений системы неравенств и целевую функцию:
Область допустимых решений данной задачи – многоугольник ОАВС.
Линии уровня функции представляют собой семейство окружностей с центром в точке (3; 2) и радиусом .
В любой точке этой линии уровня при перемещении от центра окружности функция Zвозрастает, а при перемещении к центру – убывает. Таким образом, .
Информация о работе Контрольная работа по "Методам оптимальных решений"