Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов изготовления (например, заводов) в пункты доставки (например, склады).
Транспортная модель может применяться при рассмотрении практических ситуаций, связанных с управлением запасами, составлением именных графиков, назначением служащих не рабочие места, оборотом наличного капитала.
Транспортная задача может быть сведена к задаче линейного программирования и решена симплекс-методом. Вместе с тем специфика транспортной задачи позволяет решить ее более эффективным методом. Однако, и этот метод по существу воспроизводит шаги симплекс-метода.
Определение транспортной модели
При построении транспортной модели используются:
Заметим, что потребности одного пункта назначения могут удовлетворяться из нескольких исходных пунктов, так же один пункт производства может поставлять товар в несколько пунктов потребления.
Цель построения модели заключается в определении количества продукции, которую следует перевозить из всех исходных пунктов в пункты потребления при минимальных общих транспортных расходах.
Основное предположения транспортной модели состоит в том, что величина расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции.
Рассмотрим графическое представление транспортной модели
Рисунок 6
Транспортная модель такого вида
называется сетевой и имеет mисходных пунктов иnпунктов назначения. Исходные пункты и
пункты назначения называются вершинами
сети или соответствующего графа. Маршрут
по которому перевозится продукция
называется дугой, количество продукции,
производимая вi-ом исходно
пункте обозначается
.
Количество потребляемой продукции вj-ом пункте -
.
Стоимость перевозки
.
Соответствующую математическую модель можно записать в следующем виде:
Iотражает тот факт, что суммарный объем перевозок из некоторого исходного пункта не может превышать произведенного в этом пункте количества продукции.
IIпоказывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворять потребность в спросе на эту продукцию.
Анализ транспортной модели показывает, что суммарный объем производства не должен быть меньше объема потребления.
В том случае, если что суммарный объем производства равен суммарному объему потребления, транспортная модель называется сбалансированной.
Такая модель является канонической моделью линейного программирования.
Пример транспортной модели
Заводы автомобильной фирмы расположены в Лос-Анджелесе, Детройте и Нью-Орлеане. Центры распределения в Денвере и Майами. Объем производства заводов 1000, 1500 и 1200 автомобилей соответственно. Ожидаемый спрос равен 2300 и 1400 автомобилей соответственно.
Стоимость перевозки одного автомобиля приведена в таблице 10:
Таблица 10
- количество автомобилей, которые
перевозят изi-ого пункта
вj-ый (i=1,2,3;j=1,2).
Суммарный объем производства автомобилей равен 3700 и равняется суммарному ожидаемому спросу. Следовательно, данная транспортная модель является сбалансированной и ее можно записать в следующем виде:
при ограничениях
Компактный способ записи транспортной модели связан с использованием транспортной таблицы или матрицы, у которой соответствуют исходным пунктам, а столбцы пунктам спроса.
Транспортная модель (транспортная задача) используют при рассмотрении различных практических ситуаций в логистическом управлении, связанных: с составлением наиболее экономичного плана перевозок продукции, управление запасами, назначением служащих на рабочее места, оборотом наличного капитала и многими другими. Кроме того, модель можно изменить, чтобы она учитывала перевозку нескольких видов продукции. В то же время транспортная модель и ее обобщение представляют собой частные случаи сетевых моделей.
Транспортная задача по существу представляет собой задачу линейного программирования, которую можно решать симплекс – методом. Однако специфическая структура условий задачи позволяет использовать более эффективные вычислительные алгоритмы.
Сущность транспортной задачи линейного программирования состоит в наивыгоднейшем прикреплении поставщиков однородного продукта ко многим потребителям этого продукта. На практике постоянно возникает необходимость решения таких задач, особенно когда количество пунктов отправления и получения грузов увеличивается.
Условие транспортной задачи обычно записывается в виде матрицы, в которой потребители однородного груза размещаются по столбцам, а поставщики - по строкам. В последнем столбце матрицы проставляют запас груза, имеющийся у каждого поставщика, а в последней строке - потребность в нем потребителей. На пересечении строк со столбцами (в клетках матрицы) записывают размер поставки, а также расстояние пробега по всем возможным маршрутам время доставки груза или затраты на перевозку единицы груза по этим маршрутам.
Постановка задачи и ее математическая модель. Некоторый однородный продукт, сосредоточенный у т поставщиков в количестве (), необходимо доставить п потребителям в количестве (). Известно стоимость перевозки единицы груза от го поставщика му потребителю. Необходимо составить план перевозок, имеющий минимальную стоимость. Основное предположение, используемое при построении модели, состоит в том, что величина транспортных расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции. Модель транспортной задачи представлена на рис 7.1.
| m |
| n |
Рис. 7.1. Транспортная модель
На рис. 7. 1. изображена транспортная модель в виде сети с т поставщиками некоторого однородного груза и п потребителями этого груза. При этом поставщикам груза и потребителям соответствуют вершины сети. Дуга, соединяющая поставщик груза с потребителем, представляет условный маршрут, по которому перевозится продукция. Количество продукции, производимой поставщиком , обозначено через , а количество продукции, потребляемой потребителем через ; стоимость перевозки единицы продукции из в .
Запишем математическую модель задачи:
1) Объем поставок го поставщика должен равняться количеству имеющегося у него груза:
2) Объем поставок му потребителю должен быть равен его спросу:
3) Запас груза у поставщиков должен равняться суммарному спросу потребителей:
4) Размер поставок должен выражаться неотрицательным числом:
5) общая сумма затрат на перевозку груза должна быть минимальной:
Поставленная в задаче цель может быть достигнута различными методами, например, методом северо-западного угла или методом потенциалов.
Модель транспортной задачи линейного программирования так же может использоваться для планирования ряда операций, не связанных с перевозкой грузов. Так, с ее помощью решаются задачи по оптимизации размещения производства, топливно-энергетического баланса, планов загрузки оборудования распределения сельскохозяйственных культур по участкам различного плодородия и т. п.
Поставленная транспортная задача линейного программирования называется сбалансированной транспортной моделью, так как объем запасов равняется объему заказов. В реальных ситуациях не всегда объем производства равен спросу, однако транспортную модель всегда можно сбалансировать.
В случае превышения запас продукции над потребностью, т. е. если , вводится фиктивный (n+1) – й потребитель с потребностью
а соответствующие стоимости перевозок считаются равными нулю. Аналогично, при , вводится фиктивный (m+1) – й поставщик с запасом груза а соответствующие стоимости перевозок считаются равными нулю. Этими действиями задача сводится к сбалансированной транспортной задаче, из оптимального плана которой, получается оптимальный план исходной задачи.
Модель транспортной задачи представляет собой задачу линейного прогпаммирования и, етественно, ее можно решать с использованием метода последовательного улучшения плана или методом использованием метода последовательного улучшения оценок (симплексным методом). Но в этом случае основная трудность связана с числом переменных задачи . Поэтому специальные алгоритмы, например, такие как метод потенциалов и венгерский метод, оказываются более эффективными.
Алгоритм метода потенциалов, (его называют еще модифицированным распределительным алгоритмом) начинает работу с некоторого опорного плана транспортной задачи (допустимого плана перевозок). Для построения опорного плана обычно используется один из двух методов: метод северо-западного угла или метод минимального элемента. На конкретной задаче рассмотрим метод северо-западного угла. Он позволяет найти некоторый допустимый план перевозок.
Задача. На трех складах () имеется соответственно 140, 180 и 160 единиц однородного груза. Этот груз требуется перевести к пяти потребителям () соответственно в количествах 60, 70, 120, 130, 100 единиц. Стоимость перевозки от складов к потребителям приведена в табл. 7.2. (в правом верхнем углу каждой клетки). Например, стоимость перевозки единицы груза со склада потребителю равна 2 у. е.
Таблица 7.2
Исходные данные для решения транспортной задачи
| Поставщики | Потребители | Запасы продукции | ||||
| Потребности |
Найти допустимый план перевозок.
Для решения задачи на первом этапе составляется система ограничений и целевая функция. Система ограничений в общем виде (для задачи) имеет вид:
причем для
Целевая функция затрат на перевозку, значение которой необходимо минимизировать при имеющихся ограничениях, выглядит следующим образом:
2 + 3 +4. + 2 + 4 + 2 , (92)
Далее перераспределяются объемы поставок грузов методом «северо-западного угла», т.е. первой заполняется верхняя левая (северо-западная) клетка исходной таблицы. Примем объем перевозки со склада к потребителю максимально возможным из условий задачи и равным 60 ед. Потребитель полностью удовлетворил свою потребность, и поэтому графу « » в табл.7.3 можно исключить из дальнейшего рассмотрения.
В таблице 7.3. найдем «северо-западный угол» (теперь это клетка )и укажем максимально возможное значение. Оно рассчитывается следующим образом: со склада уже перевезено 60 ед. груза, поэтому остаток на этом складе составляет 80 ед. (140-60). Вносим в клетку вместо значение, равное 70 ед. Потребитель полностью удовлетворил свою потребность, и поэтому графу « » в табл. 7.3. можно исключить из дальнейшего рассмотрения. Остаток продукции на складе 10 ед. (140 – 60 – 70) припишем потребителю .Таким образом, весь груз со склада перевезен потребителям и первая строка табл. 7.3 исключается из дальнейшего рассмотрения.
В нашей табл.7.3 найдем новый «северо-западный угол» (клетка )и укажем в нем максимально возможное значение это 110 ед. (120 – 10). Остаток продукции на складе 70 ед. (180 – 110) припишем потребителю . Тем самим потребитель полностью удовлетворил свою потребность, и поэтому графу « » в табл. 7.3 можно исключить из дальнейшего рассмотрения.
В оставшейся части табл. № найдем новый «северо-западный угол» (клетка ) и укажем в нем максимально возможное значение это 60 ед. (130 – 70). Остаток продукции на складе в количестве 100 ед. припишем потребителю .
Одной из типичных задач линейного программирования является так называемая транспортная задача. Она возникает при планировании наиболее рациональных перевозок грузов. В одних случаях это означает определение такого плана перевозок, при котором стоимость последних была минимальной, а в других – более важным является выигрыш времени. Первая задача получила название транспортной задачи по критерию стоимости , а вторая – транспортная задача по критерию времени .
Первая задача является частным случаем задачи линейного программирования и может быть решена симплексным методом.
Пусть в p пунктахотправления находится соответственноa 1 , a 2 , a 3 …a p единиц однородного груза, который должен быть доставленq потребителямв количествах b 1 , b 2 , b 3 …b q единиц.Заданы стоимостиc ik перевозок единицы груза изi - го пункта отправленияk –му пункту потребления.
Обозначим x ik ³ 0 (i = 1, 2…p; k = 1, 2…q)количество единиц груза, перевозимого из i -госкладаk -му потребителю; тогда переменныеx ik должны удовлетворятьследующим ограничительным условиям:
1) (i = 1, 2 …p);
2) 
(k = 1, 2…q);
3) x ik ³ 0
Суммарные затраты на перевозки будут равны
L = c 11 x 11 + c 12 x 12 + c 13 x 13 + …+ c pq x pq .
Следовательно, требуется найтиpq переменных x ik , удовлетворяющих указанным условиям и минимизирующих целевую функцию.
§ Пример
В двух пунктах отправления А и В находится соответственно 150 и 90 тонн горючего. Складам №1, 2, и 3 требуется соответственно 60, 70 и 110 тонн горючего. Стоимость перевозки одной тонны горючего из пункта А на склады №1, 2 и 3 соответственно 6, 10 и 4 гривны за тонну горючего, а из пункта В – 12, 2 и 8 гривен. Составить оптимальный план перевозок горючего, чтобы общая сумма транспортных расходов была наименьшей.
Решение.
Обозначим:
x11 - количество горючего, которое может быть поставлено из пункта А на склад №1;
x12 - количество горючего, которое может быть поставлено из пункта А на склад №2;
x13 - количество горючего, которое может быть поставлено из пункта А на склад №3;
x21 - количество горючего, которое может быть поставлено из пункта B на склад №1;
x22 - количество горючего, которое может быть поставлено из пункта B на склад №2;
x23 - количество горючего, которое может быть поставлено из пункта B на склад №3;
c 11 = 6 – стоимость единицы количества x 11 горючего, перевозимого из пункта А на склад №1;
с 12 = 10 - стоимость единицы количества x 11 горючего, перевозимого из пункта А на склад №2;
с 13 = 4 - стоимость единицы количества x 11 горючего, перевозимого из пункта А на склад №3;
с 21 = 12 - стоимость единицы количества x 11 горючего, перевозимого из пункта В на склад №1;
с 22 = 2 – стоимость единицы количества x 11 горючего, перевозимого из пункта В на склад №2;
с 23 = 8 - стоимость единицы количества x 11 горючего, перевозимого из пункта А на склад №3.
Тогда линейная функция, отражающая общую сумму транспортных расходов, имеет вид
L = c 11 x 11 + c 12 x 12 + c 13 x 13 + c 21 x 21 + c 22 x 22 + c 23 x 23 .
Составляем ограничивающие условия:
x 11 ³ 0, x 12 ³ 0, x 13 ³ 0, x 21 ³ 0, x 22 ³ 0, x 23 ³ 0.
x 11 + x 12 + x 13 = 150 --- уравнение, отображающее, что в пункте А находится 150 единиц горючего;
x 21 + x 22 + x 23 = 90 --- уравнение, отображающее, что в пункте B находится 90 единиц горючего;
x 11 + x 21 = 60 --- уравнение, отображающее, что на склад №1 из пунктов А и В требуется 60 единиц горючего;
x 12 + x 22 = 70 --- уравнение, отображающее, что на склад №2 из пунктов А и В требуется 70 единиц горючего;
x 13 + x 23 = 110 --- уравнение, отображающее, что на склад №3 из пунктов А и В требуется 110 единиц горючего;
Решение задачи заключается в необходимости минимизировать линейную функцию L при ограничивающих условиях.
Решим транспортную задачу используя MATHCAD.
Задаем ценовые параметры
Формируем линейную функцию
Задаем произвольные начальные условия
Блок решения
Записываем ограничивающие условия
Задаем оператор минимизации линейной формы
Находим оптимальной решение
Минимальная сумма транспортных расходов
Варианты индивидуальных контрольных заданий №6 (кратно 4)
1. На двух складах А и В находится по 90 тонн горючего. Перевозка одной тонны горючего со склада А в пункты №1, 2, 3 соответственно стоят 1, 3 и 5 гривен. Перевозка одной тонны горючего со склада В в те же пункты стоит соответственно 2, 4 и 5 гривен. В каждый пункт надо доставить по одинаковому количеству тонн горючего. Составить такой план перевозки горючего, при котором транспортные расходы будут наименьшими.
2. В резерве трех железнодорожных станций А, В и С находятся соответственно 60, 80 и 100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам погрузки хлеба, если пункту №1 необходимо 40 вагонов, №2 – 60 вагонов, №3 – 80 вагонов и №4 – 60 вагонов. Стоимость перегона одного вагона со станции А в указанные пункты соответственно равна 1, 2, 3 и 4 гривны. Стоимость перегона одного вагона со станции В в указанные пункты соответственно равна 4, 3, 2 и 0 гривен. Стоимость перегона одного вагона со станции С в указанные пункты соответственно равна 0, 2, 2 и 1 гривны.
3. Завод имеет три цеха А, В и С и четыре склада №1, №2, №3, №4. Цех А производит 30 тысяч штук изделий, цех В – 40 тысяч штук изделий, цех С – 20 тысяч штук изделий. Пропускная способность складов за то же время характеризуется следующими показателями: склад №1 – 20 тысяч штук изделий, склад №2 – 30 тысяч штук изделий, склад №3 – 30 тысяч штук изделий, склад №4 – 10 тысяч штук изделий. Стоимость перевозки из цеха А соответственно в склады №1, 2, 3, 4 за одну тысячу изделий соответственно равна 20, 30, 20 и 40 гривен; стоимость перевозки из цеха В соответственно в склады №1, 2, 3, 4 равна 30, 20, 50 и 10 гривен за одну тысячу изделий; а стоимость перевозки одной тысячи изделий из цеха С в склады №1, 2, 3, 4 соответственно равна 40, 30, 20 и 60 гривен. Составить такой план перевозки изделий, при котором расходы на перевозку 90 тысяч изделий был бы наименьшим.
4. На трех складах А, В и С находится сортовое зерно соответственно 10, 15 и 25 тонн, которое надо доставить в четыре пункта: пункту №1 – 5 тонн, пункту №2 – 10 тонн, пункту №3 – 20 тонн и пункту №4 – 15 тонн. Стоимость доставки одной тонны со склада А в указанные пункты соответственно равна 8 000, 3 000, 5 000, 2 000 гривен. Стоимость доставки одной тонны со склада В в указанные пункты соответственно равна 4 000, 1 000, 6 000, 7 000 гривен. Стоимость доставки одной тонны со склада С в указанные пункты соответственно равна 1 000, 9 000, 4 000, 3 000 гривен. Составить оптимальный план перевозки зерна в четыре пункта, минимизирующий стоимость перевозок.
Литература
1. Эконометрика: Учебник / Под ред. И.И. Елисеевой. – М.: Финансы и статистика, 2002. – 344 с.
2. Практикум по эконометрике: Учебн. пособие / Под ред. И.И. Елисеевой. – М.: Финансы и статистика, 2003. – 192 с.
3. Доугерти К. Введение в эконометрику: Пер. с англ. – М.: ИНФРА-М, 1999. – 402 с.
4. Кремер Н.Ш., Путко Б.А. Эконометрика: Учебник для вузов / Под ред. проф. Н.Ш. Кремера. – М.: ЮНИТИ-ДАНА, 2002. – 311 с.
5. Магнус Я.Р., Катышев П.К., Пересецкий А.А. Эконометрика. Начальный курс: Учебник. – М.: Дело, 2001. – 400 с.
6. Катышев П.К., Магнус Я.Р., Пересецкий А.А. Сборник задач к начальному курсу эконометрики. – М.: Дело, 2002. – 208 с.
7. Сборник задач по эконометрике: Учебное пособие для студентов экономических вузов / Сост. Е.Ю. Дорохина, Л.Ф. Преснякова, Н.П. Тихомиров. – М.: Издательство «Экзамен», 2003. – 224 с.
Frisch R. Editorial. Econometrica. – 1933. – № 1. – P. 2.
Более подробно смотри Приложение A.
Подробнее об автокорреляции см. в разделе 4.
Под названием транспортная задача объединяется широкий круг задач с единой матетической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены известным симплексным методом. Однако, обычная транспортная задача имеет большое число переменных и решение ее симплексным методом громозко. С другой стороны матрица системы ограничений транспортной задачи весьма своеобразна, поэтому для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить последовательность опорных решений, которая завершается оптимальным решением.
Общая характеристика транспортной задачи
Условие:
Однородный груз сосредоточен у m поставщиков в объемах a 1 , a 2 , ... a m .
Данный груз необходимо доставить n потребителям в объемах b 1, b 2 ... b n .
Известны C ij
, i=1,2,...m; j=1,2,...n — стоимости перевозки единиц груза от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью, и суммарные затраты на перевозку всех грузов являются минимальными.
Исходные данные транспортной задачи записываются в виде таблицы:
Исходные данные задачи могут быть представлены в виде:
- вектора А=(a 1 ,a 2 ,...,a m) запасов поставщиков
- вектора B=(b 1 ,b 2 ,...,b n) запросов потребителей
- матрицы стоимостей:
Математическая модель транспортной задачи
Переменными (неизвестными) транспортной задачи являются x ij , i=1,2,...,m j=1,2,...,n — объемы перевозок от i-го поставщика каждому j-му потребителю.
Эти переменные могут быть записаны в виде матрицы перевозок:
Так как произведение C ij *X ij определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны:
По условию задачи требуется обеспечить минимум суммарных затрат.
Следовательно, целевая функция задачи имеет вид:
Система ограничений задачи состоит из двух групп уравнений.
Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью и имеет вид:
Вторая группа из n уравнений выражает требование удовлетворить запросы всех n потребителей полностью и имеет вид:
Учитывая условие неотрицательности объемов перевозок математическая модель выглядит следующим образом:
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарынм запросам потребителей, т.е.:
Такая задача называется задачей с правильным балансом , а модель задачи закрытой . Если же это равенство не выполняется, то задача называется задачей с неправильным балансом , а модель задачи — открытой .
Пример 34.1Математическая формулировка транспортной задачи такова: найти переменные задачи X=(x ij), i=1,2,...,m; j=1,2,...,n, удовлетворяющие системе ограничений (цифра 2 на математической модели) , (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1)
Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице 34.2
Решение:
1. Вводим переменные задачи (матрицу перевозок):
2. Записываем матрицу стоимостей:
3. Целевая функция задачи равняется сумме произведений всех соответствующих элементов матриц C и X.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
4. Составим систему ограничений задачи.
Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам первого поставщика, а сумма перевозок во второй строке матрицы X равняться запасам второго поставщика:
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:
Это означает, что запросы потребителей удовлетворяются полностью.
Необходимо также учитывать, что перевозки не могут быть отрицательными:
Ответ
: Таким образом, математическая модель рассматриваемой задачи записывается следующим образом:
Найти переменные задачи, обеспечивающие минимум целевой функции (1) и удовлетворяющие системе ограничений (2) и условиям неотрицательности (3).
Рассматривается транспортная модель и ее варианты. Такая модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов (например, заводов) в пункты доставки (например, склады). Транспортную модель можно применять при рассмотрении ряда практических ситуаций, связанных с управлением запасами,
составлением сменных графиков, назначением служащих на рабочие места, оборотом наличного капитала, регулированием расхода воды в водохранилищах и многими другими. Кроме того, модель можно видоизменить, с тем чтобы она учитывала перевозку нескольких видов продукции.
Транспортная задача представляет собой задачу линейного программирования, однако ее специфическая структура позволяет так модифицировать симплекс-метод, что вычислительные процедуры становятся более эффективными. При разработке метода решения транспортной задачи существенную роль играет теория двойственности.
В классической транспортной задаче рассматриваются перевозки (прямые или с промежуточными пунктами) одного или нескольких видов продукции из исходных пунктов в пункты назначения. Эту задачу можно видоизменить, включив в нее ограничения сверху на пропускные способности транспортных коммуникаций. Задачу о назначениях и задачу управления запасами можно рассматривать как задачи транспортного типа.
Пример
. В пунктах отправления А 1 , А 2 , А 3 находится однородный груз в количестве a 1 , а 2 , а 3 , соответственно, который необходимо перевезти в пункты назначения В 1 , В 2 , В 3 , потребность каждого из которых составляет b 1 , b 2 , b 3 . Известно расстояние между пунктами перевозок (оценки).
Определить такой план перевозок, при котором общее количество тонно-километров будет минимальной.
Входные данные согласно варианту приведены в таблице 3.
1 | 2 | 3 | Запасы |
|
1 | 10 | 15 | 22 | 50 |
2 | 16 | 20 | 11 | 85 |
3 | 18 | 16 | 33 | 52 |
Потребности | 62 | 81 | 43 |
Математическая модель транспортной задачи:
F=∑∑c ij x ij , (1)
при условиях:
∑x ij = a i , i = 1,2,…, m, (2)
∑x ij = b j , j = 1,2,…, n, (3)
x ij ≥ 0
Запишем экономико-математическую модель для нашей задачи. Переменные:
x 11 – количество груза из 1-го склада в 1-й магазин; x 12 – количество груза из 1-го склада в 2-й магазин; x 13 – количество груза из 1-го склада в 3-й магазин; x 21 – количество груза из 2-го склада в 1-й магазин; x 22 – количество груза из 2-го склада в 2-й магазин; x 23 – количество груза из 2-го склада в 3-й магазин; x 31 – количество груза из 3-го склада в 1-й магазин; x 32 – количество груза из 3-го склада в 2-й магазин; x 33 – количество груза из 3-го склада в 3-й магазин
Ограничения по запасам:
x 11 + x 12 + x 13 ≤ 50 (для 1 базы)
x 21 + x 22 + x 23 ≤ 85 (для 2 базы)
x 31 + x 32 + x 33 ≤ 52 (для 3 базы)
Ограничения по потребностям:
x 11 + x 21 + x 31 = 62 (для 1 магазина)
x 12 + x 22 + x 32 = 81 (для 2 магазина)
x 13 + x 23 + x 33 = 43 (для 3 магазина)
Целевая функция: 10x 11 + 15x 12 + 22x 13 + 16x 21 + 20x 22 + 11x 23 + 18x 31 + 16x 32 + 33x 33 → min
Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке
- При некоторых реальных условиях перевозки груза из определенного пункта A i в пункт назначения B j не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт B j является сколь угодно большой величиной М и при этом условии известными методами находят решение транспортной задачи. Такой подход к нахождению решения ТЗ называется запрещением перевозок.
- В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Ai в B j требуется обязательно перевезти a ij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки A i и столбца B j , записывают указанное число a ij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой транспортной задачи находят оптимальный план, который определяет оптимальный план исходной задачи.
- Иногда требуется найти решение ТЗ, при котором из A i в B j должно быть перевезено не менее заданного количества груза a ij . Для определения оптимального плана такой задачи считают, что запасы Ai и потребности Bj меньше фактических на a ij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.
Модель без дефицита
В соответствии с терминологией транспортной модели поставщики представлены обычным и сверхурочным производством для различных этапов. Потребители задаются спросом соответствующих этапов. Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.Матрица полных затрат для эквивалентной транспортной задачи приведена в следующей таблице:
Дополнительный столбец используется для балансировки транспортной задачи, т.е. S = ∑a i - ∑b j . Затраты на единицу продукции в дополнительном столбце равны нулю. Так как дефицит не допускается, то продукцию, выпускаемую на рассматриваемом этапе, нельзя использовать для удовлетворения спроса предыдущих этапов. В таблице это ограничение представлено заштрихованными ячейками, что, в сущности, эквивалентно очень большим затратам на единицу продукции.
Так как задолженность в модели не допускается, то для каждого этапа k в нее необходимо включить ограничение, состоящее в том, что накопленный спрос не должен превышать соответствующего общего объема произведенной продукции, т.е. ∑ (a ri + a ti) ≥ ∑b j , k = 1,2,...,N.
Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i+1, i+2,..., N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1. Затем корректируются значения, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.
Модель с дефицитом
Рассмотрим обобщение описанной выше модели при условии, что допускается дефицит. Предполагается, что задолженный спрос должен быть удовлетворен к концу N-этапного горизонта планирования. Таблицу 1 можно легко модифицировать, чтобы учесть влияние задолженности, введя соответствующие удельные издержки в заблокированные маршруты.Так, например, если p i – удельные потери от дефицита (т.е. на единицу продукции) в случае, когда продукция требуется на этапе i, а поставляется на этапе i+1, то удельные расходы, соответствующие ячейкам R N,1 и T R ,1 , составляют: {c N + p1 + p 2 + … + p N -1 } и {d N + p1 + p 2 + … + p N -1 }соответственно.
Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.
