Рассматривается транспортная модель и ее варианты. Такая модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов (например, заводов) в пункты доставки (например, склады). Транспортную модель можно применять при рассмотрении ряда практических ситуаций, связанных с управлением запасами,
составлением сменных графиков, назначением служащих на рабочие места, оборотом наличного капитала, регулированием расхода воды в водохранилищах и многими другими. Кроме того, модель можно видоизменить, с тем чтобы она учитывала перевозку нескольких видов продукции.
Транспортная задача представляет собой задачу линейного программирования, однако ее специфическая структура позволяет так модифицировать симплекс-метод, что вычислительные процедуры становятся более эффективными. При разработке метода решения транспортной задачи существенную роль играет теория двойственности.
В классической транспортной задаче рассматриваются перевозки (прямые или с промежуточными пунктами) одного или нескольких видов продукции из исходных пунктов в пункты назначения. Эту задачу можно видоизменить, включив в нее ограничения сверху на пропускные способности транспортных коммуникаций. Задачу о назначениях и задачу управления запасами можно рассматривать как задачи транспортного типа.
Пример
. В пунктах отправления А 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 }соответственно.
Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.
Одной из типичных задач линейного программирования является так называемая транспортная задача. Она возникает при планировании наиболее рациональных перевозок грузов. В одних случаях это означает определение такого плана перевозок, при котором стоимость последних была минимальной, а в других – более важным является выигрыш времени. Первая задача получила название транспортной задачи по критерию стоимости , а вторая – транспортная задача по критерию времени .
Первая задача является частным случаем задачи линейного программирования и может быть решена симплексным методом.
Пусть в 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.
Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов изготовления (например, заводов) в пункты доставки (например, склады).
Транспортная модель может применяться при рассмотрении практических ситуаций, связанных с управлением запасами, составлением именных графиков, назначением служащих не рабочие места, оборотом наличного капитала.
Транспортная задача может быть сведена к задаче линейного программирования и решена симплекс-методом. Вместе с тем специфика транспортной задачи позволяет решить ее более эффективным методом. Однако, и этот метод по существу воспроизводит шаги симплекс-метода.
Определение транспортной модели
При построении транспортной модели используются:
Заметим, что потребности одного пункта назначения могут удовлетворяться из нескольких исходных пунктов, так же один пункт производства может поставлять товар в несколько пунктов потребления.
Цель построения модели заключается в определении количества продукции, которую следует перевозить из всех исходных пунктов в пункты потребления при минимальных общих транспортных расходах.
Основное предположения транспортной модели состоит в том, что величина расходов на каждом маршруте прямо пропорциональна объему перевозимой продукции.
Рассмотрим графическое представление транспортной модели
Рисунок 6
Транспортная модель такого вида
называется сетевой и имеет mисходных пунктов иnпунктов назначения. Исходные пункты и
пункты назначения называются вершинами
сети или соответствующего графа. Маршрут
по которому перевозится продукция
называется дугой, количество продукции,
производимая вi-ом исходно
пункте обозначается
.
Количество потребляемой продукции вj-ом пункте -
.
Стоимость перевозки
.
Соответствующую математическую модель можно записать в следующем виде:
Iотражает тот факт, что суммарный объем перевозок из некоторого исходного пункта не может превышать произведенного в этом пункте количества продукции.
IIпоказывает, что суммарные перевозки продукции в некоторый пункт потребления должны полностью удовлетворять потребность в спросе на эту продукцию.
Анализ транспортной модели показывает, что суммарный объем производства не должен быть меньше объема потребления.
В том случае, если что суммарный объем производства равен суммарному объему потребления, транспортная модель называется сбалансированной.
Такая модель является канонической моделью линейного программирования.
Пример транспортной модели
Заводы автомобильной фирмы расположены в Лос-Анджелесе, Детройте и Нью-Орлеане. Центры распределения в Денвере и Майами. Объем производства заводов 1000, 1500 и 1200 автомобилей соответственно. Ожидаемый спрос равен 2300 и 1400 автомобилей соответственно.
Стоимость перевозки одного автомобиля приведена в таблице 10:
Таблица 10
- количество автомобилей, которые
перевозят изi-ого пункта
вj-ый (i=1,2,3;j=1,2).
Суммарный объем производства автомобилей равен 3700 и равняется суммарному ожидаемому спросу. Следовательно, данная транспортная модель является сбалансированной и ее можно записать в следующем виде:
при ограничениях
Компактный способ записи транспортной модели связан с использованием транспортной таблицы или матрицы, у которой соответствуют исходным пунктам, а столбцы пунктам спроса.
Модели транспортной задачи
Модель, в которой спрос и производство равны, называется закрытой (сбалансированной).
Если баланс производства и потребления нарушен, т.е. часть произведенного продукта не вывозится а i > b j , модель транспортной задачи будет открытой. Для решения открытой модели приведем ее к виду закрытой, введя фиктивный пункт потребления. Его потребность в произведенной продукции будет равна: b m+1 = а i - b j . В случае, когда спрос превышает мощность пунктов-изготовителей, также имеем вариант открытой модели. Подход к ее решению аналогичен ранее приведенному: открытую модель сводим к закрытой, вводя соответственно фиктивного поставщика. В связи с нарушением баланса спроса и предложения изменяются и ограничительные условия: предложение больше спроса - условия х ij а i , в противном случае х ij b j .
Удовлетворение критериального условия - минимизация транспортных расходов - возможно только при учете реальных затрат, связанных с поставкой продукции реальным потребителям. Это необходимо иметь в виду, чтобы в процессе решения задачи блокировать прикрепление к фиктивному потребителю реальных поставщиков.
Методы решения транспортных задач
Решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т.д. пунктах производства, по первому, второму и т.д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются a i (q) , а текущих неудовлетворенных потребностей - b j (q) . Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем a i (0) = a i , b j (0) = b j . Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х i,j = min {a i (q) , b j (q) }. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину:
a i (q+1) = a i (q) - x i,j , b j (q+1) = b j (q) - x i,j .
Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: a i (q+1) =0 или b j (q+1) =0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т.е. переместиться к следующей клетке вниз по столбцу. Если же b j (q+1) =0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции.
Основываясь на условии баланса запасов и потребностей (a i = b j), нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (a i (q) = b j (q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана.
Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения c i,j . В связи с этим на практике для получения исходного плана используется другой способ - метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами.
Поскольку в правиле ”северо-западного угла“ значение Cij не учитывается, нельзя ожидать, что при вычислении исходного плана по этому правилу соответствующее значение линейной формы будет близким к минимальному.
1. Правило минимума по строке. Пусть минимальным элементом первой строки будет C1k (если минимальных элементов имеется более одного, то выбираем элемент с наименьшим индексом j).Предположим X1k= a, если a1<=bk; x1k=bk, если a1>bk. В первом случае полагают Xik=0 для i = k и переходят ко второй строке, заменяя bk наbk-a1. После этого находят минимальный элемент второй строки и повторяют процесс. Во втором случае заменяют a1 на a1-bk, bk-на нуль и определяют наименьший за вычетом C1k элемент первой строки, после чего описанный процесс повторяется.
2. Правило минимума по столбцу. Вычисление исходного плана проводится по правилу, описанному выше, с той разницей, что строки заменяются столбцами.
3. Правило минимального элемента матрицы. Отыскивается минимальный элемент Cij матрицы стоимостей перевозок, после чего величина перевозки (xij) полагается равной min(aibj). Процесс повторяется до тех пор, пока весь продукт не будет перевезен.
Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:
vj[k] - ui[k] = Cij, i=1,..., m; j=1, …, n.
Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи.
Метод минимальной стоимости. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую в клетку, которая ей соответствует, помещают меньшее из чисел аi или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Метод двойного предпочтения. Если таблица стоимостей велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем.
В каждом столбце отмечают знаком V клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку V V. В них находится минимальная стоимость как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз, исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком /. В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.
Транспортная задача - это классическая задача линейного программирования о нахождении наиболее рационального с точки зрения затрат плана перевозок однородного продукта от изготовителя (поставщика) к потребителю. Термин "транспортная задача" определяет не только область приложения метода, но и особенности его реализации с точки зрения используемых математических приемов и т.п. В новых условиях хозяйствования, когда максимально необходимо сокращать расходы, в том числе и транспортные, решение транспортной задачи приобретет важнейшее значение.
Среди задач линейной оптимизации могут быть выделены два класса задач со специальной структурой:
транспортная задача
задача о назначениях.
Эти задачи используются для моделирования оптимизации экономических проблем, связанных с формированием оптимального плана перевозок, оптимального распределения индивидуальных контрактов на транспортировки, составления оптимального штатного расписания, определения оптимальной специализации предприятий, рабочих участков и станков, оптимального назначения кандидатов на работы, оптимального использования торговых агентов. Критерием эффективности в данных задачах является линейная функция, ограничения также линейны, поэтому для их решения могут применяться методы линейной оптимизации, например симплекс-метод. Однако специальная структура таких задач позволяет разработать более удобные методы их решения. Некоторые из таких методов приведены этой книге. Даны общая формулировка задач, основные термины и определения, этапы построения математических моделей, этапы получения оптимальных решений. Также приведены числовые примеры экономических задач, которые могут быть решены этими методами.
Построим транспортную модель для конкретной задачи.
Четыре предприятия данного экономического района для производства продукции используют некоторое сырье. Спрос на сырье каждого из предприятий соответственно составляет: 120, 50, 190 и 110 усл. ед. Сырье сосредоточено в трех местах.
Предложения поставщиков сырья равны: 160, 140 и 170 усл. ед. На каждое предприятие сырье может завозиться от любого поставщика. Тарифы перевозок известны и задаются матрицей
В i -й строке j -м столбце матрицы С стоит тариф на перевозку сырья от i -гo поставщика j -му потребителю, i=1, 2, 3; j =1, 2, 3, 4. Под тарифом понимается стоимость перевозки единицы сырья.
Требуется составить план перевозок, при котором общая стоимость перевозок минимальна.
Построение математической модели
Цель задачи состоит в минимизации суммарной стоимости на перевозки. Эта цель может быть достигнута с помощью оптимальной организации перевозок сырья. Следовательно, за неизвестные можно принять количество сырья, перевозимого от каждого поставщика каждому потребителю.
Пусть хij - количество сырья, перевозимого от i -го поставщика j-му потребителю. Параметры задачи - число поставщиков и потребителей, предложение и спрос сырья в каждом пункте, тарифы на перевозки.
Ограничения задачи - это ограничения на предложение и спрос сырья. Предложения сырья всех поставщиков не должны быть меньше суммарного спроса на него во всех пунктах потребления. В данной задаче имеет место точное равенство между предложением и спросом. 120+50+190+110=160+140+170=470.
Количество сырья, вывозимого от каждого поставщика, должно быть равно наличному количеству сырья. Количество сырья, доставленное каждому потребителю, должно равняться его спросу. Последнее ограничение - условие неотрицательности хij.
Критерием эффективности (целевой функцией) являются суммарные затраты S на перевозку, равные сумме произведений тарифов на перевозку на количество перевозимого сырья от каждого поставщика каждому потребителю.
Окончательно математическая модель задачи имеет вид
Целевая функция и ограничения линейны, т.е. данная задача относится к задачам линейного программирования, однако, благодаря особой структуре, эта задача получила специальное название: транспортная задача или транспортная модель.
Определение начального плана транспортировок. Метод "северо-западного" угла
Рассмотрим метод "северо-западного" угла.
Метод "северо-западного" угла
Шаг 1. Составляют транспортную таблицу.
Шаг 2. Транспортную таблицу начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос:
Если а1 < b2, то х11 = a1 и предложение первого поставщика полностью исчерпано. Первая строка вычеркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: х21 == min(a2,b1-a1). Если b1-a1 Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 1. Транспортная таблица имеет следующий вид (табл. 3.1): Таблица 3.1 В первую клетку помещают: х11 = min(160,120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160 - 120=40 усл. ед. Двигаемся по первой строке вправо х21 =min(160 -120,50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз х22 =min(140,50 - 40) = 10; Второй столбец вычеркивается. Двигаемся по второй строке вправо х23 = min(140 -10,90) = 130. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз x33 = min(170,190 -130) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо х34 = min(170 -160, 10) = 110. Таблица заполнена. Число ненулевых значений xij, транспортная математическая модель метод угол равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю. Начальный план перевозок имеет вид Стоимость перевозок по этому плану составляет S1= 120*7+40*8+10*5+130*9+60*3+110*6=3220. Метод "северо-западного" угла -- наиболее простой метод нахождения начального решения. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.