Пример №3
Фирма, обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: “Морской”, “Солнечный”, “Слава” и “Уютный”, в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять прилетают очередным рейсом в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов прибытия в отели приведены в таблице 1.
Исходный пункт, i |
Пункт назначения (отели), j | ||||
|
Морской |
Солнечный |
Слава |
Уютный | |
|
1 |
2 |
3 |
4 | |
Железнодорожный
вокзал |
1 |
10 |
0 |
20 |
11 |
Аэропорт |
2 |
12 |
7 |
9 |
20 |
Морской
вокзал |
3 |
0 |
14 |
16 |
18 |
Таблица 1
В условиях жесткой конкуренции фирма должна минимизировать свои расходы, значительную часть которых составляет именно транспортные расходы. Требуется определить такой план перевозки туристов из пункта прибытия в отели, при котором суммарные транспортные расходы будут минимальны и все туристы будут размещены в отелях.
Математическая модель задачи
1) Переменные задачи. Обозначим количество туристов, которые будут перевозиться из пункта i в отель j как Xij (i=1,2,3; j=1,2,3,4). Это переменные задачи, значения которых должны быть определены в процессе решения. Например, X23 – это число туристов, которое должно быть перевезено из аэропорта (пункт 2) в отель “Слава” (пункт 3). В задаче содержится 3*4=12 переменных.
2) Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные и целые числа, т.е.
Xij – целые числа, (2)
где i=1, 2, 3; j=1, 2, 3, 4.
Кроме этого, должны быть удовлетворяться следующие условия. Число туристов, вывозимых с железнодорожного вокзала (пункт 1) равно 15, поэтому:
X11 + X12 + X13 + X14 = 15 (3)
Аналогично для аэропорта (пункт 2):
X21 + X22 + X23 + X24 = 25 (4)
И для морского вокзала (пункт 3):
X31 + X32 + X33 + X34 = 5 (5)
По условию задачи в отеле “Морской” (пункт 1) забронировано 5 мест, поэтому:
X11 + X21 + X31 = 5 (6)
Аналогично, для отеля “Солнечный” (пункт 2):
X12 + X22 + X32 = 15 (7)
Для отеля “Слава” (пункт 3):
X13 + X23 + X33 =15 (8)
Для отеля “Уютный” (пункт 4):
X14 + X24 + X34 =10 (9)
Обычно транспортная задача представляется в виде таблицы, где в ячейках помещаются переменные задачи (Xij), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j (Cij). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи (в данном примере – это число туристов в исходных пунктах и число мест в пунктах назначения – отелях).
Для примера 2 таблица имеет вид:
Исходный
пункт,i |
Пункт назначения
(отели),j |
Число туристов в
исходном пункте | |||||||
|
1 |
2 |
3 |
4 |
| ||||
|
|
10 |
|
0 |
|
20 |
|
11 |
|
1 |
X11 |
|
X12 |
|
X13 |
|
X14 |
|
15 |
|
|
12 |
|
7 |
|
9 |
|
20 |
|
2 |
X21 |
|
X22 |
|
X23 |
|
X24 |
|
25 |
|
|
0 |
|
14 |
|
16 |
|
18 |
|
3 |
X31 |
|
X32 |
|
X33 |
|
X34 |
|
5 |
|
5 |
15 |
15 |
10 |
45 |
Таблица 2
3) Целевая функция. Транспортные расходы на перевозку туристов в отели вычисляются по формуле:
Z = CijXij = 10X11 + 0X12 + 20X13 + ... +18X34 (10)
Окончательно транспортная задача имеет вид (таблица 2). Нужно найти такие значения переменных Xij (i=1,2,3; j=1,2,3,4) при которых целевая функция, определяемая формулой (10), будет иметь минимальное значение и будут выполнены ограничения (1) - (9)
Как и в рассмотренной выше задаче оптимального выпуска продукции (пример 1) транспортная задача является задачей линейного программирования.
Решение транспортной задачи в Excel
1) Ввод данных. Вводим данные таблицы 1 и 2 в ячейки Excel (рис.9).
В ячейках B3 : E5 введены стоимости перевозок (табл. 1).
В ячейках F3 : F5 находится число прибывающих туристов. А в ячейках B6 : E6 находится число мест в отелях. Ячейки B8 : E10 – рабочие (изменяемые) ячейки, в которых будут вычисляться значения переменных задачи Xij.
В ячейках F8 : F10 нужно записать формулы для вычисления левых частей ограничений (3)-(5):
в F8 должна быть сумма ячеек B8 : E8;
в F9 должна быть сумма ячеек B9 : E9;
в F10 должна быть сумма ячеек B10 : E10.
Формулы для вычисления левых частей ограничений (6)-(9) введем в ячейки B11 : E11:
в B11 должна быть сумма ячеек B8 : B10;
в C11 должна быть сумма ячеек C8 : C10;
в D11 должна быть сумма ячеек D8 : D10;
в E11 должна быть сумма ячеек E8 : E10;
Целевую функцию поместим в ячейку G3:
G3: СУММПРОИЗВ (B3 : E5; B8 : E10).
Таблица исходных данных имеет вид (Рис.13):
Рис. 13
2) Заполнение окна процедуры «Поиск решения».
целевая функция : G3;
значение целевой функции : min;
изменяемые ячейки : B8 : E10;
ограничения задачи :
F8 : F10 = F3 : F5 (формулы (3)-(5))
B11 : E11 = B6 : E6 (формулы (6)-(9))
B8 : E10 >=0 (1) и B8 : E10 – целые числа (2)
В окне «Параметры» установить «Линейная модель». Результаты заполнения окна показаны на рис.14:
Рис.14
3) Выполнив процедуру «Поиск решения» получим следующие результаты:
Рис. 15
Таким образом, с железнодорожного вокзала (исходный пункт 1) следует 10 туристов отвезти в отель «Уютный» (пункт 4) и 5 туристов в отель «Солнечный» (пункт назначения 2); из аэропорта (исходный пункт 2) 10 туристов отвезти в отель «Солнечный» (пункт назначения 2) и 15 туристов в отель «Слава» (пункт назначения 3); туристов прибывающих на морской вокзал (исходный пункт 3) нужно отправить в отель «Морской» (пункт назначения 1). Все эти результаты видны в конечной таблице (рис.12) При этом суммарная стоимость транспортных расходов составит 315 рублей (ячейка G3).
Решение задачи в Excel (пример 3)