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

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

Оптимизация транспортных потоков

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

Ниже сформулируем транспортную задачу.

Ткацкая фабрика имеет три склада А1, А2, А3, на которых сосредоточены запасы произведенной продукции а1, а2, а3 единиц товара. Фабрика имеет также пять фирменных магазинов В1, В2, В3, В4, В5, потребность которых ‑ b1, b2, b3, b4, b5 единиц товара. Стоимость перевозки единицы товара из пункта А i (i=1,2,...,m) в пункт B k (k=1,2,...,n) составляет C i k рублей.

Составить такой план перевозок товара, чтобы были выполнены заявки всех магазинов и при этом суммарная стоимость всех перевозок была минимальна.

Если сумма всех запасов равна сумме всех заявок:

,

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

Дадим задаче математическую формулировку.

Обозначим через х i k количество товара, перевозимого со склада Аi в магазин В k (i=1,2,...,m; k=1,2,...,n). Таким образом, в задаче имеется m´n переменных, которые предполагаются неотрицательными и должны удовлетворять следующим условиям:

x11+x12+...+x1n= a1

x21+x22+...+x2n= a2 (5.1)

...........................

xm1+xm2+...+xmn= am

x11+x21+...+xm1= b1 (5.2)

x12+x22+...+xm2= b2

..............................

x1n+x2n+...+xmn= bn

При этом суммарная стоимость всех перевозок должна быть минимальна:

(5.3)

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

Таблица 5.1

	Магазин
Склад	В1	В2	В3	В4	В5	Запас
А1	x11	x12	x13	x14	x15	a1
А2	x21	x22	x23	x24	x25	a2
А3	x31	x32	x33	x34	x35	a3
Заявка	b1	b2	b3	b4	b5

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

Последовательность выполнения работы:

1.  Составить транспортную таблицу.

2.  Формализовать целевую функцию и ограничения

3.  Решить задачу оптимизации, определив оптимальный план перевозок, обеспечивающий их минимальную стоимость.

Исходные данные

Таблица 5.2

	Показатель	Матрица
Вар.	a1	a2	a3	b1	b2	b3	b4	b5	тарифов
1	300	280	220	180	140	190	120	170	1 19 10
2	250	200	150	180	120	90	105	105	1 1 19
3	150	220	130	160	70	90	80	100	8 4 15
4	280	300	220	170	120	190	140	180	28 35 30
5	150	250	200	180	120	90	105	105	1 17 15
6	250	400	350	300	160	220	180	140	9 15 16
7	150	150	200	100	70	130	110	90	2 14 25
8	280	220	300	150	140	190	130	190	3 15

Продолжение табл. 5.2

	Показатель	Матрица
Вар.	a1	a2	a3	b1	b2	b3	b4	b5	тарифов
9	400	250	350	200	170	230	225	175	15 17 1
10	200	250	150	180	120	90	105	105	12 13 19
11	200	250	150	120	180	105	90	105	1
12	250	250	200	120	110	85	195	190	1 2
13	250	280	170	160	120	100	150	170	1 1
14	350	300	350	160	160	180	220	280	6 1 1
15	250	350	300	150	170	190	210	180	13 19
16	220	400	280	160	180	170	220	190	20 6
17	160	400	240	170	190	140	180	120	16 1
18	300	330	370	190	150	240	200	220	1 21 19
19	280	340	280	170	160	190	200	180	15 10
20	250	270	380	140	170	200	160	230	1 4 10

Выполнение работы в среде Excel

Для решения транспортной задачи в Excel создадим транспортную таблицу на рабочем листе ЭТ. Клетки этой таблицы, соответствующие переменным xik, оставим незаполненными. Транспортная таблица содержит часть исходных данных, к которым относятся запасы товара на складах и заявки магазинов. Оставшиеся исходные данные внесем в виде матрицы тарифов на перевозки (табл.5.3).

Таблица 5.3

Матрица тарифов

С11	С12	С13	С14	С15
С21	С22	С23	С24	С25
С31	С32	С33	С34	С35

На этом завершается формирование блока исходных данных.

Расчетный блок должен содержать ячейки переменных, ячейку целевой функции и ячейки ограничений. Ячейки под переменные зарезервированы нами в транспортной таблице (см. табл.5.1). Осталось заполнить ячейку целевой функции, внеся в нее формулу уравнения (5.3), и ячейки ограничений, внеся в них формулы ограничений (5.1), (5.2).

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

Таким образом, в ограничениях (5.1) вместо знака равенства следует поставить знак £, а в ограничениях (5.2) ‑ знак ³.

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

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

В диалоговом окне Поиск решения имеется кнопка Параметры, при нажатии которой открывается диалоговое окно Параметры поиска решения. Для решения данной задачи следует изменить только величину относительной погрешности, увеличив ее до 0,01. Меньшая погрешность не нужна для решения задачи и создает для компьютера слишком жесткие условия.

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

Контрольные вопросы

1.  Особенности транспортной задачи в ряду задач распределения ресурсов.

2.  Какая транспортная задача называется сбалансированной?

3.  Каким способом решается несбалансированная транспортная задача?

Библиографический список

1.  Курицкий вокруг нас. – Л.: Машиностроение,1989, – С. 32–36.

2.  Курицкий оптимальных решений средствами Excel 7.0. – BHV‑Санкт-Петербург, 1997, – С. 275–284.

Пример оформления работы 5 представлен в приложении.