Транспортная задача линейного программирования
Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.Формулировка транспортной задачи
Однородный груз сосредоточен у k поставщиков в объемах a 1 , а2,..., аk. Данный груз необходимо доставить и потребителям в объемах b1, b2, ..., bn. Известны сiji= 1, 2, ..., k и j = 1, 2, ..., n — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.Исходные данные транспортной задачи обычно записываются в таблицу:
| | b1 | b2 | … | bn |
|
a1 | с11 |
с12 | |
с1n |
| a2 | с21 | … | | с2n |
|
… | … |
… | … |
… |
| ak | сk1 | … | … | сkn |
Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А = (a1, а2,..., аk), вектора запросов потребителей В= (b1, b2, ..., bn) и матрицы стоимостей C={сij}
В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, склады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.
Математическая модель транспортной задачи
Переменными (неизвестными) транспортной задачи являются xij ..,i-(=1,2, ..., k), j= 1,2, ...,n — объемы перевозок от каждого i -го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок:
или
| | a1 | a2 | … | an |
|
b1 | x11 |
x12 | |
x1n |
| b2 | x21 | … | | x2n |
|
… | … |
… | … |
… |
| bk | xk1 | … | … | xkn |
Так как произведение cijxij . определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны
. По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид:
Система ограничений задачи состоит из двух групп уравнений. Первая группа из k уравнений описывает тот факт, что запасы всех k поставщиков вывозятся полностью:
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
xij=≥0, i=1,2,...,k; j=1,2,...,n
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.
Математическая формулировка транспортной задачи такова: найти переменные X =(xij ) задачи удовлетворяющие системе ограничений:
условиям неотрицательности
и обеспечивающие минимум целевой функции.
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу A системы уравнений-ограничений задачи.
Таким образом в векторной форме задача будет выглядеть так:
Пример. Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице:
| | 20 | 30 | 40 |
| 40 |
3 | 5 |
7 |
| 50 | 4 | 6 | 10 |
Решение. Введем переменные задачи (матрицу перевозок)
| x11 | x12 | x13 |
|
x21 | x22 |
x23 |
Запишем матрицу стоимостей
Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц С и X:
F(X )=3x 11 +5x 12 +7x13+4x21+6x22+10x23.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам 1-го поставщика, а сумма перевозок во второй строке матрицы X — запасам 2-го поставщика. Следовательно:
x11 + x 12 + x 13 = 40; и х21 + х22 + х23 = 50.
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:
x11 + x 21 = 20;x 12 + x22= 30; и х31 + х32 = 40.
Это означает, что запросы потребителей удовлетворяются полностью.
Необходимо также учитывать, что перевозки не могут быть отрицательными:
х ij ≥ 0 , i = 1, 2, j= 1,2,3.
Следовательно, математическая модель рассматриваемой задачи такова: найти переменные задачи, обеспечивающие минимум функции:
F(X)=3·x11+5·x12+7·x31+4·x21+6·x22+10·x23
и удовлетворяющие системе ограничений
Необходимое и достаточное условия разрешимости транспортной задачи
Теорема. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей:
т.е. задача должна быть с правильным балансом.
Доказательство . Необходимость. Пусть задача имеет допустимое решение
X0=(x0ij), x0ij≥0, i=1,2,...,k; n=1,2,...,n
Докажем, что . Подставив
X0 в уравнения системы ограничений (6.2), (6.3), получим
Достаточность. Пусть задача имеет правильный баланс
Докажем, что в этом случае задача имеет оптимальное решение.
Сначала покажем, что область допустимых решений задачи – непустое множество. Легко проверить, что
Далее покажем, что существует оптимальное решение. Учитывая, что стоимости перевозок единиц груза ограничены сверху и снизу C≤cij≤ D; i=1,2,…,k; j=1,2,…,n, где C и D — конечные постоянные, можно записать
Свойство системы ограничений транспортной задачи
Теорема. Ранг системы векторов-условий транспортной задачи равен N = k+ n- 1. Доказательство. Как известно из линейной алгебры для нахождения базиса системы векторов A1А2, ..., Аn необходимо составить однородную систему уравненийA1 x 1 +А2x 2 + ... Аnx 2 = θ.
(здесь θ - нулевой вектор)
Эту систему с помощью преобразований Жордана приводят к равносильной разрешенной; в базис включают векторы, соответствующие разрешенным неизвестным. Ранг системы векторов равен числу векторов, входящих в базис, т.е. числу разрешенных неизвестных этой системы. Системе векторов-условий транспортной задачи Aij., i = 1, 2, ..., k; j = 1, 2, ..., n соответствует однородная система уравнений
где θ = (0, 0, ..., 0) T — нулевой вектор (транспонированный).
Запишем матрицу этой системы (она является также матрицей системы ограничений транспортной задачи):
Покажем, что найдутся N = k + n - 1 линейно независимых векторов-условий. Из векторов-условий задачи выберем следующие:
A 1 n А2 n , ..., АknA 11 А12, ..., А1( n -1) и убедимся, что они линейно независимы. Для этого составим систему уравнений
A1n x 1 n+А2nx2n+…+ Aknxkn +А12x 12 + ... А1(n-1)x 1( n -1) = θ.
Матрица этой системы, как легко показать, приводится к единичной. Следовательно система уравнений имеет единственное нулевое решение x1n= x2n= … = xkn = x11= x12=…= x1(n-1)=0,а система векторов линейно независима. Теорема доказана.
Для решения транспортной задачи можно воспользоваться средствами MS Excel или калькулятором.
Распределительный метод
Один из наиболее простых методов решения транспортных задач - распределительный метод.Пусть для транспортной задачи найдено начальное опорное решение Х1 и вычислено значение целевой функции на этом решении F(Х1). По доказанной выше теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Обозначив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину
можно получить новое опорное решение Х2.
Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l,m), приращение целевой функции Δlm равно разности двух сумм:
- сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком “+” ; 
- сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком “-”.
В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции.
Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. Δ lm< 0, то перераспределение величины θ по соответствующему циклу приведет к уменьшению значения F(X) на величину θ•Δlm, т.е. опорное решение можно улучшить. Если же величины Δlm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие
Δlm≥0, ∀xlm=0
Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, m) построить цикл и вычислить оценку Δlm. Если оценка неотрицательная, переходят к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину θ=min{xij}. В результате получится новое опорное решение.
Для каждого нового опорного решения вычисление оценок начинается с первой свободной клетки таблицы. Очередность проверяемых свободных клеток целесообразно устанавливать в порядке возрастания стоимости перевозок cij ,так как решается задача на нахождение минимума.
Пример. Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице:
| b1 | b2 | b3 | |||||
| 20 | 40 | 40 | |||||
| a1 | 20 | 1 | 3 | 2 | |||
| a2 | 30 | 4 | 5 | 7 | |||
| a3 | 50 | 6 | 8 | 15 | |||
Решение. Строим начальное опорное решение методом минимальной стоимости :
Затем вычисляем значение целевой функции на нем: F(X1) = 20·1 + 30·5 + 10·8 + 40·15 = 850.
Таблица
см. также Пример решения задачи распределительным методом
Экономические задачи, сводящиеся к транспортной модели
Рассматривается транспортная модель и ее варианты. Такая модель используется для составления наиболее экономичного плана перевозок одного вида продукции из нескольких пунктов (например, заводов) в пункты доставки (например, склады). Транспортную модель можно применять при рассмотрении ряда практических ситуаций, связанных с управлением запасами, составлением сменных графиков, назначением служащих на рабочие места, оборотом наличного капитала, регулированием расхода воды в водохранилищах и многими другими. Кроме того, модель можно видоизменить, с тем чтобы она учитывала перевозку нескольких видов продукции.Транспортная задача представляет собой задачу линейного программирования, однако ее специфическая структура позволяет так модифицировать симплекс-метод, что вычислительные процедуры становятся более эффективными. При разработке метода решения транспортной задачи существенную роль играет теория двойственности.
В классической транспортной задаче рассматриваются перевозки (прямые или с промежуточными пунктами) одного или нескольких видов продукции из исходных пунктов в пункты назначения. Эту задачу можно видоизменить, включив в нее ограничения сверху на пропускные способности транспортных коммуникаций. Задачу о назначениях и задачу управления запасами можно рассматривать как задачи транспортного типа.
Пример. В пунктах отправления А1, А2, А3 находится однородный груз в количестве a1, а2, а3, соответственно, который необходимо перевезти в пункты назначения В1, В2, В3, потребность каждого из которых составляет b1, b2, b3. Известно расстояние между пунктами перевозок (оценки).
Определить такой план перевозок, при котором общее количество тонно-километров будет минимальной.
Входные данные согласно варианту приведены в таблице 3.
1 | 2 | 3 | Запасы | |
1 | 10 | 15 | 22 | 50 |
2 | 16 | 20 | 11 | 85 |
3 | 18 | 16 | 33 | 52 |
Потребности | 62 | 81 | 43 |
Математическая модель транспортной задачи:
F=∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
xij ≥ 0
Запишем экономико-математическую модель для нашей задачи. Переменные:
x11 – количество груза из 1-го склада в 1-й магазин; x12 – количество груза из 1-го склада в 2-й магазин; x13 – количество груза из 1-го склада в 3-й магазин; x21 – количество груза из 2-го склада в 1-й магазин; x22 – количество груза из 2-го склада в 2-й магазин; x23 – количество груза из 2-го склада в 3-й магазин; x31 – количество груза из 3-го склада в 1-й магазин; x32 – количество груза из 3-го склада в 2-й магазин; x33 – количество груза из 3-го склада в 3-й магазин
Ограничения по запасам:
x11 + x12 + x13 ≤ 50 (для 1 базы)
x21 + x22 + x23 ≤ 85 (для 2 базы)
x31 + x32 + x33 ≤ 52 (для 3 базы)
Ограничения по потребностям:
x11 + x21 + x31 = 62 (для 1 магазина)
x12 + x22 + x32 = 81 (для 2 магазина)
x13 + x23 + x33 = 43 (для 3 магазина)
Целевая функция: 10x11 + 15x12 + 22x13 + 16x21 + 20x22 + 11x23 + 18x31 + 16x32 + 33x33 → min
Определение оптимального плана транспортных задач, имеющих некоторые усложнения в их постановке
- При некоторых реальных условиях перевозки груза из определенного пункта Ai в пункт назначения Bj не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт Bj является сколь угодно большой величиной М и при этом условии известными методами находят решение транспортной задачи. Такой подход к нахождению решения ТЗ называется запрещением перевозок.
- В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Ai в Bj требуется обязательно перевезти aij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки Ai и столбца Bj, записывают указанное число aij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой транспортной задачи находят оптимальный план, который определяет оптимальный план исходной задачи.
- Иногда требуется найти решение ТЗ, при котором из Ai в Bj должно быть перевезено не менее заданного количества груза aij. Для определения оптимального плана такой задачи считают, что запасы Ai и потребности Bj меньше фактических на aij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.
Модель без дефицита
В соответствии с терминологией транспортной модели поставщики представлены обычным и сверхурочным производством для различных этапов. Потребители задаются спросом соответствующих этапов. Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.Матрица полных затрат для эквивалентной транспортной задачи приведена в следующей таблице:
Дополнительный столбец используется для балансировки транспортной задачи, т.е. S = ∑ai - ∑bj. Затраты на единицу продукции в дополнительном столбце равны нулю. Так как дефицит не допускается, то продукцию, выпускаемую на рассматриваемом этапе, нельзя использовать для удовлетворения спроса предыдущих этапов. В таблице это ограничение представлено заштрихованными ячейками, что, в сущности, эквивалентно очень большим затратам на единицу продукции.
Так как задолженность в модели не допускается, то для каждого этапа k в нее необходимо включить ограничение, состоящее в том, что накопленный спрос не должен превышать соответствующего общего объема произведенной продукции, т.е. ∑ (ari + ati) ≥ ∑bj , k = 1,2,...,N.
Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i+1, i+2,..., N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1. Затем корректируются значения, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.
Модель с дефицитом
Рассмотрим обобщение описанной выше модели при условии, что допускается дефицит. Предполагается, что задолженный спрос должен быть удовлетворен к концу N-этапного горизонта планирования. Таблицу 1 можно легко модифицировать, чтобы учесть влияние задолженности, введя соответствующие удельные издержки в заблокированные маршруты.Так, например, если pi – удельные потери от дефицита (т.е. на единицу продукции) в случае, когда продукция требуется на этапе i, а поставляется на этапе i+1, то удельные расходы, соответствующие ячейкам RN,1 и TR,1, составляют: {cN + p1 + p2 + … + pN-1} и {dN + p1 + p2 + … + pN-1}соответственно.
Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.
Экономические задачи, сводящиеся к транспортной модели
Оптимальное распределение оборудования
Оборудование m различных видов нужно распределить между n рабочими участками. Производительность единицы оборудования i-го вида на j-м рабочем участке равна равна pij;; i = 1,…,m; j = 1,…,n. Потребность j-го участка в оборудовании составляет bj , j = 1,…,n. Запас оборудования i-го вида равен ai , i = 1,…,m. Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна.Данная задача относится к классу транспортных задач при условии, что производительность линейно зависит от количества используемого оборудования. Поставщиками в задаче являются различные виды оборудования, потребителями – рабочие участки.
Обозначим через xij число единиц оборудования i-го вида, выделенное на j-й рабочий участок, i = 1,…,m; j = 1,…,n. Математическая модель задачи имеет следующий вид:
Построенная модель является сбалансированной. Если запас оборудования и потребность в нем не равны, то переход к сбалансированной модели осуществляется с помощью преобразований. В данной задаче требуется максимизировать целевую функцию Р, представляющую суммарную производительность. Для перехода к стандартной транспортной модели надо заменить функцию Р на противоположную функцию –Р, которую нужно будет минимизировать. При решении в матрице вместо стоимостей перевозок единицы груза будут стоять производительности, взятые с противоположным знаком. Далее задача решается методом потенциалов.
Перейти к решению транспортной задачи
Станковая задача
Решается задача, относящаяся к классу задач распределения оборудования (станковая задача). На промышленном предприятия в механическом цехе имеются несколько типов станков, каждый из которых может производить однотипные детали. Производительность каждого типа станка для данного типажа деталей различна. Различны также издержки производства, связанные с потреблением электроэнергии, амортизацией оборудования и т.д.Необходимо распределить заказ на изготовление определенного количества деталей в механическом цехе на смену так, чтобы издержки производства были минимальны.
| Тип станков | Количество станков в цехе | Средняя производительность на 1 станок в смену (дет.) | Средние издержки на производство сменной нормы на 1 станок (ден. ед) | Требуемая сменная производительность (количество деталей) |
| 1 | 15 | 50 | 400 | 1110 |
| 2 | 20 | 40 | 180 | |
| 3 | 40 | 25 | 150 |
x2- количество станков второго типа,
x3 - количество станков третьего типа,
Целевая функция
400x1+180x2+150x3 = min
Система ограничений
50x1+40x2+25x3 ≥ 1110
x1 ≤ 15, x2 ≤ 20, x3 ≤ 40.
Далее задачу можно решить графическим методом.
Военно-прикладная задача линейного программирования
Пусть имеется m различных типов средств поражения (А1, А2,…, Аm) и n различных типов целей (В1, В2,…, Вn) и пусть известна вероятность поражения Pij средством Ai цели Bj. Требуется так распределить средства поражения по целям, чтобы получить максимальное значение математического ожидания числа уничтоженных целей.
Данная задача представляет собой классическую транспортную задачу с целевой функцией на максимум.
Формирование оптимального штата фирмы
Фирма набирает штат сотрудников. Она располагает n группами различных должностей по bj вакантных единиц в каждой группе, j = 1,…,n. Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по аii кандидатов в каждой группе, i = 1,…,m. Для каждого кандидата из i-ой группы требуются определенные затраты сij на обучение для занятия j-ой должности, i=1,…,m; j=1,…,n. (В частности, некоторые cij = 0, т.е. кандидат полностью соответствует должности, или cij = ∞ (cij = M), т.е. кандидат вообще не может занять данную должность.) Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение. Предположим, что общее число кандидатов соответствует числу вакантных должностей. Тогда данная задача соответствует транспортной модели. В роли поставщиков выступают группы кандидатов, а в роли потребителей – группы должностей. В качестве тарифов на перевозки рассматриваются затраты на переобучение. Математическая модель записывается в виде:
Задача календарного планирования производства
Рассмотрим задачу календарного планирования производства на N последовательных этапах. Спрос изменяется во времени, но детерминирован. Спрос можно удовлетворить либо путем изменения уровня запаса при постоянном объеме производства, либо за счет изменения объема производства при постоянном уровне запаса, либо путем изменения и уровня запаса, и выпуска. Изменения объема производства можно добиться, проводя сверхурочные работы, а изменения уровня запаса можно обеспечить за счет создания постоянного положительного запаса, либо за счет неудовлетворенного спроса.Нужно отыскать календарный план производства на N этапов, минимизирующий суммарные затраты. В модели предполагаются нулевые затраты на оформление заказа для любого этапа. В общем случае допускается дефицит при условии, что весь задолженный спрос должен быть удовлетворен к концу этапа N. Эти условия можно записать в виде транспортной задачи.
Введем следующие обозначения для этапа i; i= 1,2,...,N:
- cj - производственные затраты на единицу продукции при обычном режиме работы,
- di - производственные затраты на единицу продукции при работе в сверхурочное время (di> ci),
- hi - затраты на хранение единицы продукции, переходящей из этапа i в этап i+1,
- pi - потери от дефицита на единицу продукции, требуемой на этапе i, но поставляемой на этапе i+1,
- ari - производственная мощность (в единицах продукции) при обычном режиме работы,
- ati - производственная мощность (в единицах продукции) при работе в сверхурочное время,
- bi - спрос (в единицах продукции).
Задача о назначениях
Задача размещения производства
Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции – по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукции.Для такого вида задач заданы:
1. Издержки производства единицы продукции (руб.)
2. Издержки сбыта единицы продукции (руб.)
3. Плановый объем годового производства, который позволил бы удовлетворить спрос, и плановая стоимость единицы продукции каждого вида.
Решение: Общие издержки на единицу продукции складываются из издержек производства и издержек сбыта. Поскольку продажная цена единицы каждого вида продукции известна, то можно вычислить прибыль на единицу продукции.
Умножая прибыль, приходящуюся на единицу продукции, на годовой объем сбыта, можно получить общую годовую прибыль, соответствующую каждой паре вид продукции – предприятие.
Если прибыль рассматривать как отрицательные затраты, то исходная задача максимизации может быть сведена к минимизационной задаче о назначениях. Для того чтобы матрица стоимостей не содержала отрицательных элементов, сложим каждый элемент матрицы с максимальным числом и введем два вида фиктивной продукции (4 и 5), которой соответствует нулевая прибыль.
Оптимальное исследование рынка
Группе, исследующий рынок, требуется получить данные из n различных мест. В ее распоряжении имеется n дней, и она предполагает провести по одному дню в каждом месте, проведя по аj опросов, j=1,…,n. Вероятность успешного опроса в каждом месте задается матрицей Р. Элемент матрицы рij характеризует вероятность успешного опроса в течении i-го дня в j-м месте, i=1,…,n.Определить время проведения опросов, при котором общее число опросов максимально.
Решение. Сведем данную задачу к задаче о назначениях.
Введем величину rij=pijaj, показывающую число успешных опросов в в j-м месте в течение i-го дня.
xij = 1, если в i-й день опрос проводится в j-м месте;
xij =0 , в противном случае.
Математическая модель задачи имеет следующий вид:
Функция F характеризует суммарное число успешных опросов. Ее нужно максимизировать. Первое и второе ограничения соответствуют тому, что в течении одного дня можно находиться только в одном месте. Для расчета модели венгерским методом надо перейти к противоположной функции:
и в соответствующей таблице записывать значения rij с противоположным знаком.
Оптимальное использование рабочих агентов
Торговая фирма продает товары в n различных городах, покупательная способность жителей которых оценивается bj усл. ед., j = 1,…,n. Для реализации товаров фирма располагает n торговыми агентами, каждого из которых она направляет в один из городов. Профессиональный уровень агентов различен; доля реализуемых i-м торговым агентом покупательных способностей составляет аi, i = 1,…,n. Как следует распределить торговых агентов по городам, чтобы фирма получила максимальную выручку от продажи товаров?Решение этой проблемы может быть найдено с помощью задачи о назначениях. В качестве кандидатов выступают торговые агенты, в качестве работ – города.
Введем параметр сij = ai bj , характеризующий величину покупательных способностей, реализуемых i-м торговым агентом в j-м городе.
Управляющие переменные xij , i = 1,…,n; j = 1,…,n определяются по формуле
xij = 1, если i-й агент направлен в j-й город;
xij = M, в противном случае.
Математическая модель запишется в следующей форме:
Первое и второе ограничения формализуют соответственно условия о том, что в каждый город направляется один торговый агент и один торговый агент не может работать в двух городах. Целевая функция F – это сумма реализованных покупательных способностей всеми торговыми агентами во всех городах. Она должна подлежать максимизации. Для решения задачи венгерским методом надо, как и в предыдущем примере, перейти к противоположной функции.
Решение транспортной задачи линейного программирования
Опорное решение транспортной задачи
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы-условия, соответствующие положительным координатам, линейно независимы.Ввиду того, что ранг системы векторов условий транспортной задачи равен k + n- 1, опорное решение не может иметь отличных от нуля координат более k + n- 1. Число отличных от нуля координатневырожденного опорного решения равно k+ n- 1, а для вырожденного опорного решения меньше k + n- 1.
Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные — незанятыми или свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку хij т.е. стоящая в i-й строке и j-м столбце, имеет номер (i, j). Каждой клетке с номером (i, j)соответствует переменная хij, которой соответствует вектор-условиеAij.
Для того чтобы избежать трудоемких вычислений при проверке линейной независимости векторов-условий, соответствующих положительным координатам допустимого решения, вводят понятие цикла. Циклы также используются для перехода от одного опорного решения к другому.
Циклом называется такая последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), …,(ik,j 1 ), в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.
Цикл изображают в таблице транспортной задачи в виде замкнутой ломаной линии. В любой клетке цикла происходит поворот звена; ломаной линии на 90°. Простейшие циклы изображены на рисунке, где звездочкой отмечены клетки таблицы, включенные в состав цикла.
□ Теорема (о взаимосвязи линейной зависимости векторов-условий и возможности образования цикла). Для того чтобы система векторов-условий транспортной задачи была линейно зависимой, необходимо и достаточно, чтобы из соответствующих клеток таблицы можно было выделить часть, которая образует цикл.
Доказательство . Необходимость. Пусть система, состоящая из n векторов
линейно зависима. Тогда существует такой ненулевой набор чисел
, что справедливо равенство
Пусть λ1 ≠0. Вектор
. имеет две равные единице координаты с номерами i1, и k+j1, остальные
координаты равны нулю. В равенство (6.10) должен также входить вектор, у которого одна из этих координат равна единице и который следует умножить на коэффициент -λ1 чтобы обеспечить равенство нулю этой координаты в линейной комбинации векторов. Пусть таким вектором будет вектор 
,.
Однако он имеет, кроме того, координату с номером k+j2, равную единице. Следовательно, в равенство (6.10) должен также входить вектор с такой же единичной координатой и т.д.
В выбранной подобным образом последовательности векторов должен найтись вектор
у которого второй индекс совпадает со
вторым индексом первого вектора. Данной последовательности векторов соответствует совокупность клеток таблицы транспортной задачи (i1,j1),
(i1,j2), (i2,j2),…,(i k ,j1), которая образует цикл.
Достаточность. Пусть из соответствующих векторам А ij клеток (i, j) выбрана последовательность клеток, образующих цикл (i1,j1), (i1,j2), (i2,j2),…, (i k ,j1). Нетрудно видеть, что
Отсюда следует линейная зависимость рассматриваемой системы торов. Теорема доказана полностью.
Следствие. Допустимое решение транспортной задачи X=(xij),i= 1,2, ..., k ; j= 1, 2, ..., n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.
Пример.
1. Составить допустимый план транспортной задачи, используя метод минимальной стоимости или Мюллера-Мербаха для построения базисного плана с ограничением пропускной способности.
2. Найти оптимальный план транспортной задачи, используя метод потенциалов. Построенный допустимый и оптимальный план должен удовлетворять условиям постановки транспортной задачи.
a. 
b. 
c. 
d. 0≤xij≤dij
e. Целевая функция задачи 
3. Рассчитать целевые функции каждого базисного плана перевозок.
4. Найти экономический эффект от оптимизации. Экономический эффект от оптимизации рассчитывается как разность между целевыми функциями базисного и оптимального планов.
5. Рассчитать матрицу показателей характеристик оптимального плана перевозок транспортной задачи. Характеристики клеток рассчитываются по формуле: Dij = cij – (vj – Uj)
6. Показать варианты альтернативных решений при одной и той же целевой функции и при минимальных от нее отклонениях.
Обсуждение
1. Составить математическую модель сбалансированной задачи линейного программирования, описав все переменные, функцию цели и ограничения.
2. Найти опорное решение сформулированной транспортной задачи методами северо-западного угла, минимального элемента и аппроксимации Фогеля. Оценить значения функции цели, полученные для каждого из опорных планов, и сделать выводы о близости этих планов к оптимальному решению.
3. Решить сформулированную выше задачу методом потенциалов и методом дифференциальных рент.
4. Проверить решение в среде Excel.
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
С целью составления двойственной задачи переменные xij в условии (2) заменим на u1, u2, ui,.., um, а переменные xij в условия (3) на v1, v2, vj,.., vn.
Поскольку каждая переменная xij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.
Требуется найти не отрицательные числа ui (при i = 1,2,…,m) и vj (при j = 1,2,..,n), обращающие в максимум целевую функцию
G = ∑aiui + ∑bjvj
при условии
ui + vj ≤ cij, i = 1,2,..,m; j = 1,2,..,n (4)
В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:
ui + vj ≤ cij, если xij = 0,
ui + vj = cij, если xij ≥ 0,
Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.
Числа ui , vj называются потенциалами. Причем число ui называется потенциалом поставщика, а число vj – потенциалом потребителя.
По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.
Решение
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 8 | 9 | 10 | 9 | 180 |
| 2 | 10 | 8 | 8 | 9 | 200 |
| 3 | 11 | 10 | 9 | 10 | 130 |
| 4 | 9 | 9 | 8 | 10 | 50 |
| Потребности | 60 | 80 | 220 | 100 |
∑a = 180 + 200 + 130 + 50 = 560
∑b = 60 + 80 + 220 + 100 = 460
Как видно, суммарная потребность груза в пунктах назначения превышает запасы груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) базу с запасом груза, равным 100 (560—460). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
| 1 | 2 | 3 | 4 | 5 | Запасы | |
| 1 | 8 | 9 | 10 | 9 | 0 | 180 |
| 2 | 10 | 8 | 8 | 9 | 0 | 200 |
| 3 | 11 | 10 | 9 | 10 | 0 | 130 |
| 4 | 9 | 9 | 8 | 10 | 0 | 50 |
| Потребности | 60 | 80 | 220 | 100 | 100 |
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен 8
Для этого элемента запасы равны 180, потребности 60. Поскольку минимальным является 60, то вычитаем его.
x11 = min(180,60) = 60.
| 8 | 9 | 10 | 9 | 0 | 180 - 60 = 120 |
| x | 8 | 8 | 9 | 0 | 200 |
| x | 10 | 9 | 10 | 0 | 130 |
| x | 9 | 8 | 10 | 0 | 50 |
| 60 - 60 = 0 | 80 | 220 | 100 | 100 | 0 |
Для этого элемента запасы равны 200, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x22 = min(200,80) = 80.
| 8 | x | 10 | 9 | 0 | 120 |
| x | 8 | 8 | 9 | 0 | 200 - 80 = 120 |
| x | x | 9 | 10 | 0 | 130 |
| x | x | 8 | 10 | 0 | 50 |
| 0 | 80 - 80 = 0 | 220 | 100 | 100 | 0 |
Для этого элемента запасы равны 120, потребности 220. Поскольку минимальным является 120, то вычитаем его.
x23 = min(120,220) = 120.
| 8 | x | 10 | 9 | 0 | 120 |
| x | 8 | 8 | x | x | 120 - 120 = 0 |
| x | x | 9 | 10 | 0 | 130 |
| x | x | 8 | 10 | 0 | 50 |
| 0 | 0 | 220 - 120 = 100 | 100 | 100 | 0 |
Для этого элемента запасы равны 50, потребности 100. Поскольку минимальным является 50, то вычитаем его.
x43 = min(50,100) = 50.
| 8 | x | 10 | 9 | 0 | 120 |
| x | 8 | 8 | x | x | 0 |
| x | x | 9 | 10 | 0 | 130 |
| x | x | 8 | x | x | 50 - 50 = 0 |
| 0 | 0 | 100 - 50 = 50 | 100 | 100 | 0 |
Для этого элемента запасы равны 120, потребности 100. Поскольку минимальным является 100, то вычитаем его.
x14 = min(120,100) = 100.
| 8 | x | 10 | 9 | 0 | 120 - 100 = 20 |
| x | 8 | 8 | x | x | 0 |
| x | x | 9 | x | 0 | 130 |
| x | x | 8 | x | x | 0 |
| 0 | 0 | 50 | 100 - 100 = 0 | 100 | 0 |
Для этого элемента запасы равны 130, потребности 50. Поскольку минимальным является 50, то вычитаем его.
x33 = min(130,50) = 50.
| 8 | x | x | 9 | 0 | 20 |
| x | 8 | 8 | x | x | 0 |
| x | x | 9 | x | 0 | 130 - 50 = 80 |
| x | x | 8 | x | x | 0 |
| 0 | 0 | 50 - 50 = 0 | 0 | 100 | 0 |
Для этого элемента запасы равны 20, потребности 100. Поскольку минимальным является 20, то вычитаем его.
x15 = min(20,100) = 20.
| 8 | x | x | 9 | 0 | 20 - 20 = 0 |
| x | 8 | 8 | x | x | 0 |
| x | x | 9 | x | 0 | 80 |
| x | x | 8 | x | x | 0 |
| 0 | 0 | 0 | 0 | 100 - 20 = 80 | 0 |
Для этого элемента запасы равны 80, потребности 80. Поскольку минимальным является 80, то вычитаем его.
x35 = min(80,80) = 80.
| 8 | x | x | 9 | 0 | 0 |
| x | 8 | 8 | x | x | 0 |
| x | x | 9 | x | 0 | 80 - 80 = 0 |
| x | x | 8 | x | x | 0 |
| 0 | 0 | 0 | 0 | 80 - 80 = 0 | 0 |
| 1 | 2 | 3 | 4 | 5 | Запасы | |
| 1 | 8[60] | 9 | 10 | 9[100] | 0[20] | 180 |
| 2 | 10 | 8[80] | 8[120] | 9 | 0 | 200 |
| 3 | 11 | 10 | 9[50] | 10 | 0[80] | 130 |
| 4 | 9 | 9 | 8[50] | 10 | 0 | 50 |
| Потребности | 60 | 80 | 220 | 100 | 100 |
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
F(x) = 8*60 + 9*100 + 0*20 + 8*80 + 8*120 + 9*50 + 0*80 + 8*50 = 3830
Этап II. Улучшение опорного плана.
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 8; 0 + v1 = 8; v1 = 8
u1 + v4 = 9; 0 + v4 = 9; v4 = 9
u1 + v5 = 0; 0 + v5 = 0; v5 = 0
u3 + v5 = 0; 0 + u3 = 0; u3 = 0
u3 + v3 = 9; 0 + v3 = 9; v3 = 9
u2 + v3 = 8; 9 + u2 = 8; u2 = -1
u2 + v2 = 8; -1 + v2 = 8; v2 = 9
u4 + v3 = 8; 9 + u4 = 8; u4 = -1
| v1=8 | v2=9 | v3=9 | v4=9 | v5=0 | |
| u1=0 | 8[60] | 9 | 10 | 9[100] | 0[20] |
| u2=-1 | 10 | 8[80] | 8[120] | 9 | 0 |
| u3=0 | 11 | 10 | 9[50] | 10 | 0[80] |
| u4=-1 | 9 | 9 | 8[50] | 10 | 0 |
Минимальные затраты составят:
F(x) = 8*60 + 9*100 + 0*20 + 8*80 + 8*120 + 9*50 + 0*80 + 8*50 = 3830
Проверим оптимальность найденного плана по первой теореме двойственности (в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G).
G = 0•180 -1•200 + 0•130 -1•50 + 8•60 + 9•80 + 9•220 + 9•100 + 0•100 = 3830
Пример. Необходимо найти решение транспортной задачи по критерию стоимости методом потенциалов.
В силу специфических особенностей структуры математической модели транспортной ЗЛП разработаны для ее решения менее трудоемкие методы, чем симплекс-метод. Наибольшее применение нашел метод потенциалов, базирующийся на утверждениях теорем двойственности. Опорное решение ТЗЛП можно находить любым из предлагаемых методов. Для решения воспользуемся сервисом Транспортная задача онлайн
.
| 26 | 30 | 17 | 10 | 16 | 4 |
| 30 | 37 | 26 | 9 | 23 | 6 |
| 13 | 4 | 32 | 3 | 1 | 10 |
| 3 | 1 | 5 | 14 | 24 | 10 |
| 7 | 7 | 7 | 7 | 2 |
Решение:
Проверим необходимое и достаточное условие разрешимости задачи.
∑ a = 4 + 6 + 10 + 10 = 30
∑ b = 7 + 7 + 7 + 7 + 2 = 30
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Занесем исходные данные в распределительную таблицу.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17 |
10 | 16 |
4 |
2 | 30 | 37 | 26 | 9 | 23 | 6 |
|
3 | 13 |
4 | 32 |
3 | 1 |
10 |
4 | 3 | 1 | 5 | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Искомый элемент равен 1.
Для этого элемента запасы равны 10, потребности 2. Поскольку минимальным является 2, то вычитаем его.
26 | 30 | 17 | 10 | x | 4 |
30 |
37 | 26 |
9 | x |
6 |
13 | 4 | 32 | 3 | 1 | 8 |
3 |
1 | 5 |
14 | x |
10 |
7 | 7 | 7 | 7 | 0 | 0 |
Искомый элемент равен 1.
Для этого элемента запасы равны 10, потребности 7. Поскольку минимальным является 7, то вычитаем его.
26 | x | 17 | 10 | x | 4 |
30 |
x | 26 |
9 | x |
6 |
13 | x | 32 | 3 | 1 | 8 |
3 |
1 | 5 |
14 | x |
3 |
7 | 0 | 7 | 7 | 0 | 0 |
Искомый элемент равен 3.
Для этого элемента запасы равны 8, потребности 7. Поскольку минимальным является 7, то вычитаем его.
26 | x | 17 | x | x | 4 |
30 |
x | 26 |
x | x |
6 |
13 | x | 32 | 3 | 1 | 1 |
3 |
1 | 5 |
x | x |
3 |
7 | 0 | 7 | 0 | 0 | 0 |
Искомый элемент равен 3.
Для этого элемента запасы равны 3, потребности 7. Поскольку минимальным является 3, то вычитаем его.
26 | x | 17 | x | x | 4 |
30 |
x | 26 |
x | x |
6 |
13 | x | 32 | 3 | 1 | 1 |
3 |
1 | x |
x | x |
0 |
4 | 0 | 7 | 0 | 0 | 0 |
Искомый элемент равен 13.
Для этого элемента запасы равны 1, потребности 4. Поскольку минимальным является 1, то вычитаем его.
26 | x | 17 | x | x | 4 |
30 |
x | 26 |
x | x |
6 |
13 | x | x | 3 | 1 | 0 |
3 |
1 | x |
x | x |
0 |
3 | 0 | 7 | 0 | 0 | 0 |
Искомый элемент равен 17.
Для этого элемента запасы равны 4, потребности 7. Поскольку минимальным является 4, то вычитаем его.
x | x | 17 | x | x | 0 |
30 |
x | 26 |
x | x |
6 |
13 | x | x | 3 | 1 | 0 |
3 |
1 | x |
x | x |
0 |
3 | 0 | 3 | 0 | 0 | 0 |
Искомый элемент равен 26.
Для этого элемента запасы равны 6, потребности 3. Поскольку минимальным является 3, то вычитаем его.
x | x | 17 | x | x | 0 |
30 |
x | 26 |
x | x |
3 |
13 | x | x | 3 | 1 | 0 |
3 |
1 | x |
x | x |
0 |
3 | 0 | 0 | 0 | 0 | 0 |
Искомый элемент равен 30.
Для этого элемента запасы равны 3, потребности 3. Поскольку минимальным является 3, то вычитаем его.
x | x | 17 | x | x | 0 |
30 |
x | 26 |
x | x |
0 |
13 | x | x | 3 | 1 | 0 |
3 |
1 | x |
x | x |
0 |
0 | 0 | 0 | 0 | 0 | 0 |
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30[3] | 37 | 26[3] | 9 | 23 | 6 |
|
3 | 13[1] |
4 | 32 |
3[7] | 1[2] |
10 |
4 | 3[3] | 1[7] | 5 | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
4. Проверим оптимальность опорного плана. Найдем потенциалы uiи vjпо занятым клеткам таблицы, в которых ui+ vj= cij, полагая, что u1= 0.
u1 + v3 = 17; 0 + v3 = 17; v3 = 17
u2 + v3 = 26; 17 + u2 = 26; u2 = 9
u2 + v1 = 30; 9 + v1 = 30; v1 = 21
u3 + v1 = 13; 21 + u3 = 13; u3 = -8
u3 + v4 = 3; -8 + v4 = 3; v4 = 11
u3 + v5 = 1; -8 + v5 = 1; v5 = 9
u4 + v1 = 3; 21 + u4 = 3; u4 = -18
u4 + v2 = 1; -18 + v2 = 1; v2 = 19
v1=21 | v2=19 | v3=17 | v4=11 | v5=9 | |
u1=0 |
26 | 30 |
17[4] | 10 |
16 |
u2=9 | 30[3] | 37 | 26[3] | 9 | 23 |
u3=-8 |
13[1] | 4 |
32 | 3[7] |
1[2] |
u4=-18 | 3[3] | 1[7] | 5 | 14 | 24 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vj> cij
(1;4): 0 + 11 > 10; ∆14= 0 + 11 - 10 = 1
(2;4): 9 + 11 > 9; ∆24= 9 + 11 - 9 = 11
(3;2): -8 + 19 > 4; ∆32= -8 + 19 - 4 = 7
max(1,11,7) = 11 Выбираем максимальную оценку свободной клетки (2;4): 9.
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30[3][-] | 37 | 26[3] | 9[+] | 23 | 6 |
|
3 | 13[1][+] |
4 | 32 |
3[7][-] | 1[2] |
10 |
4 | 3[3] | 1[7] | 5 | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26[3] | 9[3] | 23 | 6 |
|
3 | 13[4] |
4 | 32 |
3[4] | 1[2] |
10 |
4 | 3[3] | 1[7] | 5 | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
u1 + v3 = 17; 0 + v3 = 17; v3 = 17
u2 + v3 = 26; 17 + u2 = 26; u2 = 9
u2 + v4 = 9; 9 + v4 = 9; v4 = 0
u3 + v4 = 3; 0 + u3 = 3; u3 = 3
u3 + v1 = 13; 3 + v1 = 13; v1 = 10
u4 + v1 = 3; 10 + u4 = 3; u4 = -7
u4 + v2 = 1; -7 + v2 = 1; v2 = 8
u3 + v5 = 1; 3 + v5 = 1; v5 = -2
v1=10 | v2=8 | v3=17 | v4=0 | v5=-2 | |
u1=0 |
26 | 30 |
17[4] | 10 |
16 |
u2=9 | 30 | 37 | 26[3] | 9[3] | 23 |
u3=3 |
13[4] | 4 |
32 | 3[4] |
1[2] |
u4=-7 | 3[3] | 1[7] | 5 | 14 | 24 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui+vj> cij
(3;2): 3 + 8 > 4; ∆32= 3 + 8 - 4 = 7
(4;3): -7 + 17 > 5; ∆43= -7 + 17 - 5 = 5
max(7,5) = 7
Выбираем максимальную оценку свободной клетки (3;2): 4.
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26[3] | 9[3] | 23 | 6 |
|
3 | 13[4][-] |
4[+] | 32 |
3[4] | 1[2] |
10 |
4 | 3[3][+] | 1[7][-] | 5 | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 1) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26[3] | 9[3] | 23 | 6 |
|
3 | 13 |
4[4] | 32 |
3[4] | 1[2] |
10 |
4 | 3[7] | 1[3] | 5 | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
u1 + v3 = 17; 0 + v3 = 17; v3 = 17
u2 + v3 = 26; 17 + u2 = 26; u2 = 9
u2 + v4 = 9; 9 + v4 = 9; v4 = 0
u3 + v4 = 3; 0 + u3 = 3; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u4 + v2 = 1; 1 + u4 = 1; u4 = 0
u4 + v1 = 3; 0 + v1 = 3; v1 = 3
u3 + v5 = 1; 3 + v5 = 1; v5 = -2
v1=3 | v2=1 | v3=17 | v4=0 | v5=-2 | |
u1=0 |
26 | 30 |
17[4] | 10 |
16 |
u2=9 | 30 | 37 | 26[3] | 9[3] | 23 |
u3=3 |
13 | 4[4] |
32 | 3[4] |
1[2] |
u4=0 | 3[7] | 1[3] | 5 | 14 | 24 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток.
(4;3): 0 + 17 > 5; ∆43= 0 + 17 - 5 = 12
Выбираем максимальную оценку свободной клетки (4;3): 5
Для этого в перспективную клетку (4;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26[3][-] | 9[3][+] | 23 | 6 |
|
3 | 13 |
4[4][+] | 32 |
3[4][-] | 1[2] |
10 |
4 | 3[7] | 1[3][-] | 5[+] | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 2) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26[0] | 9[6] | 23 | 6 |
|
3 | 13 |
4[7] | 32 |
3[1] | 1[2] |
10 |
4 | 3[7] | 1 | 5[3] | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
u1 + v3 = 17; 0 + v3 = 17; v3 = 17
u2 + v3 = 26; 17 + u2 = 26; u2 = 9
u2 + v4 = 9; 9 + v4 = 9; v4 = 0
u3 + v4 = 3; 0 + u3 = 3; u3 = 3
u3 + v2 = 4; 3 + v2 = 4; v2 = 1
u3 + v5 = 1; 3 + v5 = 1; v5 = -2
u4 + v3 = 5; 17 + u4 = 5; u4 = -12
u4 + v1 = 3; -12 + v1 = 3; v1 = 15
v1=15 | v2=1 | v3=17 | v4=0 | v5=-2 | |
u1=0 |
26 | 30 |
17[4] | 10 |
16 |
u2=9 | 30 | 37 | 26[0] | 9[6] | 23 |
u3=3 |
13 | 4[7] |
32 | 3[1] |
1[2] |
u4=-12 | 3[7] | 1 | 5[3] | 14 | 24 |
Опорный план не является оптимальным, так как существуют оценки свободных клеток.
(3;1): 3 + 15 > 13; ∆31= 3 + 15 - 13 = 5.
Выбираем максимальную оценку свободной клетки (3;1): 13
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». Цикл приведен в таблице.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26[0][-] | 9[6][+] | 23 | 6 |
|
3 | 13[+] |
4[7] | 32 |
3[1][-] | 1[2] |
10 |
4 | 3[7][-] | 1 | 5[3][+] | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 0. Прибавляем 0 к объемам грузов, стоящих в плюсовых клетках и вычитаем 0 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 | 2 | 3 | 4 | 5 | Запасы | |
|
1 | 26 |
30 | 17[4] |
10 | 16 |
4 |
2 | 30 | 37 | 26 | 9[6] | 23 | 6 |
|
3 | 13[0] |
4[7] | 32 |
3[1] | 1[2] |
10 |
4 | 3[7] | 1 | 5[3] | 14 | 24 | 10 |
|
Потребности | 7 |
7 | 7 |
7 | 2 |
|
u1 + v3 = 17; 0 + v3 = 17; v3 = 17
u4 + v3 = 5; 17 + u4 = 5; u4 = -12
u4 + v1 = 3; -12 + v1 = 3; v1 = 15
u3 + v1 = 13; 15 + u3 = 13; u3 = -2
u3 + v2 = 4; -2 + v2 = 4; v2 = 6
u3 + v4 = 3; -2 + v4 = 3; v4 = 5
u2 + v4 = 9; 5 + u2 = 9; u2 = 4
u3 + v5 = 1; -2 + v5 = 1; v5 = 3
v1=15 | v2=6 | v3=17 | v4=5 | v5=3 | |
u1=0 |
26 | 30 |
17[4] | 10 |
16 |
u2=4 | 30 | 37 | 26 | 9[6] | 23 |
u3=-2 |
13[0] | 4[7] |
32 | 3[1] |
1[2] |
u4=-12 | 3[7] | 1 | 5[3] | 14 | 24 |
Опорный план является оптимальным. Минимальные затраты составят:
F(x) = 17*4 + 9*6 + 4*7 + 3*1 + 1*2 + 3*7 + 5*3 = 191
Пример №4.
Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.
Решение:
а) Методом потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7 | 1 | 10 |
| 2 | 5 | 12 | 10 | 4 | 29 |
| 3 | 16 | 8 | 2 | 9 | 39 |
| 4 | 5 | 11 | 10 | 3 | 49 |
| 5 | 0 | 0 | 0 | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
∑a = 10 + 29 + 39 + 49 + 34 = 161
∑b = 19 + 35 + 42 + 65 = 161
Условие баланса соблюдается.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7 | 1 | 10 |
| 2 | 5 | 12 | 10 | 4 | 29 |
| 3 | 16 | 8 | 2 | 9 | 39 |
| 4 | 5 | 11 | 10 | 3 | 49 |
| 5 | 0 | 0 | 0 | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
1. Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Искомый элемент равен 6. Для этого элемента запасы равны 10, потребности 19. Поскольку минимальным является 10, то вычитаем его.
x11= min(10,19) = 10.
| 6 | x | x | x | 10 - 10 = 0 |
| 5 | 12 | 10 | 4 | 29 |
| 16 | 8 | 2 | 9 | 39 |
| 5 | 11 | 10 | 3 | 49 |
| 0 | 0 | 0 | 0 | 34 |
| 19 - 10 = 9 | 35 | 42 | 65 | 0 |
x21= min(29,9) = 9.
| 6 | x | x | x | 0 |
| 5 | 12 | 10 | 4 | 29 - 9 = 20 |
| x | 8 | 2 | 9 | 39 |
| x | 11 | 10 | 3 | 49 |
| 0 | 0 | 0 | 0 | 34 |
| 9 - 9 = 0 | 35 | 42 | 65 | 0 |
x22= min(20,35) = 20.
| 6 | x | x | x | 0 |
| 5 | 12 | x | x | 20 - 20 = 0 |
| x | 8 | 2 | 9 | 39 |
| x | 11 | 10 | 3 | 49 |
| 0 | 0 | 0 | 0 | 34 |
| 0 | 35 - 20 = 15 | 42 | 65 | 0 |
x32= min(39,15) = 15.
| 6 | x | x | x | 0 |
| 5 | 12 | x | x | 0 |
| x | 8 | 2 | 9 | 39 - 15 = 24 |
| x | x | 10 | 3 | 49 |
| 0 | 0 | 0 | 0 | 34 |
| 0 | 15 - 15 = 0 | 42 | 65 | 0 |
x33= min(24,42) = 24.
| 6 | x | x | x | 0 |
| 5 | 12 | x | x | 0 |
| x | 8 | 2 | x | 24 - 24 = 0 |
| x | x | 10 | 3 | 49 |
| 0 | 0 | 0 | 0 | 34 |
| 0 | 0 | 42 - 24 = 18 | 65 | 0 |
x43= min(49,18) = 18.
| 6 | x | x | x | 0 |
| 5 | 12 | x | x | 0 |
| x | 8 | 2 | x | 0 |
| x | x | 10 | 3 | 49 - 18 = 31 |
| 0 | 0 | 0 | 0 | 34 |
| 0 | 0 | 18 - 18 = 0 | 65 | 0 |
x44= min(31,65) = 31.
| 6 | x | x | x | 0 |
| 5 | 12 | x | x | 0 |
| x | 8 | 2 | x | 0 |
| x | x | 10 | 3 | 31 - 31 = 0 |
| 0 | 0 | 0 | 0 | 34 |
| 0 | 0 | 0 | 65 - 31 = 34 | 0 |
x54= min(34,34) = 34.
| 6 | x | x | x | 0 |
| 5 | 12 | x | x | 0 |
| x | 8 | 2 | x | 0 |
| x | x | 10 | 3 | 0 |
| 0 | 0 | 0 | 0 | 34 - 34 = 0 |
| 0 | 0 | 0 | 34 - 34 = 0 | 0 |
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6[10] | 3 | 7 | 1 | 10 |
| 2 | 5[9] | 12[20] | 10 | 4 | 29 |
| 3 | 16 | 8[15] | 2[24] | 9 | 39 |
| 4 | 5 | 11 | 10[18] | 3[31] | 49 |
| 5 | 0 | 0 | 0 | 0[34] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно: F(x) = 6*10 + 5*9 + 12*20 + 8*15 + 2*24 + 10*18 + 3*31 +0*34 = 786
4. Проверим оптимальность опорного плана. Найдем предварительные потенциалыui, vj. по занятым клеткам таблицы, в которых ui+ vj= cij, полагая, что u1= 0.
u1+ v1= 6; 0 + v1= 6; v1= 6
u2+ v2= 12; -1 + v2= 12; v2= 13
u3+ v3= 2; -5 + v3= 2; v3= 7
u4+ v4= 3;3 + v4= 3; v4= 0
| v1=6 | v2=13 | v3=7 | v4=0 | |
| u1=0 | 6[10] | 3 | 7 | 1 |
| u2=-1 | 5[9] | 12[20] | 10 | 4 |
| u3=-5 | 16 | 8[15] | 2[24] | 9 |
| u4=3 | 5 | 11 | 10[18] | 3[31] |
| u5=0 | 0 | 0 | 0 | 0[34] |
(1;2): 0 + 13 > 3; ∆12= 0 + 13 - 3 =10
(4;1): 3 + 6 > 5; ∆41= 3 + 6 - 5 = 4
(4;2): 3 + 13 > 11; ∆42= 3 + 13 - 11 =5
(5;1): 0 + 6 > 0; ∆51= 0 + 6 - 0 = 6
(5;2): 0 + 13 > 0; ∆52= 0 + 13 - 0 =13
(5;3): 0 + 7 > 0; ∆53= 0 + 7 - 0 = 7
max(10,4,5,6,13,7) = 13
Выбираем максимальную оценку свободной клетки (5;2): 0
Для этого в перспективную клетку (5;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6[10] | 3 | 7 | 1 | 10 |
| 2 | 5[9] | 12[20] | 10 | 4 | 29 |
| 3 | 16 | 8[15][-] | 2[24][+] | 9 | 39 |
| 4 | 5 | 11 | 10[18][-] | 3[31][+] | 49 |
| 5 | 0 | 0[+] | 0 | 0[34][-] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 15. Прибавляем 15 к объемам грузов, стоящих в плюсовых клетках и вычитаем 15 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6[10] | 3 | 7 | 1 | 10 |
| 2 | 5[9] | 12[20] | 10 | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10[3] | 3[46] | 49 |
| 5 | 0 | 0[15] | 0 | 0[19] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v1= 6; 0 + v1= 6; v1= 6
u2+ v2= 12; -1 + v2= 12; v2= 13
u5+ v4= 0; -13 + v4= 0; v4= 13
u4+ v3= 10;-10 + v3= 10; v3= 20
| v1=6 | v2=13 | v3=20 | v4=13 | |
| u1=0 | 6[10] | 3 | 7 | 1 |
| u2=-1 | 5[9] | 12[20] | 10 | 4 |
| u3=-18 | 16 | 8 | 2[39] | 9 |
| u4=-10 | 5 | 11 | 10[3] | 3[46] |
| u5=-13 | 0 | 0[15] | 0 | 0[19] |
(1;2): 0 + 13 > 3; ∆12= 0 + 13 - 3 =10
(1;3): 0 + 20 > 7; ∆13= 0 + 20 - 7 =13
(1;4): 0 + 13 > 1; ∆14= 0 + 13 - 1 =12
(2;3): -1 + 20 > 10; ∆23= -1 + 20 - 10= 9
(2;4): -1 + 13 > 4; ∆24= -1 + 13 - 4 =8
(5;3): -13 + 20 > 0; ∆53= -13 + 20 - 0= 7
max(10,13,12,9,8,7) = 13
Выбираем максимальную оценку свободной клетки (1;3): 7
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6[10][-] | 3 | 7[+] | 1 | 10 |
| 2 | 5[9][+] | 12[20][-] | 10 | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10[3][-] | 3[46][+] | 49 |
| 5 | 0 | 0[15][+] | 0 | 0[19][-] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (4, 3) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6[7] | 3 | 7[3] | 1 | 10 |
| 2 | 5[12] | 12[17] | 10 | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[18] | 0 | 0[16] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v1= 6; 0 + v1= 6; v1= 6
u2+ v2= 12; -1 + v2= 12; v2= 13
u5+ v4= 0; -13 + v4= 0; v4= 13
u1+ v3= 7;0 + v3= 7; v3= 7
| v1=6 | v2=13 | v3=7 | v4=13 | |
| u1=0 | 6[7] | 3 | 7[3] | 1 |
| u2=-1 | 5[12] | 12[17] | 10 | 4 |
| u3=-5 | 16 | 8 | 2[39] | 9 |
| u4=-10 | 5 | 11 | 10 | 3[49] |
| u5=-13 | 0 | 0[18] | 0 | 0[16] |
(1;2): 0 + 13 > 3; ∆12= 0 + 13 - 3 =10
(1;4): 0 + 13 > 1; ∆14= 0 + 13 - 1 =12
(2;4): -1 + 13 > 4; ∆24= -1 + 13 - 4 =8
max(10,12,8) = 12
Выбираем максимальную оценку свободной клетки (1;4): 1
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6[7][-] | 3 | 7[3] | 1[+] | 10 |
| 2 | 5[12][+] | 12[17][-] | 10 | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[18][+] | 0 | 0[16][-] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7[3] | 1[7] | 10 |
| 2 | 5[19] | 12[10] | 10 | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[25] | 0 | 0[9] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v3= 7; 0 + v3= 7; v3= 7
u1+ v4= 1; 0 + v4= 1; v4= 1
u5+ v2= 0; -1 + v2= 0; v2= 1
u2+ v1= 5;11 + v1= 5; v1= -6
| v1=-6 | v2=1 | v3=7 | v4=1 | |
| u1=0 | 6 | 3 | 7[3] | 1[7] |
| u2=11 | 5[19] | 12[10] | 10 | 4 |
| u3=-5 | 16 | 8 | 2[39] | 9 |
| u4=2 | 5 | 11 | 10 | 3[49] |
| u5=-1 | 0 | 0[25] | 0 | 0[9] |
(2;3): 11 + 7 > 10; ∆23= 11 + 7 - 10 =8
(2;4): 11 + 1 > 4; ∆24= 11 + 1 - 4 = 8
(5;3): -1 + 7 > 0; ∆53= -1 + 7 - 0 = 6
max(8,8,6) = 8
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7[3][-] | 1[7][+] | 10 |
| 2 | 5[19] | 12[10][-] | 10[+] | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[25][+] | 0 | 0[9][-] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7 | 1[10] | 10 |
| 2 | 5[19] | 12[7] | 10[3] | 4 | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[28] | 0 | 0[6] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v4= 1; 0 + v4= 1; v4= 1
u5+ v2= 0; -1 + v2= 0; v2= 1
u2+ v1= 5; 11 + v1= 5; v1= -6
u2+ v3= 10;11 + v3= 10; v3= -1
| v1=-6 | v2=1 | v3=-1 | v4=1 | |
| u1=0 | 6 | 3 | 7 | 1[10] |
| u2=11 | 5[19] | 12[7] | 10[3] | 4 |
| u3=3 | 16 | 8 | 2[39] | 9 |
| u4=2 | 5 | 11 | 10 | 3[49] |
| u5=-1 | 0 | 0[28] | 0 | 0[6] |
(2;4): 11 + 1 > 4; ∆24= 11 + 1 - 4 = 8
Выбираем максимальную оценку свободной клетки (2;4): 4
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7 | 1[10] | 10 |
| 2 | 5[19] | 12[7][-] | 10[3] | 4[+] | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[28][+] | 0 | 0[6][-] | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (5, 4) = 6.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3 | 7 | 1[10] | 10 |
| 2 | 5[19] | 12[1] | 10[3] | 4[6] | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[34] | 0 | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v4= 1; 0 + v4= 1; v4= 1
u2+ v1= 5; 3 + v1= 5; v1= 2
u2+ v2= 12; 3 + v2= 12; v2= 9
u2+ v3= 10;3 + v3= 10; v3= 7
| v1=2 | v2=9 | v3=7 | v4=1 | |
| u1=0 | 6 | 3 | 7 | 1[10] |
| u2=3 | 5[19] | 12[1] | 10[3] | 4[6] |
| u3=-5 | 16 | 8 | 2[39] | 9 |
| u4=2 | 5 | 11 | 10 | 3[49] |
| u5=-9 | 0 | 0[34] | 0 | 0 |
(1;2): 0 + 9 > 3; ∆12= 0 + 9 - 3 = 6
Выбираем максимальную оценку свободной клетки (1;2): 3
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3[+] | 7 | 1[10][-] | 10 |
| 2 | 5[19] | 12[1][-] | 10[3] | 4[6][+] | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[34] | 0 | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 1.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3[1] | 7 | 1[9] | 10 |
| 2 | 5[19] | 12 | 10[3] | 4[7] | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[34] | 0 | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v2= 3; 0 + v2= 3; v2= 3
u1+ v4= 1; 0 + v4= 1; v4= 1
u2+ v1= 5; 3 + v1= 5; v1= 2
u2+ v3= 10;3 + v3= 10; v3= 7
| v1=2 | v2=3 | v3=7 | v4=1 | |
| u1=0 | 6 | 3[1] | 7 | 1[9] |
| u2=3 | 5[19] | 12 | 10[3] | 4[7] |
| u3=-5 | 16 | 8 | 2[39] | 9 |
| u4=2 | 5 | 11 | 10 | 3[49] |
| u5=-3 | 0 | 0[34] | 0 | 0 |
(5;3): -3 + 7 > 0; ∆53= -3 + 7 - 0 = 4
Выбираем максимальную оценку свободной клетки (5;3): 0
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3[1][+] | 7 | 1[9][-] | 10 |
| 2 | 5[19] | 12 | 10[3][-] | 4[7][+] | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[34][-] | 0[+] | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
Из грузов хijстоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 3.
| 1 | 2 | 3 | 4 | Запасы | |
| 1 | 6 | 3[4] | 7 | 1[6] | 10 |
| 2 | 5[19] | 12 | 10 | 4[10] | 29 |
| 3 | 16 | 8 | 2[39] | 9 | 39 |
| 4 | 5 | 11 | 10 | 3[49] | 49 |
| 5 | 0 | 0[31] | 0[3] | 0 | 34 |
| Потребности | 19 | 35 | 42 | 65 |
u1+ v2= 3; 0 + v2= 3; v2= 3
u5+ v3= 0; -3 + v3= 0; v3= 3
u1+ v4= 1; 0 + v4= 1; v4= 1
u2+ v1= 5;3 + v1= 5; v1= 2
| v1=2 | v2=3 | v3=3 | v4=1 | |
| u1=0 | 6 | 3[4] | 7 | 1[6] |
| u2=3 | 5[19] | 12 | 10 | 4[10] |
| u3=-1 | 16 | 8 | 2[39] | 9 |
| u4=2 | 5 | 11 | 10 | 3[49] |
| u5=-3 | 0 | 0[31] | 0[3] | 0 |
Минимальные затраты составят: F(x) = 3*4 + 1*6 + 5*19 + 4*10 + 2*39 + 3*49 + 0*31 + 0*3 = 378
Постановка транспортной задачи общего вида
Классическая постановка транспортной задачи общего вида такова.Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:
ai– объемы производства i -го поставщика, i = 1, …, m;
bj – спрос j-го потребителя, j= 1,…,n;
сij – стоимость перевозки одной единицы продукции из пункта Ai– i-го поставщика, в пункт Вj – j-го потребителя.
Для наглядности данные удобно представлять в виде таблицы, которую называют таблицей стоимостей перевозок.
| Поставщики ↓ Потребители → | В1 | В2 | … | Вn | запасы |
| А1 | С11 | C12 | C1n | а1 | |
| А2 | С21 | C22 | C2n | а2 | |
| … | |||||
| Am | Cm1 | Cm2 | Cmn | аm | |
| Потребности | b1 | b2 | bn |
Требуется найти план перевозок, при котором бы полностью удовлетворялся спрос всех потребителей, при этом хватало бы запасов поставщиков и суммарные транспортные расходы были бы минимальными.
Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных хij, i= 1,…, n, j= 1, …, m, каждая переменная хij обозначает объем перевозок из пункта Ai в пункт Вj.
Набор переменных X = {xij} и будет планом, который необходимо найти, исходя из постановки задачи.
Ограничения задачи примут вид:
Очевидно, что для разрешимости задачи 1 необходимо, чтобы суммарный спрос не превышал объема производства у поставщиков:
Если это неравенство выполняется строго, то задача называется «открытой» или «несбалансированной», если же 
, то задача называется «закрытой» транспортной задачей, и будет иметь вид (2):
– условие сбалансированности.
Это условие для решения закрытых транспортных задач (ЗТЗ).
В силу ограничений (2) нетрудно увидеть, что ЗТЗ является задачей ЛП и может быть решена симплекс-методом после приведения ее к специальному виду. Но структура системы ограничений имеет некоторою специфику, а именно: каждая переменная хij входит ровно два раза в неравенства системы, и все переменные входят в неравенства системы с коэффициентом 1. В силу этой специфики существует более простой метод решения, называемый методом потенциалов, который, по сути, является некоторой модификацией симплекс-метода. По-прежнему идеей является переход от одного опорного плана к другому, обязательно «лучшему» с точки зрения значения целевой функции. Каждому опорному плану также соответствует своя распределительная таблица. Переход осуществляется от одного плана к другому, пока полученный план не будет удовлетворять условию оптимальности. Необходимо научиться строить первоначальный опорный план. В качестве первоначального плана годится любое решение системы уравнений (2). Заметим, что это система линейных уравнений, состоящая из m + n уравнений с m*n неизвестными. Можно доказать, что линейно независимых уравнений в системе (2) m + n – 1, ввиду условия сбалансированности, т.е. базисных переменных должно быть m + n– 1. Итак, в качестве плана будем представлять себе таблицу размера m ∙ n, в которой должно быть занято m + n – 1 клеток, отвечающих базисным переменным xij.
Транспортные задачи с неправильным балансом
В рассмотренной модели транспортной задачи мы предполагали, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.
Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой. Решение задачи с неправильным балансом сводится к решению задачи с правильным балансом введением в ее математическую модель фиктивного поставщика или фиктивного потребителя. Тарифы на перевозку грузов от таких поставщиков или к таким потребителям полагаются равными 0 (т.е. фактически соответствующие перевозки не производятся). В случае превышения общего запаса продукции над потребностью, т.е. если
в рассмотрение вводится фиктивный потребитель с потребностью
и тарифами на перевозку ci ( k +1) =0. Если же
то вводится фиктивный поставщик, запасы которого равны
с тарифами на перевозку c ( n +1)j=0. Этим приемом задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Заметим, что при составлении начального опорного решения для ускорения вычислений в последнюю очередь следует (хотя и не обязательно) распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствуют наименьшие тарифы на перевозку (равные 0).
Построение первоначального опорного плана по правилу наименьшей стоимости
Построение плана по правилу наименьшей стоимости заключается в следующем. Рассматриваем матрицу (таблицу) транспортных расходов, стоимостей, данную изначально в качестве условия задачи. Выбираем клетку с минимальной ценой перевозки (клетка с номером i, j) и помещаем в эту клетку наименьшее из чисел {ai, bj}. Затем исключаем из рассмотрения строку, соответствующую поставщику (если аi меньшее), или столбец, соответствующий потребителю (если вj меньшее). Исключение строки означает, что запасы i-го потребителя удовлетворены. Из оставшейся таблицы снова выбираем наименьшую стоимость, и т.д. продолжаем до тех пор, пока все запасы не исчерпаны, а потребности не удовлетворены. Проверьте, что сумма чисел в каждой строке получившейся таблицы равна аi, а сумма чисел в каждом столбце равна вj, что и требовалось. Число занятых клеток должно равняться m + n – 1, в противном случае, если занятых клеток меньше, чем m + n – 1, дополним таблицу необходимым количеством нулей (нулевых перевозок) и будем считать эти клетки с нулями занятыми так, чтобы общее количество занятых клеток равнялось равно m + n – 1. Нули поставим в клетки, соответствующие минимальной стоимости.Метод потенциалов
При построении плана мы ставим задачу найти хоть какой-нибудь, не обязательно лучший, оптимальный план, удовлетворяющий ограничениям задачи. Теперь нам хотелось бы уметь отвечать на вопрос: является ли найденный опорный план оптимальным, и если нет, то «улучшать» его. Эту задачу решает метод потенциалов, предложенный в 1949 г. советскими учеными Л.В. Канторовичем и М.К. Гавуриным. теоретической основой метода является теорема.Теорема. Если для некоторого опорного плана Х = {xij} транспортной задачи можно подобрать систему из m + n чисел u1, u2, …, um, v1, v2, … vn, называемых потенциалами, то план оптимален тогда и только тогда, когда выполняются условия:
- ui+vj=cij для всех xij > 0 (1)
- ui+vj ≤ cij для всех i = 1,m, j = 1,n
Доказательство теоремы опускаем, оно основывается на рассмотрении двойственной задачи к исходной транспортной. Итерация метода потенциалов состоит из трех шагов.
I шаг (вычисление потенциалов).
Условие (1) представляет собой систему из ( m + n – 1) линейных уравнений с (m + n) неизвестными потенциалами. Поэтому одно из неизвестных полагаем равным 0 для определенности, затем последовательно находим остальные потенциалы.
II шаг (проверка плана на оптимальность).
Для проверки плана на оптимальность необходимо проверить условие (2). Для занятых клеток это условие выполняется, именно на них достигается равенство. Остается посчитать суммы ui + vj для свободных клеток. Если ui + vj ≤ сij, то, по теореме, план является оптимальным и задача решена.
III шаг (улучшение плана).
Для проведения операции улучшения плана нам понадобится понятие цикла.
Определение. Циклом будем называть набор клеток матрицы перевозок, в котором две и ровно две соседние клетки расположены в одной строке или в одном столбце, и первая и последняя клетки набора лежат тоже в одной строке или столбце.
Графически нетрудно представить цикл в виде ломаной, каждое звено которой лежит в строке или в столбце, причем в каждой строке или столбце не более чем по одному звену.
Примеры:
- допустимый план является опорным, когда из занятых этим планом клеток нельзя образовать ни одного цикла;
- если имеем опорный план, то для каждой свободной клетки можно образовать единственный цикл, содержащий данную клетку и некоторые из занятых.
Улучшение плана производится по следующей схеме. В подчеркнутых клетках табл. 2 находим клетку с наибольшей разностью ui + vj – cij, т.е. где условие (2) нарушается максимально.
Затем для этой клетки, согласно утверждению 2, строим единственный цикл. Набор клеток в цикле помечаем поочередно знаками «+» и «–», начиная с «+» в свободной клетке.
Начиная с клетки (1, 1), где условие (2) нарушено максимально, строим цикл. Клетку (1, 1) помечаем знаком «+». Цикл единственен, у нас все занятые клетки вошли в цикл, но это необязательно. Строим новый план хn по правилу:
Замечание. Если транспортная задача является задачей открытого типа, в которой условие баланса не выполняется, а именно сумма запасов больше суммы потребностей, то решить такую задачу можно по предложенной схеме методом потенциалов, введя дополнительного потребителя, с потребностью равной разности балансов и нулевыми стоимостями перевозок от каждого поставщика к этому потребителю.
Виды транспортных задач
- Классическая транспортная задача (перевозка грузов от поставщиков к потребителям);
- Задача коммивояжера;
- Задача о назначениях;
Методы решения транспортных задач
- Классическая транспортная задача (перевозка грузов от поставщиков к потребителям);
Методы решения: метод потенциалов, симплексный метод; - Задача коммивояжера;
Методы решения: метод ветвей и границ, венгерский метод, метод минимальных линий; - Задача о назначениях;
Методы решения: венгерский метод, метод Мака, метод минимальных линий;