Математическая модель задачи

Лабораторная работа 5.

Транспортная задача

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

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

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

Пример. Фирма, обслуживающая туристов прибывающих на отдых, должна разместить их в 4 отелях: «Морской», «Солнечный», «Слава» и «Уютный», в которых забронировано соответственно 5, 15, 15 и 10 мест. Пятнадцать туристов прибывают по железной дороге, двадцать пять приле­тают очередным рейсом в аэропорт, а пять человек прибудут на теплоходе на морской вокзал. Транспортные расходы при перевозке из пунктов при­бытия в отели приведены в табл. 5.1.

Таблица 5.1.

Транспортные расходы при перевозке туристов из пунктов прибытия в отели, тыс. руб. на одного человека

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

Математическая модель задачи

1. Переменные задачи. Обозначимколичество туристов, которые будут перевозиться из пункта i в отель j как Х_ij (i = 1, 2, 3; j = 1, 2, 3, 4).Это переменные задачи, значения которых должны быть определены в процессе решения. Например, Х₂₃ – это число туристов, которое должно быть перевезено из аэропорта (пункта 2) в отель «Слава» (пункт 3). В задаче содержится 3х4 = 12 переменных.

2. Ограничения на переменные задачи. Очевидно, что все переменные задачи неотрицательные и целые числа, т.е.

Х_ij≥ 0, (1)

Х_ij – целые числа, (2)

где i = 1, 2, 3; j = 1, 2, 3, 4.

Кроме этого, должны удовлетворяться следующие условия. Число туристов, вывозимых с железнодорожного вокзала (пункт 1) равно 15, поэтому

Х₁₁ +Х₁₂ +Х₁₃ + Х₁₄ = Σ = 15. (3)

Аналогично, для аэропорта (пункт 2):

Х₂₁ +Х₂₂ +Х₂₃ + Х₂₄ = Σ =25, (4)

И для морского вокзала (пункт 3):

Х₃₁ +Х₃₂ +Х₃₃ + Х₃₄ = Σ =5, (5)

По условию задачи в отеле «Морской» (пункт 1) забронировано 5 мест, поэтому

Х₁₁ +Х₂₁ +Х₃₁ = Σ =5. (6)

Аналогично, для отеля «Солнечный» (пункт 2):

Х₁₂ +Х₂₂ +Х₃₂ = Σ =15. (7)

Для отеля «Слава» (пункт 3):

Х₁₃ +Х₂₃ +Х₃₃ = Σ =15. (8)

Для отеля «Уютный» (пункт 4):

Х₁₄ +Х₂₄ +Х₃₄ = Σ =10. (9)

Обычно транспортная задача записывается в виде таблицы, где в ячейках помещаются переменные задачи (Х_ij), а в правом верхнем углу ячейки стоят стоимости перевозки из пункта i в пункт j (С _ij). В крайнем правом столбце и нижней строке таблицы записываются числа определяющие ограничения задачи (в данном примере – это число туристов в исходных пунктах и число мест в пунктах назначения – отелях).

Для нашего примера таблица имеет вид (табл. 5.2.):

Таблица 5.2.

Транспортная задача в табличном виде

Транспортная задача, для которой суммы чисел в последнем столбце и нижней строке равны, называется сбалансированной: 15 + 25 + 5 = 45, 5 + 15 + 15 + 10 = 45. Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем стоимости перевозки в добавленных ячейках принимаются равными нулю.

Рассмотрим пример несбалансированной транспортной задачи. Предположим, что в аэропорт прибыло не пять, а десять туристов. Сумма чисел в последнем столбце будет равна: 15 + 25 + 10 = 50. Чтобы сбалансировать задачу вводим пятый столбец (фиктивный отель) с пятью местами. Таблица для сбалансированной транспортной задачи в этом случае будет иметь вид (табл. 5.3.):

Таблица 5.3.

Несбалансированная транспортная задача

3. Целевая функция. Вернемся к исходной задаче (табл. 5.2). Транспортные расходы на перевозку туристов в отели вычисляются по формуле:

Z = = 10 · X₁₁ + 0 · X₁₂ + 20 · X₁₃ + … + 18 · X_34. (10)

Окончательно транспортная задача имеет вид (табл. 2). Нужно найти такие значения переменных Х_ij (i = 1, 2, 3; j = 1, 2, 3, 4) при которых целевая функция, определяемая формулой (10), будет иметь минимальное значение и будет выполнены ограничения (1) – (9):

Х_ij≥ 0, где Х_ij – целые числа, i = 1, 2, 3; j = 1, 2, 3, 4.

Поиск по сайту: