Линейное программирование и методы оптимизации
Работа из раздела: «
Экономико-математическое моделирование»
16
Задание 1.
Графическим способом решить задачу линейного программирования . Сформулировать задачу, двойственную по отношению к данной.
Решение:
Построим область допустимых решений на плоскости .Для этого запишем уравнения прямых из системы ограничений, заменяя равенствами и преобразуем полученные выражения:
Определим полуплоскости, которые задают неравенства-ограничения.
ОДР - многоугольник. Построим n=grad z=(2,1) и основную прямую z=0, перпендикулярную n.
Перемещая прямую z=0 в направлении n, получим, что последней крайней точкой, в которой прямая пересекается с ОДР, будет точка, в которой достигается максимальное значение целевой функции z. Координаты этой точки определяются решением системы двух линейных уравнений (I) и (II), на пересечении которых она находится. В результате решения системы уравнений (I) и (II) получим оптимальное решение x*:
Сформулируем задачу, двойственную по отношению к данной.
Введём двойственные переменные ; тогда двойственная задача будет иметь вид:
Задание 2.
Графическим способом решить задачу линейного программирования (). Сформулировать задачу двойственную по отношению к данной.
Решение:
Построим область допустимых решений на плоскости Ох1х2. Для этого запишем уравнения прямых из системы ограничений, заменяя неравенства равенствами:
Определим полуплоскости, которые задают неравенства-ограничения. Построим вектор и основную прямую , перпендикулярную
16
Перемещая прямую z=0 в направлении , получим, что первой крайней точкой, в которой прямая пересекается с ОДР, будет точка А. Следовательно в этой точке достигается минимальное значение целевой функции z. Координаты точки А определяются решением системы 2-х линейных уравнений (I) и (II), на пересечении которых она находится.
В результате получаем оптимальное решение:
Сформулируем двойственную задачу.
Двойственная задача имеет вид:
Ответ.
Задание 3.
Построить математическую модель задачи и решить её с использованием симплекс-таблиц. Сформулировать соответствующую двойственную задачу и дать её экономическую интерпретацию.
На предприятии имеется несколько производственных линий. j-я линия производит в единицу времени единиц продукции i-го типа. Для выполнения задания предприятию необходимо выпускать не менее единиц i-го типа продукции, при этом эксплутационные расходы j-й линии составляют млн. руб. в единицу времени. Определить время работы каждой линии для выполнения задания при условии минимизации затрат.
Решение:
Постановка задачи в общем виде:
количество усл.ед. j-вида продукции.
Подставим исходные данные:
Для получения начального допустимого базиса и опорного решения воспользуемся методом элементарных преобразований. Построим симплекс-таблицу, где в качестве нулевой итерации возьмем коэффициенты целевой функции и системы ограничений.
|
№
|
Б
|
x1
|
x2
|
x3
|
x4
|
y1
|
y2
|
z /
|
|
|
0
|
z
|
2
|
3
|
3
|
4
|
0
|
0
|
0
|
|
|
|
5
|
1
|
0
|
1
|
-1
|
0
|
10
|
|
|
|
2
|
1
|
3
|
2
|
0
|
-1
|
12
|
|
|
1
|
z
|
2
|
3
|
3
|
4
|
0
|
0
|
0
|
|
|
y1
|
-5
|
-1
|
0
|
-1
|
1
|
0
|
-10
|
|
|
y2
|
-2
|
-1
|
-3
|
-2
|
0
|
1
|
-12
|
|
|
2
|
z
|
-13
|
0
|
3
|
1
|
3
|
0
|
-30
|
|
|
x2
|
5
|
1
|
0
|
1
|
-1
|
0
|
10
|
|
|
y2
|
3
|
0
|
-3
|
-1
|
-1
|
1
|
-2
|
|
|
3
|
z
|
-10
|
0
|
0
|
0
|
2
|
1
|
-32
|
|
|
x2
|
8
|
1
|
-3
|
0
|
-2
|
1
|
8
|
|
|
x4
|
-3
|
0
|
3
|
1
|
1
|
-1
|
2
|
|
|
4
|
z
|
0
|
10/8
|
-30/8
|
0
|
-1/2
|
18/8
|
-22
|
|
|
x1
|
1
|
1/8
|
-3/8
|
0
|
-1/4
|
1/8
|
1
|
|
|
x4
|
0
|
3/8
|
15/8
|
1
|
ј
|
-5/8
|
5
|
|
|
5
|
z
|
0
|
2
|
0
|
2
|
0
|
2
|
-12
|
|
|
x1
|
1
|
Ѕ
|
12/8
|
1
|
0
|
-1/2
|
6
|
|
|
y1
|
0
|
12/8
|
15/2
|
4
|
1
|
-5/2
|
20
|
|
|
Все коэффициенты в строке целевой функции и в столбце положительны, поэтому полученное решение является оптимальным.
Сформулируем двойственную задачу.
Экономическая интерпретация двойственной задачи:
Найти такую совокупность стоимостей единицы продукции i-го типа, при которых общая стоимость производимой продукции была бы максимальной, при условии что суммарная цена единиц всех четырех видов производимой продукции была бы не больше эксплуатационных расходов j-ой линии в единицу времени.
Ответ:
Задание 4.
Построить математическую модель задачи и решить её с использованием симплекс-таблиц. Сформулировать соответствующую двойственную задачу и дать её экономическую интерпретацию.
При выпуске одной усл. ед. j-го вида товаров необходимо усл. ед. i-го типа сырья, при этом в виде отходов получают усл. ед. k-го типа сырья. При реализации одной усл. ед. j-го вида товаров выручают тыс. руб. От поставщиков не может поступать более усл .ед. i-го типа сырья. Рассчитать план выпуска каждого вида товаров для получения наибольшей прибыли.
Решение:
Постановка задачи в общем виде:
количество усл.ед. j-вида ресурса.
Подставим исходные данные:
Приведем ЗЛО к ОЗЛО, т.е. перейдем от ограничений-неравенств к ограничениям-равенствам путем введения новых переменных.
Для получения начального допустимого базиса и опорного решения воспользуемся методом элементарных преобразований. Построим симплекс-таблицу, где в качестве нулевой итерации возьмем коэффициенты целевой функции и системы ограничений.
|
№
|
Б
|
x1
|
x2
|
x3
|
y1
|
y2
|
y3
|
z /
|
|
|
0
|
z
|
-2
|
-3
|
-2
|
0
|
0
|
0
|
0
|
|
|
y1
|
6
|
2
|
2
|
1
|
0
|
0
|
10
|
|
|
y2
|
0
|
4
|
1
|
0
|
1
|
0
|
3
|
|
|
y3
|
4
|
5
|
5
|
0
|
0
|
1
|
11
|
|
|
1
|
z
|
-2
|
0
|
-5/4
|
0
|
ѕ
|
0
|
9/4
|
|
|
y1
|
6
|
0
|
3/2
|
1
|
-1/2
|
0
|
17/2
|
|
|
x2
|
0
|
1
|
ј
|
0
|
ј
|
0
|
ѕ
|
|
|
y3
|
4
|
0
|
15/4
|
0
|
-5/4
|
1
|
29/4
|
|
|
2
|
z
|
-2/3
|
0
|
0
|
0
|
1/3
|
1/3
|
14/3
|
|
|
y1
|
22/5
|
0
|
0
|
1
|
0
|
-2/5
|
28/5
|
|
|
x2
|
-4/15
|
1
|
0
|
0
|
1/3
|
-1/15
|
4/15
|
|
|
x3
|
16/15
|
0
|
1
|
0
|
-1/3
|
4/15
|
29/15
|
|
|
3
|
z
|
0
|
0
|
0
|
5/33
|
1/3
|
3/11
|
182/33
|
|
|
x1
|
1
|
0
|
0
|
5/22
|
0
|
-1/11
|
14/11
|
|
|
x2
|
0
|
1
|
0
|
2/33
|
1/3
|
-1/11
|
20/33
|
|
|
x3
|
0
|
0
|
1
|
-8/33
|
-1/3
|
4/11
|
19/33
|
|
|
Все коэффициенты в строке целевой функции и в столбце положительны, поэтому полученное решение является оптимальным.
Сформулируем двойственную задачу.
Экономическая интерпретация двойственной задачи:
Найти такую совокупность стоимостей единицы продукции i-го вида товара, при которых общая стоимость производимого товара была бы минимальной, при условии что суммарная цена единиц всех видов производимого товара была бы не меньше выручки при реализации одной условной ед. j-го вида товара.
Ответ:
Задание 5.
|
Пi
|
Зj
|
|
|
|
45
|
38
|
40
|
28
|
34
|
|
|
20
|
3
|
17
|
6
|
19
|
2
|
|
|
40
|
1
|
15
|
7
|
6
|
1
|
|
|
52
|
5
|
13
|
8
|
11
|
17
|
|
|
73
|
18
|
13
|
17
|
1
|
8
|
|
|
Завод имеет 4 цеха А,B,C,D и 5 складов. Производительность 1-го цеха за смену П1 тыс.шт. деталей,i =1,4; пропускная способность j-го склада за это же время составляет Е1 тыс. шт. деталей,j=1,5;.Стоимост перевозок 1 тыс.шт. деталей из цеха 1 в склад j задаются матрицей РРCijРР
Составить такой план перевозки изделий, при котором расходы на перевозку изделий были бы наименьшими.
Решение.
|
Пi
|
45
|
38
|
40
|
28
|
34
|
i
|
|
|
20
|
53
|
717
|
8 6
|
-519
|
2220
|
0
|
|
|
40
|
41+
|
615
|
7733-
|
-66
|
117
|
-1
|
|
|
52
|
5545-
|
713
|
887+
|
-511
|
217
|
0
|
|
|
73
|
1318
|
131338
|
1417
|
1128
|
887
|
6
|
|
|
j
|
5
|
7
|
8
|
-5
|
2
|
|
|
|
|
Пi
|
45
|
38
|
40
|
28
|
34
|
i
|
|
|
20
|
23
|
1317
|
5 6
|
119
|
22 20
|
0
|
|
|
40
|
11 33+
|
1215
|
47
|
06
|
11 7-
|
-1
|
|
|
52
|
55 12-
|
1613 +
|
88 40
|
411
|
517
|
3
|
|
|
73
|
218
|
1313 38-
|
517
|
11 28
|
88 7+
|
0
|
|
|
j
|
2
|
13
|
5
|
1
|
2
|
|
|
|
|
Пi
|
45
|
38
|
40
|
28
|
34
|
i
|
|
|
20
|
-13
|
717
|
2 6
|
-519
|
22 20
|
0
|
|
|
40
|
1 1 40
|
915
|
47
|
36
|
41 +
|
2
|
|
|
52
|
55 5+
|
1313 7-
|
88 40
|
111
|
817
|
6
|
|
|
73
|
518
|
1313 31+
|
817
|
11 28
|
88 14-
|
6
|
|
|
j
|
-1
|
7
|
5
|
-5
|
2
|
|
|
|
|
Пi
|
45
|
38
|
40
|
28
|
34
|
i
|
|
|
20
|
23
|
717
|
5 6
|
-519
|
22 20
|
0
|
|
|
40
|
1 1 40
|
615
|
47
|
-66
|
41 +
|
-1
|
|
|
52
|
55 12
|
1013
|
88 40
|
-211
|
517
|
3
|
|
|
73
|
818
|
1313 38
|
1117
|
11 28
|
88 7
|
6
|
|
|
j
|
2
|
7
|
5
|
-5
|
2
|
|
|
|
План является оптимальным.
Задание 6.
На 5 складах находится по m горючего, . Его нужно перевести к 4 АЗС, потребности которых составляют m, . Стоимость перевозок от j-го склада к i-й АЗС задаются матрицей Составить такой план перевозки горючего, при котором транспортные расходы будут наименьшими.
|
Пi
|
Зj
|
|
|
|
90
|
120
|
170
|
125
|
75
|
|
|
110
|
9
|
3
|
1
|
4
|
6
|
|
|
190
|
4
|
9
|
3
|
7
|
15
|
|
|
130
|
3
|
8
|
4
|
13
|
7
|
|
|
150
|
7
|
4
|
9
|
5
|
10
|
|
|
Решение.
|
Пi
|
Зj
|
|
|
|
90
|
120
|
170
|
125
|
75
|
|
|
110
|
9
|
3
|
1
|
4
|
6
|
|
|
190
|
4
|
9
|
3
|
7
|
15
|
|
|
130
|
3
|
8
|
4
|
13
|
7
|
|
|
150
|
7
|
4
|
9
|
5
|
10
|
|
|
Постановка транспортной задачи в общем виде:
количество единиц груза, которое нужно доставить из i-ПО в j-ПН
Подставим исходные данные:
транспортная задача является закрытой.
Решим транспортную задачу с помощью транспортной таблицы методом потенциалов.
число базисных клеток.
Составим план перевозок методом наименьшей цены.
|
90
|
120
|
170
|
125
|
75
|
i
|
|
|
110
|
29
|
43
|
11 110
|
54
|
66
|
0
|
|
|
190
|
44 35
|
69
|
33 60
|
77 95
|
815
|
2
|
|
|
130
|
33 55
|
58
|
24
|
613
|
77 75
|
1
|
|
|
150
|
27
|
44 120
|
19
|
55 30
|
610
|
0
|
|
|
j
|
2
|
4
|
1
|
5
|
6
|
|
|
|
План можно улучшить, так как есть свободные клетки, где псевдостоимость больше стоимости (5>4). Рассмотрим цикл , который минимизирует план на 95 единицы. Получился новый план.Снова рассчитаем псевдостоимости.
|
90
|
120
|
170
|
125
|
75
|
i
|
|
|
110
|
29
|
33
|
1 1 15
|
44 95
|
66
|
0
|
|
|
190
|
4 4 35
|
59
|
33 155
|
67
|
815
|
2
|
|
|
130
|
33 55
|
48
|
24
|
513
|
77 75
|
1
|
|
|
150
|
37
|
44 120
|
29
|
55 30
|
710
|
1
|
|
|
j
|
2
|
3
|
1
|
4
|
6
|
|
|
|
полученный план перевозок является оптимальным.
Сформулируем двойственную задачу:
Экономическая интерпретация двойственной задачи:
Найти такую совокупность u1…u9 - платежей от потребителей, чтобы общая сумма оплаты поставщикам за предоставленный груз была бы максимальной.
Ответ:, .
