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

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

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

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

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

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

Имеется m пунктов отправления (поставщиков): А1, А2, …, Аm, в которых сосредоточены запасы какого-то однородного товара (груза) в количестве соответственно а1, а2,…,аm. Кроме того, имеется n пунктов назначения (потребителей): B1, B2, …,Bn, подавших заявки соответственно на b1, b2, …, bn единиц товара.

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

c11 с12 с13 . . . с1n

c21 c22 c23 . . . c2n

. . . . . . . .

ci1 ci2 ci3 . . . cin

. . . . . . . .

cm1 cm2 cm3 . . . cmn

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

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

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

x11 + x12 + . . . + x1j + . . . + x1n = a1,

x21 + x22 + . . . + x2j + . . . + x2n = a2,

. . . . .

xi1 + xi2 + . . . + xij + . . . + xin = ai,

. . . . .

xm1 + xm2 + . . . + xmj + . . . + xmn = am,

или, короче, xij = ai (i = 1, m), (2.1)

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

x11 + x21 + . . . + xi1 + . . . + xm1 = b1,

x12 + x22 + . . . + xi2 + . . . + xm2 = b2,

. . . . .

x1j + x2j + . . . + xij + . . . + xmj = bj,

. . . . .

x1n + x2n + . . . + xin + . . . + xmn = bn,

или, короче, xij = bj (j = 1, n), (2.2)

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

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

F = c11x11 + c12x12 + . . . + . . . +c1jx1j + . . . + c1nx1n +

+ c21x21 + c22x22 + . . . + . . . +c2jx2j + . . . + c2nx2n + . . . +

+ cm1xm1 + cm2xm2 + . . . + . . . +cmjxmj + . . . + cmnxmn → min,

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

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

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

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

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

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

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

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

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

ai = bj, (2.4)

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

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

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

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

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

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

xij = ai (2.5)

xij = bj, (2.6)

В силу условия (2.4) правые части уравнений (2.5) и (2.6) совпадают. Левые части этих уравнений, являющиеся суммами всевозможных переменных xij данной задачи, также совпадают. Таким образом, сумма первых 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)

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

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

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

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

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

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

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

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

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

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

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

Стоимости перевозок (коэффициенты затрат) помещают в правом верхнем углу каждой ячейки, с тем чтобы в самой ячейке при составлении плана помещать перевозки xij поставки клетки (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 единицам, то есть, х11+ х12 + х13 + х14 = 60 (уравнение баланса по первой строке).

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

х11 + х12 + х13 + х14 = 60 ,

х21 + х22 + х23 + х24 = 120 , (2.1.1)

х31 + х32 + х33 + х34 = 100 ,

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

х11 + х21 + х31 = 20,

х12 + х22 + х32 = 110, (2.1.2)

х13 + х23 + х33 = 40,

х14+ х24 + х34 = 110,

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

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

F = 1∙ х11 +2 х12 +5 х13 +3 х14 +1 х21 +6 х22 +5 х23 +2 х24 +

+ 6∙х31 +3 х32 +7 х33 +4 х34 (2.1.4)

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

на множестве неотрицательных решений системы ограничений (2.1.1) и (2.1.2) найти такое решение Х*=( х*11, х*12, х*13, . . . х*33, х*34), при котором линейная функция (2.1.4) принимает минимальное значение.

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

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

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

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

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

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

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

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

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

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

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

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

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

Решение. Дадим максимально возможную поставку в клетку (1,1) – «северо-западный» угол таблицы поставок или, иными словами, переменной х11 максимально возможное значение: х11= min(60,20) = 20. Величину х11= 20 запишем в левом нижнем углу клетки (1,1) таблицы. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения. Теперь в таблице поставок найдем новый «северо-западный» угол – клетку (1,2) и дадим в нее максимально возможное значение с учетом того, что 1-й поставщик уже отдал 20 единиц груза и у него осталось 60-20 = 40 единиц груза, то есть, х12 = 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 эта особенность шагов метода «северо-западного» угла служит причиной того, что полученное распределение является базисным.

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



i>4
  • Далее ⇒
  •