Технология решения транспортной задачи

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

Производство продукции осуществляется на четырех предприятиях, а затем развозится в 5 пунктов потребления. Предприятия могут выпускать в день 235, 175, 185 и 175 единиц продукции. Пункты потребления готовы принимать ежедневно 125, 160, 60, 250 и 175 единиц продукции. Хранение на предприятии единицы продукции обходится в 2 у. е. в день, штраф за недопоставленную продукцию – 3,5 у. е. в день. Стоимость перевозки единицы продукции (в у. е.) с предприятий в пункты потребления приведена в табл.1.1.

 

Таблица 1.1. Транспортные расходы

Предприятия	Пункты потребления
	3,2		2,35		3,65
	3,0	2,85	2,5	3,9	3,55
	3,75	2,5	2,4	3,5	3,4
			2,1	4,1	3,4

 

Решение задачи сводится к реализации следующих этапов:

1. Проверка сбалансированности модели задачи. Модель является сбалансированной, т. к. суммарный объем производимой продукции в день равен суммарному объему потребности в ней:

235 + 175 + 185 + 175 = 125 + 160 + 60 + 250 + 175.

2. Построение математической модели. Неизвестными в этой задаче являются объемы перевозок. Пусть x_ij – объем перевозок с i -го предприятия в j -й пункт потребления; a_i – объем производства на i -м предприятии; b_j – спрос в j -м пункте потребления; c_ij – стоимость перевозки единицы продукции с i -го предприятия в j -й пункт потребления. Суммарные транспортные расходы – это функционал качества (критерий цели):

 

 

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

3. Решение задачи с помощью окна Поиск решения:

- подготовка рабочего листа для задачи (рис. 1.10). Формулы для расчета приведены в табл. 1.25;

Рис. 1.10. Исходные данные для решения транспортной задачи

 

Таблица 1.2. Формулы для расчета в транспортной задаче

Описание	Ячейка	Формула
Ограничения_1	G11	=CУMM(B11:F11)
	G12	=СУММ(В12:F2)
	G13	=СУММ(В13:F.З)
	G14	=СУММ(В14:F4)
Ограничения_2	В15	=СУММ(В11:В14)
	С15	=СУММ(С11:С14)
	D15	=CУMM(D11:D14)
	Е15	=СУММ(Е11:Е14)
	F15	=CУMM(F11:F14)
Целевая функция	В19	=СУММПР0ИЗВ (B5:F8;B11:F14)

 

- ввод данных в окно Поиск решения ( рис. 1.11);

Рис. 1.11. Ввод данных в окно Поиск решения для транспортной задачи

 

- результат решения представлен на рис. 1.12.

Рис. 1.12. Оптимальное решение для транспортной задачи

 

 

1.4.Задачи для самостоятельной работы

№1. Необходимо составить оптимальный график работы служащих фирмы, занимающейся грузоперевозками, с учетом минимума издержек на заработную плату, учитывая установленный график работы персонала. Известно, что в офисе фирмы требуется в понедельник - четверг не менее 8 работников, в пятницу и субботу – не менее 10 работников, в воскресенье – не менее 12 работников. Причем должен соблюдаться следующий рабочий график: каждый сотрудник работает 6 дней в неделю с одним выходным.

Дневная оплата сотрудников составляет 650 руб. для графиков работы с выходными в субботу или воскресенье и 600 руб. – с выходными в другие дни (без учета премиальных и комиссионных). Изменится ли график работы персонала, если дневная оплата для всех сотрудников будет 600 руб.?

№2. Для обслуживания парка компьютеров в автотранспортном предприятии требуется не менее пяти человек в день: 4 оператора ЭВМ, администратор. Нагрузка на использование компьютеров возрастает со среды по пятницу, причем нагрузка распределяется таким образом, что основной пик приходится на четверг. Поэтому в эти дни требуются дополнительные человекоресурсы – по 1 сотруднику в среду и пятницу и 2 сотрудника в четверг. Таким образом, получается, что максимальное количество работников в смену составляет 7 человек. Причем должен соблюдаться следующий рабочий график: каждый сотрудник работает 5 дней в неделю с двумя выходными подряд. Дневная оплата сотрудников составляет 750 руб. (без учета премиальных и комиссионных). Рассчитайте минимальную недельную заработную плату сотрудников. Определите оптимальное количество человек в смену для обслуживания парка компьютеров с учетом минимума издержек на заработную плату, учитывая установленный график работы персонала.

№3. Для обслуживания клиентов и организации работы в крупном автотранспортном предприятии требуется не менее 100 человек в день. Нагрузка на использование оборудования снижается с пятницы по воскресенье, т.е. в выходные дни, причем нагрузка распределяется таким образом, что основной спад приходится на воскресенье. Поэтому в выходные дни количество работающих уменьшается – по 15 сотрудников в пятницу и субботу и 20 сотрудников в воскресенье. При составлении расписания должен соблюдаться следующий рабочий график: каждый сотрудник работает 5 дней в неделю с двумя выходными подряд. Дневная оплата сотрудников составляет 550 руб. Рассчитайте минимальную недельную заработную плату сотрудников. Определите оптимальное количество человек в смену для обслуживания клиентов предприятия с учетом минимума издержек на заработную плату, учитывая установленный график работы персонала.

№4. Управление городским автобусным парком решило провести исследование возможности более рациональной организации своей работы с целью снижения интенсивности внутригородского движения. Сбор и обработка необходимой информации позволили сделать вывод, что необходимое минимальное количество автобусов существенно меняется в течение суток (рис.1.13). Длительность непрерывного использования автобусов на линии равна 8 ч в сутки (с учетом необходимых затрат времени на текущий ремонт и обслуживание). График перекрывающихся смен представлен на рис.1.14.

 

 

Рис.1.13. Минимально необходимое количество автобусов на линии

 

 

Рис.1.14 График перекрывающихся смен

 

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

 

№5 (по вариантам).

Имеются п пунктов производства и m пунктов распределения продукции. Стоимость перевозки единицы продукции из i -го пункта производства в j -й центр потребления c_ij приведена в таблицах, где под строкой понимается пункт производства, а под столбцом – пункт потребления. Кроме того, в таблицах в i -й строке указан объем производства в i -м пункте, а в j -м столбце указан спрос в j -м центре потребления. Хранение продукции на предприятии обходится в 1,6 у.е. в день, а штраф за просроченную поставку единицы продукции, заказанной в пункте потребления, но там не хранящейся, равен 34 у.е. в сутки. Составить план перевозок по доставке требуемой продукции в пункты потребления, минимизирующий суммарные транспортные расходы. Необходимые данные для решения задач взять из соответствующих таблиц по вариантам.

 

Вариант 1

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А		1,8
В		5,1
С	3,5			3,1
D	2,2	4,9	1,3
Е			8,95
Объемы потребления

 

Вариант 2

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	2,3
В		1,3		2,5
С	4,9
D
Е		2,1	1,2
Объемы потребления

Вариант 3

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А			4,1
В		2,5
С				4,2
D	5,1
Объемы потребления

Вариант 4

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	1,7
В	5,2	2,6	9,8
С
D			2,5
Объемы потребления

Вариант 5

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А			4,8
В
С	5,5
D			8,2
Е	1,8
Объемы потребления

 

Вариант 6

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	6,2		4,2
В			5,1
С
D
Е		2,75
Объемы потребления

 

Вариант 7

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А
В
С
D
Объемы потребления

Вариант 8

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А				7,4
В
С		2,2
D	2,5
Объемы потребления

 

Вариант 9

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	6,3	8,6
В	2,5
С
D
Объемы потребления

Вариант 10

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	7,3
В
С
D
Е	4,8
Объемы потребления

Вариант 11

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	6,3
В
С
D		5,5
Е
Объемы потребления

 

Вариант 12

Предприятия	Стоимость перевозки единицы продукции	Объем производства
Пункты потребления
А	4,2
В
С				7,3
D
Е
Объемы потребления

 

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

1. Какие задачи относятся к задачам линейного программирования?

2. С помощью какого инструмента в Excel можно использовать симплекс-метод?

3. Опишите технологию решения задачи линейного программирования средствами Excel.

4. Опишите параметры окна Параметры поиска решения задачи.

5. Опишите технологию решения транспортной задачи средствами Excel.

6. Что представляют собой суммарные транспортные расходы?

7. Сто такое целевая функция?

8. Опишите параметры окна Поиск решения.

 

Домашнее Задание №2.