Контрольная работа - Моделирование задач. Линейное программирование
Подождите немного. Документ загружается.
Факультет дистанционного образования
Томский государственный университет систем управления и
радиоэлектроники (ТУСУР)
Кафедра автоматизации обработки информации (АОИ)
Контрольная работа №1
По дисциплине «Системный анализ и исследование операций»
Учебное пособие Л.П. Турунтаева «Системный анализ и исследование операций»
Вариант № 9
Задание 1.1. Моделирование задач исследования операций.
В данном задании необходимо ввести управляемую переменную,
записать математическую модель задачи в общем виде с указанием
физического смысла переменных, целевой функции и ограничений.
Условия задачи:
На приобретение оборудования для нового производственного
участка выделено A тыс. руб. Его предполагается разместить на площади S
кв. м. Участок может быть оснащен машинами пяти типов. Машина i-го
типа стоит
i
R
тыс. руб., занимает площадь Q кв. м и производит
i
P
единиц
продукции в смену. Определить, какое количество машин каждого типа
необходимо закупить, чтобы обеспечить максимальную производительность
участка.
Решение:
Управляемая переменная. Так как нужно определить какое
количество машин каждого типа нужно для обеспечения максимальной
производительности, необходимо ввести переменную:
1
x
– необходимое количество машин каждого типа.
Целевая функция.
Производительность каждого типа машин составит
1
xP
i
.
Обозначив общую производительность через Z, можно дать
следующую математическую формулировку целевой функции: определить
(допустимые) значения
1
x
, максимизирующие величину общей
производительности
1
5
1
max xPZ
i
i
.
Ограничения. При решении рассматриваемой задачи должны быть
учтены ограничения на расход ресурсов.
Каждая машина i-го типа стоит
i
R
тыс. руб., тогда на машины в
количестве
1
x
шт. потребуется
ii
xR
тыс.руб. Всего на приобретение машин
потребуется
5
1i
ii
xR
тыс.руб. и расходы не должны превышать A тыс. руб.
Тогда ограничение на расходы можно записать в виде
AxR
i
ii
5
1
.
Также каждая машина i-го типа занимает площадь Q кв. м. Общая
площадь, занимаемая машинами:
5
1i
i
Qx
. И общая площадь не должна
превышать S. Ограничение на занимаемую площадь можно записать как
SQx
i
i
5
1
.
На переменную задачи
1
x
должны быть наложены условия
неотрицательности и неделимости, т.е. необходимо ввести ограничения
0
1
x
,
1
x
- целое.
Математическую модель задачи можно записать следующим образом:
определить количество
1
x
машин каждого типа, при котором достигается
5544332211
max xPxPxPxPxPZ
(целевая функция)
при
целое -
0
1
1
54321
5544332211
x
x
SQxQxQxQxQx
AxRxRxRxRxR
(о
граничения),
или
1
5
1
max xPZ
i
i
при
AxR
i
ii
5
1
,
SQx
i
i
5
1
.
0
i
x
,
i
x
– целое,
5,4,3,2,1i
.
Задание 1.2. Решение задач линейного программирования общего
вида.
В данном задании необходимо решить исходную задачу ЛП
графическим способом, затем от исходной ЗЛП перейти к двойственной,
решить ее симплекс-методом и по решению двойственной задачи найти
решение исходной.
Условия задачи:
min32
21
xx
(1.2.1)
165
21
xx
(1.2.2)
1223
21
xx
(1.2.3)
8
21
xx
(1.2.4)
1
1
x
(1.2.5)
Решение:
Построим множество допустимых решений
задачи. Данное
множество
образуется в результате пересечения полуплоскостей
(ограничений). Области, в которых выполняются соответствующие
ограничения в виде неравенств, указываются штрихами, направленными в
сторону допустимых значений переменных (рис. 1.2.1).
Рис. 1.2.1
Обозначим границы области многоугольника решений. На рисунке
1.2.2 область допустимых значений неограниченна.
Рис. 1.2.2.
Построим вектор-градиент
,C
составленный из производных целевой
функции по переменным задачи, который указывает направление
возрастания целевой функции по этим переменным.
).3,2(),(
21
CCC
Начало этого вектора лежит в точке с координатами (0, 0), а конец – в точке
(2,3). Рассмотрим целевую функцию задачи F = 2x
1
+3x
2
→ min. Построим
прямую, отвечающую значению функции F = 0: F = 2x
1
+3x
2
= 0. Будем
двигать эту прямую параллельным образом. Поскольку нас интересует
минимальное решение, поэтому двигаем прямую до первого касания
обозначенной области. На рисунке 1.2.3 эта прямая обозначена пунктирной
линией красного цвета.
Рис. 1.2.3.
На рисунке 1.2.3 видно, что оптимальному решению соответствует
точка
),(
21
xxX
. Так как точка
X
является точкой пересечения прямых
(1.2.2) и (1.2.4), значения
1
x
и
2
x
определяются решением системы двух
уравнений:
.8
;165
21
21
xx
xx
Решая полученную систему при помощи MathCAD, получаем
6
1
x
и
2
2
x
.
Перейдем к двойственной задаче:
Прямая ЗЛП Двойственная ЗЛП
min32)(
21
xxXZ
maxy81216)(
4321
yyyYf
165
21
xx
1
y
23
4321
yyyy
1223
21
xx
2
y
325
321
yyy
8
21
xx
3
y
0,,,
4321
yyyy
1
1
x
4
y
В канонической форме ЗЛП примет вид:
0,,,,,
,325
,23
,000y81216)(
654321
6321
54321
654321
yyyyyy
yyyy
yyyyy
yyyyyYf
Решим задачу прямым симплекс методом.
Итерация 0.
Заносим данные задачи в симплекс-таблицу:
Базис
1
y
2
y
3
y
4
y
5
y
6
y
Значение
5
y
1 3 1 1 1 0 2
6
y
[5] 2 1 0 0 1 3
f -16 -12 -8 -1 0 0 0
Опорный план Y
0
=(0,0,0,0,2,3). Текущий опорный план не является
оптимальным, т.к. значения
65
, yy
– положительные, коэффициенты в
целевой f со знаком минус.
Итерация 1.
В базис включаем переменную
1
y
, так как коэффициент при ней
отрицательный и имеет наибольшее по модулю значение. Исключаем из
базиса ту переменную, которой соответствует наименьшее отношение
5
3
}3/5 ;1/2min{:/
1
ii
ab
, т.е. исключаем
6
y
. Элемент [5] – ведущий.
Базис
1
y
2
y
3
y
4
y
5
y
6
y
Значение
5
y
0 [13/5] 4/5 1 1 -1/5 7/5
1
y
1 2/5 1/5 0 0 1/5 3/5
f 0 -28/5 -24/5 -1 0 16/5 48/5
Опорный план Y
1
=(3/5,0,0,0,7/5,0). Текущий опорный план не является
оптимальным, т.к. значение
5
y
– положительное, коэффициенты в целевой f
со знаком минус.
Итерация 2.
В базис включаем переменную
2
y
, так как коэффициент при ней
отрицательный и имеет наибольшее по модулю значение. Исключаем из
базиса ту переменную, которой соответствует наименьшее отношение
13
7
5
2
/
5
3
;
5
13
/
5
7
min:/
2
ii
ab
, т.е. исключаем
5
y
. Элемент [13/5] – ведущий.
Базис
1
y
2
y
3
y
4
y
5
y
6
y
Значение
2
y
0 1 [4/13] 5/13 5/13 -1/13 7/13
1
y
1 0 1/13 -2/13 -2/13 3/13 5/13
f 0 0 -40/13 15/13 28/13 36/13 164/13
Опорный план Y
2
=(5/13,7/13,0,0,0,0). Текущий опорный план не
является оптимальным, т.к. в целевой f присутствуют коэффициенты со
знаком минус.
Итерация 3.
В базис включаем переменную
3
y
, так как коэффициент при ней
отрицательный. Исключаем из базиса ту переменную, которой соответствует
наименьшее отношение
4
7
13
1
/
13
5
;
13
4
/
13
7
min:/
3
ii
ab
, т.е. исключаем
2
y
.
Элемент [4/13] – ведущий.
Базис
1
y
2
y
3
y
4
y
5
y
6
y
Значение
3
y
0 13/4 1 5/4 5/4 -1/4 7/4
1
y
1 -1/4 0 -1/4 -1/4 1/4 1/4
f 0 10 0 5 6 2 18
Опорный план Y
3
=(0.25,0,1.75,0,0,0). Текущий опорный план является
оптимальным.
f(Y) = 16∙0.25 = 4.
Z(X) = 2∙6 + 3∙2 = 18.
Оптимальное решение двойственной задачи:
25.0
1
y
– степень дефицитности 1-го ресурса равна 0.25;
0
2
y
– ресурс 2-го вида не дефицитен;
75.1
3
y
– степень дефицитности 3-го ресурса равна 1.75;
0
4
y
– ресурс 4-го вида не дефицитен;
0
5
y
;
0
6
y
– продукты
21
, xx
следует выпускать (штраф равен 0).
Оптимальное решение прямой ЗЛП (из строки f ):
6
1
x
– объем выпуска продукта 1-го вида;
2
2
x
– объем выпуска продукта 2-го вида;
0
3
x
– остатка ресурса 1-го вида нет;
10
4
x
– остаток ресурса 2-го вида;
0
5
x
– остатка ресурса 3-го вида нет;
5
6
x
– остаток ресурса 4-го вида.
Задание 1.3. Решение транспортной задачи линейного
программирования.
В данном задании необходимо найти решение транспортной задачи по
критерию стоимости методом потенциалов. При выполнении задания
укажите формулу для подсчета потенциалов и оценок незаполненных
клеток, а также условие оптимальности решения.
Условия задачи:
19 17 29 28 8 22
13 31 27 16 29 13
20 30 34 7 26 17
11 19 30 16 2 18
7 7 7 7 7
Решение:
Задача является открытой, т.к. запасы поставщиков больше
потребностей потребителей
m
i
n
j
ji
ba
1 1
. Перейдем к закрытой задаче,
добавляя фиктивного (n+1)-го потребителя, потребности которого равны
излишку запасов поставщиков, т.е.
m
i
n
j
jin
bab
1 1
1
.
Тарифы
)1( ni
c
считаются равными нулю.
7 7 7 7 7 35
22 19 17 29 28 8 0
13 13 31 27 16 29 0
17 20 30 34 7 26 0
18 11 19 30 16 2 0
Определим начальный опорный план способом минимального элемента:
7 7 7 7 7 35
22 19 17 [7] 29 28 8 0 [15]
13 13 31 27 [7] 16 29 0 [6]
17 20 30 34 7 [7] 26 0 [10]
18 11 [7] 19 30 16 2 [7] 0 [4]
Заполненных клеток должно быть
.91461 nm
Опорный план
вырожденный.
Определяем потенциалы через заполненные клетки.
6,1 ;4,1 ,0 ;0
1
jicuvu
ijij
.
v
1
=11 v
2
=17 v
3
=27 v
4
=7 v
5
=2 v
6
=0
u
1
=0 17 0
u
2
=0 27 0
u
3
=0 7 0
u
4
=0 11 2 0
Определяем оценки
ij
для незаполненных клеток.
.6,1 ;4,1 , jicuv
ijijij
v
1
=11 v
2
=17 v
3
=27 v
4
=7 v
5
=2 v
6
=0
u
1
=0 19 [-8] 29 [-2] 28 [-21] 8 [-6]
u
2
=0 13 [-2] 31 [-14] 16 [-9] 29 [-27]
u
3
=0 20 [-9] 30 [-13] 34 [-7] 26 [-24]
u
4
=0 19 [-2] 30 [-3] 16 [-9]
План оптимален, т.к. все оценки
ij
неположительны.
Оптимальное решение:
7 7 7 7 7
22 17
13 27
17 7
18 11 2