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

 

Формируемые навыки и умения:

- изучение сущности модели транспортной задачи линейного программирования; - освоение методики построения и решения модели транспортной задачи линейного программирования.

 

Теоретическая поддержка

 

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

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

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

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

Экономико-математическая формулировка и модель транспорт­ной задачи имеют следующий вид.

Найти такие неотрицательные значения x_ij> 0, , которые минимизируют затраты на перевозку грузов:

при ограничениях

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

Вторая группа n равенств выражает условие, что спрос каждого потребителя полностью удовлетворяется.

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

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

а) когда предложение больше спроса, т. е. вводят «фиктивного» потребителя с заявкой и транспортными издержками .

При решении задачи часть товаров попадает к фиктивному потре­бителю, а фактически это означает, что этот груз останется на соот­ветствующей базе поставщика;

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

Четвертый тип ограничений (x_ij> 0) означает, что товары пере­возятся от поставщиков потребителям, т. е. исключаются встреч­ные перевозки.

Пример решения задачи

Постановка задачи . Пусть необходимо составить оптимальный план перевозки товара с трех баз А₁, А₂, А₃, товарные запасы которых составляют: а₁ = 180 т, а₂ = 150 т, а₃ = 80 т, в четыре магазина B₁, B₂, B₃, B₄ с заявками соответственно: b₁ = 120 т, b₂ = 110 т, b₃ = 80 т, b₄ = 140 т. Исходные данные задачи вместе с величинами транспортных издержек С_ij (ден. ед. за т) представлены в виде таблицы 2.1.

 

 

Таблица 2.1 – Исходные данные транспортной задачи

 

Поставщики (базы)	Потребители (магазины)	Запасы баз аi
B1	B2	B3	B4
A1	C11=15 х11=?	C12=3 х12=?	C13=7 х13=?	C14=12 х14=?
A2	C21=4 х21=?	C22=5 х22=?	C23=11 х23=?	C24=9 х24=?
A3	C31=10 х31=?	C32=8 х32=?	C33=2 х33=?	C34=6 х34=?
Заявки магазинов bj

Решение задачи

1 Экономико-математическая модель задачи

Определяем тип транспортной задачи путем проверки баланса запасов баз:

и заявок магазинов:

Равенство запасов и заявок соблюдается:

Значит, имеем транспортную задачу закрытого типа.

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

найти такие неотрицательные значения: x₁₁, x₁₂ x₁₃ x₁₄ x₂₁ x_22, x₂₃, x₂₄, x₃₁, x₃₂, x₃₃, x₃₄, которые бы давали минимум функции цели:

 

при следующих условиях:

- вывоз всех товаров с баз

- полное выполнение заказов магазинов

- исключение встречных перевозок

.

В таком виде экономико-математическая постановка задачи считается законченной.

2 Решение задачи с помощью инструмента Excel Поиск решения

Алгоритм решения задачи состоит из нескольких этапов:

1) Внести данные по издержкам С_ij в диапазон А1: F6 (таблица 2.2).

 

Таблица 2.2 - Ввод исходных данных

 

	А	B	C	D	E	F
	Поставщики	Потребители	Запасы поставщиков
	В1	В2	В3	В4
	А1
	А2
	А3
	Заявки потребителей

 

2) Создать на этом же листе Excel в диапазоне А8: F13 следующую таблицу (таблица 2.3). В качестве исходных значений Xij, i=1, 2, 3, j=l, 2, 3, 4 в блоке В10: Е12 можно взять нули.

 

Таблица 2.3 - Ввод ограничений

 

	А	B	C	D	E	F
	Поставщики	Потребители	Запасы поставщиков
	В1	В2	В3	В4
	А1					=СУММ(В10: Е10)
	А2					=СУММ(В11: Е11)
	А3					=СУММ(В12: Е12)
	Заявки потребителей	=СУММ (В10: В12)	=СУММ (С10: С12)	=СУММ (D10: D12)	=СУММ (Е10: Е12)	=СУММПРОИЗВ (В3: Е5; В10: Е12)

 

Чтобы сформировать формулы суммирования для ограничений, выделить блок B10: F13 (т. е. на 1 строку и на 1 столбец больше блока решений) и выполнить Автосуммирование на панели инструментов. В окаймляющие строку и столбец будут занесены формулы суммиро­вания по столбцам и строкам. Эти формулы и будут использованы для правых частей ограничений по потребителям и поставщикам в соответствии с таблицей 2.3.

3) Ввести функцию цели

Для этого в ячейку F13 занести формулу =СУММПРОИЗВ(В3: Е5; В10: Е12).

4) Выбрать команду Сервис → Поиск решения В окне По­иск решения внести:

• в поле Установить целевую ячейку — ссылку на F13;

• в поле Изменяя ячейки — ссылку на В10: Е12;

• установить переключатель на min;

• чтобы задать ограничения, нажать кнопку Добавить и добавить ограничения:

- по столбцам: В13=В6; С13=С6; D13=D6; E13=E6;

- по строкам: F10=F3; F11=F4; F12=F5;

- граничные: В10: E12> 0.

Нажать кнопку ОК, затем — Выполнить. Результаты решения представлены в таблице 2.4.

Таблица 2.4 - Результаты расчета

 

	А	B	C	D	E	F
	Поставщики	Потребители	Запасы поставщиков
	В1	В2	В3	В4
	А1
	А2
	А3
	Заявки потребителей

 

5) Результат сохранить в виде отчета Результаты.

Вывод: Минимальные транспортные издержки по перевозке груза составляют 2250 ден. ед. При этом база А₁ поставляет свой товар в магазины В₂ – 110 т, В₃ – 70 т; база А₂ поставляет товар в магазины В₁ – 120 т, В₄ – 30 т; база А₃ поставляет свой товар в магазины В₃ – 10 т, В₄ – 110 т. Запасы поставщиков полностью распределены, а заявки потребителей удовлетворены в полном объеме.

 

Задачи для самостоятельного решения

 

Задача 1

Четыре овощехранилища каждый день обеспечивают кар­тофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т. Тарифы (в д.е. за 1 т) указаны в следующей таблице 2.5.

 

Таблица 2.5 – Исходные данные

 

Овощехранилища	Магазины

 

Составьте план перевозок, минимизирующий суммарные транс­портные расходы.

Задача 2

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

.

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

 

Задача 3

Мясокомбинат имеет в своем составе четыре завода, на каждом из которых могут выпускать три вида колбасных изде­лий. Мощности каждого из заводов соответственно равны 320, 280, 270 и 350 т/сутки. Ежедневные потребности в колбасных изделиях каждого вида также известны и соответственно равны 450, 370 и 400 т. Себестоимость 1 т каждого вида колбасных изделий на каждом заводе определяются матрицей

.

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

Задача 4

ОАО «Универмаг «Центральный» получило предложение от фирм ОАО «Элема», ЗАО «Акмо», ОАО «Веснянка» на покупку пальто трех размеров 46-48, 50-52, 54-56. Стоимость пальто в зависимости от размеров и их количественное ограничение даны в таблице 2.6.

 

Таблица 2.6 – Исходные данные

 

Фирма	Размер	Ресурсы, шт.
46-48	50-52	54-56
ОАО «Элема»
ЗАО «Акмо»
ОАО «Веснянка»
Потребность, шт.

 

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

 

Задача 5

Фирма реализует продукцию в пяти торговых точках. Покупательский спрос жителей этих областей оценивается в соответствующих единицах и задан в таблице 2.7. В этой же таблице представлен профессиональный уровень каждого i-го продавца значениями С_i как доля реализуемых покупательских способностей.

 

Таблица 2.7 – Исходные данные

 

Объект	I	II	III	IV	V
Спрос
Продавец
Доля Сi	0, 7	0, 6	0, 5	0, 45	0, 4

 

Требуется распределить продавцов по объектам так, чтобы обеспечить максимальную реализацию продукции.

 

12345678910Следующая ⇒

Поделиться: