Решение задач теории графов средствами Excel

Задача о закреплении самолетов за воздушными линиями

Эта задача возникает при выборе оптимального варианта плана закрепления самолетов за данными воздушными линиями, обеспечивающего необходимые объемы перевозок при минимальных суммарных эксплуатационных расходах.

Пусть имеется n различных типов самолетов, которые нужно распределить между m авиалиниями. Пусть месячный объем перевозок самолетом i-го типа на j-й авиалинии равен а_ij единицам, а связанные с этим месячные эксплуатационные расходы составляют c_ij рублей. Определить число x_ij самолетов i-го типа, которое следует закрепить за j-й авиалинией для обеспечения перевозки по этой линии а_ij единиц ( ) при минимальных суммарных эксплуатационных расходах, если известно, что имеется N_i самолетов i-го типа ( ).

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

.

ЦФ представляет суммарные эксплуатационные расходы в месяц.

Ограничения имеют вид:

x_ij 0, x_ij- целые числа, .

Условия (1) определяют, что самолеты j-й авиалинии должны обеспечивать объем перевозок не меньше заданного.

Условия (2) представляют собой ограничение по количеству имеющихся самолетов i-го типа.

Пример 3.5

Три типа самолетов требуется распределить между четырьмя авиалиниями. В приводимых ниже таблицах задано число самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы.

Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000 и 500 единиц груза.

Тип самолета	Число самолетов	Месячный объем перевозок одним самолетом по авиалиниям
		I	II	III	IV

Тип самолета	Эксплуатационные расходы
	I	II	III	IV

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

15x₁₁+20x₁₂+25x₁₃+40x₁₄+70x₂₁+28x₂₂+15x₂₃+45x₂₄+40x₃₁+70x₃₂+40x₃₃+65x₃₄ ®min,

Ограничения имеют вид:

15x₁₁+30x₂₁+25x₃₁ 300,

10x₁₂+25x₂₂+50x₃₂ 200,

20x₁₃+10x₂₃+30x₃₃ 1000,

50x₁₄+17x₂₄+45x₃₄ 500,

x₁₁+x₁₂+x₁₃+x₁₄=50,

x₂₁+x₂₂+x₂₃+x₂₄=20,

x₃₁+x₃₂+x₃₃+x₃₃=30,

x_ij 0, целые ( ).

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 31. Значения переменных x_ij располагаются в блоке ячеек B4:E6 (см. рис. 3.14). Коэффициенты целевой функции, отражающие расходы на перевозку находятся по адресам B18:E20. Данные о месячных объемах перевозок одним самолетом имеются в блоке B12:E14. Задан план перевозок и число самолетов- соответственно блоки B7:E7 и F4:F6.

Формулы целевой функции и ограничений находятся соответственно в ячейке F8 и ячейках B8:E8 (ограничения по плану), F4:F6 (ограничения по количеству самолетов) (см. рис. 3.14 и 3.15). Вид электронной таблицы в режиме отображения формул представлен на рис. 3.15.

В группе Ограничения (см. рис. 3.16) заданы, помимо остальных, ограничения на целочисленность переменных (первая запись), означающие, что количество выбранных самолетов (значения x_ij) должно быть целым числом. Задание ограничения на целочисленность увеличивает время вычислений Поиска решения.

Результаты поиска решения приведены на рис. 3.14.

Рис. 3.14

Рис. 3.15

Рис. 3.16

Задача о ранце

Здесь речь идет о собравшемся в поход путешественнике, который должен упаковать в ранец различные полезные предметы n наименований, причем могут потребоваться несколько одинаковых предметов. Имеются m ограничений такого типа, как вес, объем, линейные размеры и т.д. Пусть а_ij- i-я характеристика предмета j-го наименования , b_i- ограничения по весу, объему и т.д. Обозначим через x_j количество предметов j-го наименования, запланированное к погрузке в ранец . Считается, что известна полезность c_j одного предмета j.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

.

ЦФ представляет суммарная полезность собранных предметов.

Ограничения имеют вид:

x_j 0, x_j- целое, .

Условия (1) означают, что количество отобранных предметов не превышает возможностей погрузки.

Пример 3.6

В грузовую автомашину надо поместить четыре вида предметов, причем могут потребоваться несколько одинаковых предметов. Имеется три вида ограничений такого типа, как вес, объем и т.д. В приведенной ниже таблице даны a_ij– i-я характеристика предмета j-го наименования, c_j- полезность одного предмета j-го наименования ( ). Требуется загрузить машину так, чтобы суммарная полезность груза была максимальной.

Ограничения	Предмет1	Предмет2	Предмет3	Предмет4	Значения ограничений
I
II
III
Полезность

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

3x₁+4x₂+3x₃+3x₄→ max,

Ограничения имеют вид:

3x₁+3x₂+5x₃+2x₄ 1000,

4x₁+2x₂+4x₃+4x₄ 600,

3x₁+5x₂+4x₃+3x₄ 600,

x_j 0, целые, .

Вид электронной таблицы Excel, созданной для решения задачи, представлен на рис. 34. Значения переменных x_ij располагаются в блоке ячеек B3:E3 (см. рис. 3.17). Коэффициенты целевой функции, отражающие полезности предметов находятся по адресам B6:E6. Данные о характеристиках предметов имеются в блоке B9:E11. Заданы значения ограничений соответственно блок H9:H11.

Рис. 3.17

Формулы целевой функции и ограничений находятся соответственно в ячейке F6 и ячейках F9:E11 (ограничения по свойствам) (см. рис. 3.17 и 3.18). Вид электронной таблицы в режиме отображения формул представлен на рис. 318.

Запись условий задачи в окне "Поиск решения" можно увидеть на рис. 3.19.

Результаты поиска решения приведены на рис. 3.17.

Рис. 3.18

Рис. 3.19

Задача коммивояжера

Имеется n городов. Выезжая из исходного города А₁, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в город А₁.

Задача заключается в определении последовательности объезда городов, при которой коммивояжеру требуется минимизировать некоторый критерий эффективности: стоимость проезда, время в пути, суммарное расстояние и т.д. Пусть задана матрица C=||c_ij|| расстояний между городами и требуется минимизировать суммарную длину пути.

Введем переменные

x_ij=1, если коммивояжер переезжает из города А_i в город А_j, i j;

x_ij=0, в противном случае,

.

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

.

ЦФ представляет суммарную длину пути.

Ограничения имеют вид:

где u_i, - неограниченные действительные переменные.

Условия (1) означает, что коммивояжер выезжает из каждого города один раз, а условия (2)- что он въезжает один раз в каждый город.

Условия (3), выглядящие несколько искусственно, предназначены обеспечить связность маршрута коммивояжера. Более точно эти условия запрещают любой цикл, не проходящий через город 1, и тем самым исключают ситуации, подобные приведенной на рисунке 3.20.

Рис. 3.20

Пример 3.7

Коммивояжеру, находящемуся в Париже, необходимо посетить три города. Он получил информацию о стоимости проезда самолетом в каждый из выбранных городов и стоимость проезда из одного города в другой. На основе добытых данных он составил матрицу стоимостей (см. табл.) проезда в выбранные города и обратно. Зная матрицу стоимостей коммивояжеру надо так составить маршрут путешествия, чтобы затраты на путешествие были бы минимальными и чтобы выполнялось требование: каждый пункт посещается только один раз.

Пункты	Париж	Берлин	Рим	Лондон
Париж
Берлин
Рим
Лондон

Математическая модель задачи выглядит следующим образом.

Целевая функция имеет вид:

0x₁₁+270x₁₂+430x₁₃+160x₁₄+70x₂₁+0x₂₂+160x₂₃+10x₂₄+200x₃₁+130x₃₂+0x₃₃+ +350x₃₄+210x₄₁+160x₄₂+250x₄₃+0x₄₄® min,

Ограничения имеют вид:

x₁₁+x₂₁+x₃₁+x₄₁=1,

x₁₂+x₂₂+x₃₂+x₄₂=1,

x₁₃+x₂₃+x₃₃+x₄₃=1.

x₁₄+x₂₄+x₃₄+x₄₄=1,

x₁₁+x₁₂+x₁₃+x₁₄=1,

x₂₁+x₂₂+x₂₃+x₂₄=1,

x₃₁+x₃₂+x₃₃+x₃₄=1,

x₄₁+x₄₂+x₄₃+x₄₄=1,

u₂-u₃+3x₂₃ 2,

u₂-u₄+3x₂₄ 2,

u₃-u₂+3x₃₂ 2,

u₃-u₄+3x₃₄ 2,

u₄-u₂+3x₄₂ 2,

u₄-u₃+3x₄₃ 2.

Вид электронной таблицы, созданной для решения задачи, представлен на рис. 3.21. Значения переменных x_ij располагаются в блоке B3:E6. В данном блоке ячейки, расположенные по диагонали обнулены (пункт назначения не может быть одновременно пунктом прибытия) и выделены, для удобства задания ограничений. Даны стоимости проезда из города в город (блок B11:E14). Для вычислений необходимо задать размерность задачи n (количество городов) - ячейка F16.

Рис. 3.21

Целевая функция расположена в ячейке F8. Ограничения находятся в блоках B7:E7 (коммивояжер въезжает один раз в каждый город) и F3:F6 (коммивояжер выезжает из каждого города один раз) (см. рис. 3.21 и 3.22). Вид электронной таблицы в режиме отображения формул представлен на рис. 3.22. В задаче коммивояжера есть ряд специфических ограничений по дополнительным переменным u_i (см. мат модель). Формулы этих ограничений находятся в блоке ячеек B17:E19. Значения самих переменных располагаются в блоке B8:E8.

На рис. 3.23 представлена запись условий задачи в окне "Поиск решения". Как известно, дополнительные переменные не относятся к целевой функции, но они, также как и x_ij, являются изменяемыми, поэтому адреса содержащих их ячеек должны быть введены в поле Изменяя ячейки одновременно с адресами переменных целевой функции.

Операцию ввода удобно проводить с помощью мыши. Необходимо установить курсор ввода в поле Изменяя ячейки, затем выделить мышью блок ячеек переменных целевой функции, нажать <Ctrl> и, удерживая эту клавишу, выделить мышью блок ячеек рабочего листа, отведенный для переменных u_i. В поле ввода адреса блоков отделяются ";" (см. рис. 3.23).

Рис. 3.22

Перечислим ограничения, которых не видно на рис. 42: $C$4=0; $D$5=0; $E$6=0; $F$3:$F$6=1.

Рис. 3.23

Первая запись в группе Ограничения представляет собой совокупность ограничений по дополнительным переменным u_i. Каждая ячейка блока в левой части неравенства содержит формулу одного ограничения (см. рис. 3.22 и мат. модель), правую часть представляет одно значение, равное 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.

По результатам поиска решения найден ответ задачи: из Парижа коммивояжер летит в Лондон, оттуда в Рим, затем в Берлин, откуда возвращается в Париж. Общая стоимость перелета составит 610 д. е. (см. рис. 3.21).