Решение закрытой транспортной задачи по критерию стоимости.

Транспортная задача.

Постановка задачи.

Изложенный в предыдущих разделах симплекс-метод является универсальным методом, применимым для решения практически всех задач линейного программирования (группа МФЗ-301 изучала на 1-ом курсе, а группе МЭБЗ-301 остаётся лишь поверить этому). Однако существуют некоторые частные типы задач линейного программирования, которые, в силу некоторых особенностей своей структуры, допускают решение более простыми методами, являющимися модификациями симплексного метода. К ним относятся, в частности, так называемая транспортная задача.

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

Рассмотрим первый тип транспортной задачи - задачу по критерию стоимости. Классическая транспортная задача линейного программирования по критерию стоимости формулируется следующим образом.

Имеется m пунктов отправления (поставщиков): А₁, А₂, …, А_m, в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно а₁, а₂,…,а_m. Кроме того, имеется n пунктов назначения (потребителей): B₁, B₂, …,B_n, подавших заявки соответственно на b₁, b₂, …, b_n единиц товара.

Известна стоимость c_ij перевозки единицы товара от пункта отправления A_i до пункта назначения B_j. Таблица (матрица) стоимостей перевозки c_ij задана:

c₁₁ с₁₂ с₁₃... с_1n

c₂₁ c₂₂ c₂₃... c_2n

........

c_i1 c_i2 c_i3... c_in

........

c_m1 c_m2 c_m3... c_mn

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

Дадим этой задаче математическую формулировку. Обозначим x_ij - количество груза, доставляемого из i-го пункта отправления (от i-го поставщика) А_i в j-й пункт назначения (j-му потребителю) B_j (i=1,m; j=1,n). Неотрицательные переменные x_i1, x_i2, …, x_mn (число которых равно mxn) должны удовлетворять следующим условиям:

1. Суммарное количество груза, направляемое из каждого пункта отправления во все пункты назначения, должно быть равно запасу груза в данном пункте (или мощности данного поставщика). Это даст нам m условий-равенств:

x₁₁ + x₁₂ +... + x_1j +... + x_1n = a₁,

x₂₁ + x₂₂ +... + x_2j +... + x_2n = a₂,

.....

x_i1 + x_i2 +... + x_ij +... + x_in = a_i,

.....

x_m1 + x_m2 +... + x_mj +... + x_mn = a_m,

или, короче, x_ij = a_i (i = 1, m), (2.1)

2. Суммарное количество груза, доставляемое в каждый пункт назначения от всех пунктов отправления, должно быть равно заявке, поданной данным потребителем. Это даст нам n условий-равенств:

x₁₁ + x₂₁ +... + x_i1 +... + x_m1 = b₁,

x₁₂ + x₂₂ +... + x_i2 +... + x_m2 = b₂,

.....

x_1j + x_2j +... + x_ij +... + x_mj = b_j,

.....

x_1n + x_2n +... + x_in +... + x_mn = b_n,

или, короче, x_ij = b_j (j = 1, n), (2.2)

Уравнения (2.1), (2.2) называются балансовыми уравнениями.

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

F = c₁₁x₁₁ + c₁₂x₁₂ +... +... +c_1jx_1j +... + c_1nx_1n +

+ c₂₁x₂₁ + c₂₂x₂₂ +... +... +c_2jx_2j +... + c_2nx_2n +... +

+ c_m1x_m1 + c_m2x_m2 +... +... +c_mjx_mj +... + c_mnx_mn → min,

или, короче, F = (с_ij · x_ij) → min (2.3)

где знак двойной суммы означает, что суммирование производится по всем комбинациям индексов (i=1,m; j=1,n), то есть по всем комбинациям пунктов отправления с пунктами назначения.

Функция (2.3) линейна, ограничения-равенства (2.1), (2.2) также линейны. Перед нами – типичная задача линейного программирования с ограничениями-равенствами (ОЗЛП), которая формулируется следующим образом.

Требуется на множестве неотрицательных решений найти переменные x_ij, (i = 1, m; j = 1, n), удовлетворяющие условиям (2.1), (2.2) и минимизирующие целевую функцию F (2.3).

Математическая модель транспортной задачи, как видно из (2.1)-(2.3), обладает следующими особенностями:

а) система ограничений задана в виде уравнений (то есть, задача задана в канонической форме);

б) коэффициенты при переменных в системах ограничений равны единице или нулю;

в) каждая переменная входит в систему ограничений два раза: один раз в сумму по i и один раз в сумму по j;

Транспортные задачи, в которых выполняется условие

a_i = b_j, (2.4)

то есть, суммарные запасы равны суммарным потребностям, называются закрытыми транспортными задачами (закрытая модель транспортной задачи). В противном случае задача называется открытой (открытая модель транспортной задачи).

Решение закрытой транспортной задачи по критерию стоимости.

Постановка задачи.

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

Модификациями симплексного метода применительно к закрытой транспортной задаче являются распределительный метод и его разновидности ( метод северо-западного угла, метод минимальной стоимости, метод двойного предпочтения), а также метод потенциалов, с которыми ознакомимся ниже.

Основной особенностью транспортной задачи является то, что все коэффициенты при переменных в уравнениях (2.1), (2.2) равны единице. Кроме того, имеет значение структура связей между условиями. Нетрудно убедиться, что не все т + п уравнений нашей задачи являются независимыми. Действительно, складывая между собой все уравнения (2.1) и все уравнения (2.2), получим

x_ij = a_i (2.5)

x_ij = b_j, (2.6)

В силу условия (2.4) правые части уравнений (2.5) и (2.6) совпадают. Левые части этих уравнений, являющиеся суммами всевозможных переменных x_ij данной задачи, также совпадают. Таким образом, сумма первых m уравнений системы ограничений равна сумме оставшихся n уравнений этой системы. Следовательно, условия (2.1), (2.2) связаны одной линейной зависимостью, и фактически из этих уравнений только т+п- 1, а не т + п являются линейно независимыми.

Отсюда следует:

Теорема 2.1. Ранг R системы уравнений (2.1), (2.2) при условии (2.4) равен т+n-1.

Значит, уравнения (2.1), (2.2) можно разрешить относительно т+n-1 базисных переменных, выразив их через остальные, свободные переменные, количество которых равно: r= mn - (т+п-1) = тп – т - (п -1) = m(п-1)- (п-1) = (m-1)(n-1)

Условимся значения x_ij количества единиц груза, направляемых из пункта А_i в пункт В_j,- называть перевозками или поставками в клетку (i,j).

Любую совокупность значений (х_ij) (i=1,..., т; j = 1,..., п) будем называть планом перевозок, или просто планом.

План (x_ij) называется допустимым, если он удовлетворяет условиям (2.1), (2.2) («балансовым условиям»), то есть, все заявки удовлетворены, все запасы исчерпаны.

Допустимый план называется опорным (или базисным распределением поставок), если в нем не более R=т+п-1 базисных перевозок x_ij отличны от нуля, а остальные (не менее r=(n-1)(m-1)) перевозки равны нулю.

План (x_ij) называется оптимальным, если он, среди всех допустимых планов, приводит к наименьшей стоимости всех перевозок.

Как известно, в задаче линейного программирования оптимальное решение достигается в одной из вершин ОДР, соответствующей одному из базисных решений, в котором, крайней мере, r свободных переменных обращаются в нуль. Значит, в нашем случае для оптимального плана перевозок, по крайней мере, (т-1)(п-1) значений x_ij должны быть равны нулю.

Методы решения транспортной задачи (ТЗ) не требуют манипуляций с симплекс-таблицами, а сводятся к более простым операциям непосредственно с транспортной таблицей, где в определенном порядке записаны все условия транспортной задачи. Такую таблицу называют транспортной таблицей или таблицей поставок. В транспортной таблице записываются:

- пункты отправления (ПО) и пункты назначения (ПН), или поставщики и потребители;

- запасы, имеющиеся в пунктах отправления,(мощности поставщиков);

- заявки, поданные пунктами назначения, (спросы потребителей);

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

Стоимости перевозок (коэффициенты затрат) помещают в правом верхнем углу каждой ячейки, с тем чтобы в самой ячейке при составлении плана помещать перевозки x_ij – поставки клетки (i,j).

Образец транспортной таблицы дан в табл. 2.0.

Таблица 2.0

ПО ПН	В1	В2	...	Вj	...	Вn	Запасы aj
A1	с11	с12	...	с1j	...	с1n	a1
A2	с21	с22	...	с2j	...	с2n	a2
...	...	...	...	...	...	...	...
Аi	сi1	сi2	...	сij	...	сin	ai
...	...	...	...	...	...	...	...
Am	сm1	сm2	...	сmj	...	сmn	am
Заявки bj	b1	b2	...	bj	...	bn

 

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

Пример 2.1. Построение экономико-математической модели транспортной задачи.

Пусть имеется три поставщика и четыре потребителя некоторого однотипного груза. Мощности поставщиков и спросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик-потребитель» сведены в таблицу поставок (таблица 2.1). В правом верхнем углу (i,j)-ой клетки таблицы 2.1 (где i-номер строки, j-номер столбца) стоит, так называемый, коэффициент затрат – затраты на перевозку единицы груза от i-го поставщика к j‑му потребителю. Например, в правом верхнем углу клетки (1,4) стоит число 3, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 3 условные денежные единицы.

Таблица 2.1.

Поставщики	Поставщикки	В1	В2	В3	В4	Мощность поставщиков (запасы) - аi
А1	х 11	х 1 2	х 1 3	х 14
А2	х 21	х 22	х 23	х 24
А3	х 31	х 32	х 33	х 34
Спрос потребителей (заявки) -bj

Требуется сформулировать математическую модель данной задачи.

Решение. Искомый объем перевозки от i-го поставщика к j-му потребителю - поставку клетки (i, j) обозначим через х_ij. Запишем величины поставок х_ij в нижнем левом углу клетки (i, j) таблицы. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения переменных х_ij. Так, например, объем груза, забираемого от 1-го поставщика, должен быть равен мощности этого поставщика – 60 единицам, то есть, х₁₁+ х₁₂ + х₁₃ + х₁₄ = 60 (уравнение баланса по первой строке).

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

х₁₁ + х₁₂ + х₁₃ + х₁₄ = 60,

х₂₁ + х₂₂ + х₂₃ + х₂₄ = 120, (2.1.1)

х₃₁ + х₃₂ + х₃₃ + х₃₄ = 100,

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляем для каждого столбца таблицы поставок:

х₁₁ + х₂₁ + х₃₁ = 20,

х₁₂ + х₂₂ + х₃₂ = 110, (2.1.2)

х₁₃ + х₂₃ + х₃₃ = 40,

х₁₄+ х₂₄ + х₃₄ = 110,

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует предположить, что (2.1.3)

Суммарные затраты F на перевозку выражаются через коэффициенты затрат и величины поставок следующим образом:

F = 1∙ х₁₁ +2 ∙ х₁₂ +5 ∙ х₁₃ +3 ∙ х₁₄ +1 ∙ х₂₁ +6 ∙ х₂₂ +5 ∙ х₂₃ +2 ∙ х₂₄ +

+ 6∙ х₃₁ +3 ∙ х₃₂ +7 ∙ х₃₃ +4 ∙ х₃₄ (2.1.4)

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу):

на множестве неотрицательных решений системы ограничений (2.1.1) и (2.1.2) найти такое решение Х^*=(х^*₁₁, х^*₁₂, х^*₁₃,... х^*₃₃, х^*₃₄), при котором линейная функция (2.1.4) принимает минимальное значение.

* * * * * * * * * * * * * * * * * * * * * * * * *

Выше показали, что ранг системы уравнений-ограничений транспортной задачи равен R=т + п-1, где т- число строк, а n -число столбцов транспортной таблицы. Значит, в каждом опорном плане, включая оптимальный, будут отличны от нуля не более, чем п + т-1 перевозок.

Ячейки таблицы, в которых мы будем записывать эти отличные от нуля перевозки, условимся называть базисными, остальные (пустые)- свободными.

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

1) мощности всех поставщиков (запасы продукции) реализованы, то есть, сумма перевозок в каждой строке таблицы должна быть равна запасу данного пункта отправки (поставщика);

2) спросы (заявки) всех потребителей удовлетворены, то есть, сумма перевозок в каждом столбце таблицы должна быть равна заявке данного пункта назначения (потребителя);

3) суммарные затраты на перевозку - минимальны.

В дальнейшем все действия по нахождению решения транспортной задачи будут сводиться к преобразованию транспортной таблицы 2.1.

Нахождение первоначального опорного плана.

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

А. Метод «северо-западного угла».

Рассмотрим его на конкретном примере.

Пример 2.2. Найти первоначальное базисное распределение поставок (опорный план) для транспортной задачи 2.1.

Решение. Дадим максимально возможную поставку в клетку (1,1) – «северо-западный» угол таблицы поставок или, иными словами, переменной х₁₁ максимально возможное значение: х₁₁ = min(60,20) = 20. Величину х₁₁ = 20 запишем в левом нижнем углу клетки (1,1) таблицы. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения. Теперь в таблице поставок найдем новый «северо-западный» угол – клетку (1,2) и дадим в нее максимально возможное значение с учетом того, что 1-й поставщик уже отдал 20 единиц груза и у него осталось 60-20 = 40 единиц груза, то есть, х₁₂ = min(60-20,110) = 40. После этого запасы 1-го поставщика полностью реализованы и 1-ая строка таблицы поставок выпадет из рассмотрения. В оставшейся таблице снова находим «северо-западный» угол и т.д. В результате получаем следующее исходное распределение поставок (таблица 2.2).

Таблица 2.2.

Поставщики	Поставщикки	В1	В2	В3	В4	аi
А1	20	40
А2		70	40	10
А3				100
bj

 

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

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

Число заполненных клеток в полученном распределении равно m+n-1= =3+4-1=6, то есть, равно числу основных (базисных) переменных. Это, конечно, не случайно. Действительно, на каждом шаге, кроме последнего, данного метода из рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец, и строка. Поэтому число заполненных клеток (число шагов) на единицу меньше, чем сумма строк и столбцов таблицы поставок, то есть равно m+n-1. Согласно теореме 2.1 эта особенность шагов метода «северо-западного» угла служит причиной того, что полученное распределение является базисным.

Существенный недостаток метода «северо-западного» угла состоит в том, что опорный план построен без учета значений коэффициентов затрат задачи. Однако, данный метод допускает модификацию, лишенную этого недостатка.