Саак А.Э. Методические указания к выполнению лабораторных работ по курсу Разработка управленческого решения
Подождите немного. Документ загружается.
51
ячейке F8 и ячейках B8:E8 (ограничения по плану), F4:F6 (ограничения по
количеству самолетов) (см. рис. 31 и 32). Вид электронной таблицы в режиме
отображения формул представлен на рис. 32.
Рис. 32
Рис. 33
В группе
Ограничения (см. рис. 33) заданы, помимо остальных, ограни-
чения на целочисленность переменных (первая запись), означающие, что ко-
личество выбранных самолетов (значения x
ij
) должно быть целым числом. За-
дание ограничения на целочисленность увеличивает время вычислений Поис-
ка решения.
Результаты поиска решения приведены на рис. 31.
4. 6. Задача о ранце
В грузовую автомашину надо поместить четыре вида предметов, причем
могут потребоваться несколько одинаковых предметов. Имеется три вида ог-
раничений такого типа, как вес, объем и т.д. В приведенной ниже таблице да-
52
ны a
ij
- i-я характеристика предмета j-го наименования, c
j
- полезность одного
предмета j-го наименования (i=
13, , j=14, ). Требуется загрузить машину так,
чтобы суммарная полезность груза была максимальной.
Ограничения Пред
мет1
Пред
мет2
Пред
мет3
Пред-
мет4
Значения огра-
ничений
I 3 3 5 2 1000
II 4 2 4 4 600
III 3 5 4 3 600
Полезность
3 4 3 3
Математическая модель задачи выглядит следующим образом.
Целевая функция имеет вид:
3⋅x
1
+4⋅x
2
+3⋅x
3
+3⋅x
4
→max,
Ограничения имеют вид:
3⋅x
1
+3⋅x
2
+5⋅x
3
+2⋅x
4
≤1000,
4⋅x
1
+2⋅x
2
+4⋅x
3
+4⋅x
4
≤600,
3⋅x
1
+5⋅x
2
+4⋅x
3
+3⋅x
4
≤600,
x
j
≥0, целые, j=14, .
Вид электронной таблицы Excel, созданной для решения задачи, пред-
ставлен на рис. 34. Значения переменных x
ij
располагаются в блоке ячеек
B3:E3 (см. рис. 34). Коэффициенты целевой функции, отражающие полезно-
сти предметов находятся по адресам B6:E6. Данные о характеристиках пред-
метов имеются в блоке B9:E11. Заданы значения ограничений- соответствен-
но блок H9:H11.
Рис. 34
Формулы целевой функции и ограничений находятся соответственно в
53
ячейке F6 и ячейках F9:E11 (ограничения по свойствам) (см. рис. 34 и 35).
Вид электронной таблицы в режиме отображения формул представлен на рис.
35.
Запись условий задачи в окне "Поиск решения" можно увидеть на рис.
36.
Результаты поиска решения приведены на рис. 34.
Рис. 35
Рис. 36
4. 7. Назначение механизмов на работы
Имеются три механизма М
1
, М
2
, М
3
, каждый из которых может быть ис-
пользован на трех видах работ Р
1
, Р
2
, Р
3
с производительностью (в условных
единицах), заданной в виде таблицы:
Механизмы Работы
Р
1
Р
2
Р
3
М
1
1 2 3
М
2
2 4 1
М
3
3 1 5
54
Требуется так распределить механизмы по одному на каждую из работ,
чтобы суммарная производительность всех механизмов была максимальной.
Математическая модель задачи выглядит следующим образом.
Целевая функция имеет вид:
x
11
+2⋅x
12
+3⋅x
13
+2⋅x
21
+4⋅x
22
+x
23
+3⋅x
31
+x
32
+5⋅x
33
→max,
Ограничения имеют вид:
x
11
+x
12
+x
13
=1,
x
21
+x
22
+x
23
=1,
x
31
+x
32
+x
33
=1,
x
11
+x
21
+x
31
=1,
x
12
+x
22
+x
32
=1,
x
13
+x
23
+x
33
=1.
Вид электронной таблицы Excel, созданной для решения задачи, пред-
ставлен на рис. 37. Значения переменных x
ij
располагаются в блоке ячеек
B4:D6 (см. рис. 37). Коэффициенты целевой функции, отражающие произво-
дительность механизмов, находятся по адресам B11:D13.
Рис. 37
Формулы целевой функции и ограничений находятся соответственно в
ячейке E8 и ячейках E4:E6 (каждый механизм может быть назначен только на
одну работу), B8:D8 (каждая работа выполняется только на одном механизме)
(см. рис. 37 и 38). Вид электронной таблицы в режиме отображения формул
представлен на рис. 38.
55
Рис. 38
Рис. 39
Данная задача является задачей линейного булева программирования и в
ней переменные x
ij
должны принимать значения либо 0 либо 1. В поиске ре-
шения такое ограничение задается тремя ограничениями, по которым изме-
няемые ячейки в блоке (x
ij
) одновременно больше либо равны 0, меньше либо
равны 1 и являются целыми. Первые три записи в группе
Ограничения (см.
рис. 39) отражают этот факт.
Результаты поиска решения приведены на рис. 37.
4. 8. Задача коммивояжера
Коммивояжеру, находящемуся в Париже, необходимо посетить три го-
рода. Он получил информацию о стоимости проезда самолетом в каждый из
выбранных городов и стоимость проезда из одного города в другой. На осно-
ве добытых данных он составил матрицу стоимостей (см. табл.) проезда в вы-
бранные города и обратно. Зная матрицу стоимостей коммивояжеру
надо так
составить маршрут путешествия, чтобы затраты на путешествие были бы ми-
нимальными и чтобы выполнялось требование: каждый пункт посещается
56
только один раз.
Пункты Париж Берлин Рим Лондон
Париж 0 270 430 160
Берлин 70 0 160 10
Рим 200 130 0 350
Лондон 210 160 250 0
Математическая модель задачи выглядит следующим образом.
Целевая функция имеет вид:
0x
11
+270⋅x
12
+430⋅x
13
+160⋅x
14
+70⋅x
21
+0⋅x
22
+160x
23
+10x
24
+200⋅x
31
+130x
32
+0⋅
x
33
+ +350⋅x
34
+210⋅x
41
+160x
42
+250⋅x
43
+0⋅x
44
→min,
Ограничения имеют вид:
x
11
+x
21
+x
31
+x
41
=1,
x
12
+x
22
+x
32
+x
42
=1,
x
13
+x
23
+x
33
+x
43
=1.
x
14
+x
24
+x
34
+x
44
=1,
x
11
+x
12
+x
13
+x
14
=1,
x
21
+x
22
+x
23
+x
24
=1,
x
31
+x
32
+x
33
+x
34
=1,
x
41
+x
42
+x
43
+x
44
=1,
u
2
-u
3
+3⋅x
23
≤2,
u
2
-u
4
+3⋅x
24
≤2,
u
3
-u
2
+3⋅x
32
≤2,
u
3
-u
4
+3⋅x
34
≤2,
u
4
-u
2
+3⋅x
42
≤2,
u
4
-u
3
+3⋅x
43
≤2.
Вид электронной таблицы, созданной для решения задачи, представлен
на рис. 40. Значения переменных x
ij
располагаются в блоке B3:E6. В данном
блоке ячейки, расположенные по диагонали обнулены (пункт назначения не
может быть одновременно пунктом прибытия) и выделены, для удобства за-
дания ограничений. Даны стоимости проезда из города в город (блок
57
B11:E14). Для вычислений необходимо задать размерность задачи n (количе-
ство городов)- ячейка F16.
Рис. 40
Целевая функция расположена в ячейке F8. Ограничения находятся в
блоках B7:E7 (коммивояжер въезжает один раз в каждый город) и F3:F6
(коммивояжер выезжает из каждого города один раз) (см. рис. 40 и 41). Вид
электронной таблицы в режиме отображения формул представлен на рис. 41.
В задаче коммивояжера есть ряд специфических ограничений по дополни-
тельным переменным u
i
(см. мат модель). Формулы этих ограничений нахо-
дятся в блоке ячеек B17:E19. Значения самих переменных располагаются в
блоке B8:E8.
На рис. 42 представлена запись условий задачи в окне "Поиск решения".
Как известно, дополнительные переменные не относятся к целевой функции,
но они, также как и x
ij
, являются изменяемыми, поэтому адреса содержащих
их ячеек должны быть введены в поле
Изменяя ячейки одновременно с ад-
ресами переменных целевой функции.
Операцию ввода удобно проводить с помощью мыши. Необходимо ус-
тановить курсор ввода в поле
Изменяя ячейки, затем выделить мышью блок
ячеек переменных целевой функции, нажать <Ctrl> и, удерживая эту клави-
шу, выделить мышью блок ячеек рабочего листа, отведенный для перемен-
58
ных u
i
. В поле ввода адреса блоков отделяются ";" (см. рис. 42).
Рис. 41
Перечислим ограничения, которых не видно на рис. 42: $C$4=0; $D$5=0;
$E$6=0; $F$3:$F$6=1.
Рис. 42
Первая запись в группе
Ограничения представляет собой совокупность
ограничений по дополнительным переменным u
i
. Каждая ячейка блока в ле-
вой части неравенства содержит формулу одного ограничения (см. рис. 41 и
мат. модель), правую часть представляет одно значение, равное n-2, содер-
жащееся в F18. Такая запись означает, что каждая ячейка блока $B$17:$D$19
меньше либо равна 2 (4-2=2).
В поиске решения нельзя явно задать ограничение i≠j. Исходя из смысла
переменных x
ij
можно предположить, что значения тех x
ij
, для которых i=j
(расположенных по диагонали в блоке переменных), всегда должны быть
равны 0 и ввести соответствующие ограничения. В группе
Ограничения та-
ких ограничений четыре: $B$3=0, $C$4=0, $D$5=0, $E$6=0.
По результатам поиска решения найден ответ задачи: из Парижа комми-
59
вояжер летит в Лондон, оттуда в Рим, затем в Берлин, откуда возвращается в
Париж. Общая стоимость перелета составит 610 д. е. (см. рис. 40).
4. 9. Задача о доставке
Фирма обслуживает 5 клиентов. Каждый день она доставляет своим кли-
ентам товары на грузовых машинах. Существует 3 допустимых маршрута
доставки, каждый из которых позволяет обслужить определенное количество
клиентов и требует использования в течении дня одного транспортного сред-
ства. Каждый маршрут характеризуется определенными расходами (см.
табл.). Необходимо выбрать такое множество маршрутов, при котором обес
-
печивается обслуживание каждого из клиентов и, кроме того, суммарные
расходы минимальны, при условии, что каждый клиент обслуживается один
раз в день.
Таблица обслуживания клиентов по мар-
шрутам
Клиенты Маршруты
1 2 3
1
1 1
2
1
Продолжение табл.
3
1 1
4
1
5
1 1
Расходы по
маршруту
900 1000 800
Математическая модель задачи выглядит следующим образом.
Целевая функция имеет вид:
900⋅x
1
+1000⋅x
2
+800⋅x
3
→min,
Ограничения имеют вид:
1⋅x
11
+0⋅x
21
+1⋅x
31
=1,
1⋅x
12
+0⋅x
22
+0⋅x
32
=1,
60
1⋅x
13
+0⋅x
23
+1⋅x
33
=1,
0⋅x
12
+1⋅x
22
+0⋅x
32
=1,
0⋅x
13
+1⋅x
23
+1⋅x
33
=1.
Вид электронной таблицы Excel, созданной для решения задачи, пред-
ставлен на рис. 43. Значения переменных x
j
располагаются в блоке ячеек
B10:D10 (см. рис. 43). Коэффициенты целевой функции, отражающие стои-
мость доставки по маршруту, находятся по адресам B9:D9. Данные об обслу-
живании клиентов по маршрутам имеются в блоке B4:D8
Рис. 43
Формулы целевой функции и ограничений находятся соответственно в
ячейке E10 и ячейках E4:E8 (каждый клиент обслуживается по каждому мар-
шруту только один раз в день) (см. рис. 43 и 44). Вид электронной таблицы в
режиме отображения формул представлен на рис. 44.
Рис. 44
Запись условий задачи в окне "Поиск решения" можно увидеть на рис.
45.
Результаты поиска решения приведены на рис. 43.