ТЗ линейного программирования. Постановка задачи

Транспортная задача линейного программирования формулирует­ся следующим образом.

Имеется m пунктов отправления (ПО): A₁, A₂, …, A_m, в ко­торых сосредоточены запасы какого-то однородного груза в количест­ве соответственно a₁, a₂, …, a_m единиц. Кроме того, имеется пунктов назначения (ПН): B₁, B₂, …, B_n подавших заявки соот­ветственно на b₁, b₂, …, b_n, единиц груза.

Предполагается, что сумма всех заявок равна сумме всех запа­сов:

a_i = b_j (3.1)

Известна стоимость С_ij перевозки единицы груза от каждого пункта отправления A_i до каждого пункта назначения В_j. Таблица (матрица) стоимостей перевозки С_ij задана:

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

При такой постановке задачи показателем эффективности плана перевозок является стоимость; поэтому поставленную задачу точнее называют транспортной задачей по критерию стоимости.

Дадим этой задаче математическую формулировку. Обозначим x_ij- количество груза, отправляемого из i-го пункта отправле­ния в j-й пункт назначения B_j.

Неотрицательные переменные, число которых равно m*n, должны удовлетворять следующим ус­ловиям.

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

x_1j =a₁,

x_2j =a₂, (3.2)

………….

x_mj =a_m,

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

x_i1=b₁,

x_i2=b₂, (3.3)

…………

x_in=b_n,

Условия (3.2), (3.3) называются "балансовыми условиями".

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

L= С_ij x_ij = min (3.4)

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

Данная задача имеет некоторые особенности, позволяющие ре­
шить ее вручную простыми табличными методами. Во-первых, все коэффициенты при переменных в уравнениях (3.2), (3.3) равны едини­це. Во-вторых, не все m+n уравнений задачи являются независимыми. Действительно, складывая между собой все уравнения (3.2) и
все уравнения (3.3), мы должны получить одно и то же в силу условия (3.1). Таким образом, условия (3.2), (3.3) связаны одной линейной зависимостью и фактически из этих уравнений только m, а не n являются линейно независимыми. Значит, ранг r системы уравнений (3.2), (3.3) равен

r=m+n-1

а, следовательно, можно разрешить эти уравнения относительно m+n-1 базисных переменных, выразив их через остальные, свобод­ные, количество которых равно

K=mn-(m+n-1) = (m-1) (n-1)

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

Условимся о терминологии. Значения x_ij количества единиц груза, направляемых из пункта A_i в пункт B_j, будем называть перевозками.

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

План x_ij будем называть допустимым, если он удовлетворяет условиям (3.2), (3.3): все заявки удовлетворены, все запасы исчерпаны.

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

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

Перейдем к изложению табличных методов решения транспортной задачи (ТЗ), которые сводятся к более простым операциям с так на­зываемой транспортной таблицей, где в определенном порядке записаны все исходные условия ТЗ.

Образец транспортной таблицы дан в табл. 3.1, где стоимости перевозок единицы груза из ПО A_i в ПН B_j помещаются в правом верхнем углу каждой клетки таблицы, о тем, чтобы в самой клетке при составлении плана помещать перевозки x_ij. Таблица 3.1

ПО ПН	B1	B2	…	Bn	Запасы
A1	C11	C12	…	C1n	a1
A2	C21	C22	…	C2n	a2
	…	…	…	…
Am	Cm1	Cm2	…	Cmn	a
заявки	b1	b2	…	bn	ai bj

В правом столбце помещены запасы товара в каждом ПО, в ниж­ней строке - заявки, поданные каждым ПН. В правой нижней клетке таблицы записывается сумма запасов, равная сумме заявок.

Как показано выше, в каждом опорном плане, включая оптималь­ный, будут отличны от нуля не более чем m+n-1 перевозок. Клетки таблицы, в которых записываются эти отличные от нуля пере­возки, условимся называть базисными, а остальные (пус­тые) - свободными.

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

- сумма перевозок в каждой отроке таблицы должна быть равна запасу данного ПО;

- сумма перевозок в каждом столбце должна быть равна заявке данного ПН;

- общая стоимость перевозок - минимальная.

В дальнейшем все действия по нахождению решения ТЗ будут сводиться к преобразованию транспортной табл. 3.1. При описании этих преобразований будем пользоваться нумерацией клеток таблицы, подобной нумерации клеток шахматной доски. Клеткой A_iB_j или, короче, клеткой (i, j) будем называть клетку, стоящую в i-й строке и j-м столбце транспортной таблицы.

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

Частные случаи транспортной задачи

В рассмотренных выше случаях число заявок равнялось числу запасов. Чаще всего бывает не так.

1) Число запасов превышает число заявок. В этом случае необ­ходимо ввести дополнительный фиктивный пункт потребления с нуле­выми стоимостями перевозок (т.е. везти никуда не надо). Далее за­дача решается обычным способом, но часть запасов окажется не вос­требованной.

2) Число заявок превышает число запасов. В этом случае вво­дится фиктивный пункт производства с нулевыми стоимостями перевоз­ки. Задача решается также обычно, только некоторые пункты потребления не дополучат требуемое, но стоимость всей операции все равно получится минимальной.

10. Построение опорной задачи: метод северо-западного угла и наименьших стоимостей

Пример 1. Условия ТЗ заданы транспортной табл. 3.2.

2. Требуется найти опорное решение ТЗ (построить опорный план).

Решение. Будем заполнять табл.3.2 перевозками постепенно, начиная с левой верхней клетки (1,1) ("северо-западного угла" таблицы). Будем рассуждать при этом следующим образом. Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте A₁, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта В₁, удовлетворена, а в пункте A₁ осталось еще 30 единиц груза. Удовлетворим за счет их заявку пункта В₂ (27 единиц), запишем 27 в клетку (1,2); оставшиеся 3 единицы груза пункта A₁ назначим пункту B₃. В составе заявки пункта B₃ остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта A₂, чем его запас будет ис­черпан, и еще 9 возьмем из пункта А₃. Таблица 3.2

ПО ПН	B1	B2	B3	B4	B5	Запасы
A1	10	8	5	6	9
A2	6	7	8	6	5
A3	8	7	10	8	7
A4	9	5	4	6	8
Заявки bj

Из оставшихся 18 единиц пункта A₃ 12 выделим пункту B₄; ос­тавшиеся 6 единиц назначим пункту B₅, что вместе со всеми 20 единицами пункта A₄ покроет его заявку (табл.3.3). Таблица 3.3

ПО ПН	B1	B2	B3	B4	B5	Запасы
A1	18 10	27 8	3 5	6	9
A2	6	7	30 8	6	5
A3	8	7	9 10	12 8	6 7
A4	9	5	4	6	20 8
Заявки bj

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

Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является не
только допустимым; но и опорным решением транспортной задачи. Действительно, число базисных клеток таблицы, в которых стоят ненуле­вые перевозки, удовлетворяет условию m+n-1=8. Остальные клетки - свободные (пустые), в них стоят нулевые перевозки и их число равно 12. Значит, наш план - опорный и по­ставленная задача построения опорного плана решена.

Однако полученный опорный план не является оптимальным, по­скольку при его построении мы совсем не учитывали стоимостей пе­ревозок С_ij. Стоимость этого плана, которая найдется, если умножить каждую перевозку на соответствующую стоимость, равна

18.10+ 27.8 + 3.5 + 30.8 + 9.10 + 12.8 + 6.7 + 20.8 = 1039.

Прежде чем рассматривать способы улучшения опорного плана и обеспечения его оптимальности, опишем еще один способ нахожде­ния опорного плана называемый способом "минимальных стоимостей перевозок". В этом случае в матрице стоимостей перевозки (матрице затрат) отыскиваем минимальный элемент и в первую очередь включа­ем в план самую дешевую перевозку, притом в максимально возмож­ном объеме. Обращаясь к исходным данным табл.3.2, в план включаем перевозку 20 единиц груза из ПО А₄ в ПН B₄ со стоимостью 4, что полностью исчерпывает запас ПО A₄. Следующий по величине элемент матрицы затрат (5), расположенный в нескольких клетках таблицы, определяет включение в план перевозки между пунктами A₂ и B₅, где объем перевозки наибольший (26), и затем перевозки между пунктами A₁ и В₃ объемом 22 единицы, что удовлетворяет заяв­ки пунктов B₃, и В₅. Далее планируются перевозки со стоимостью 6 между пунктами A₁ и B₄ объемом 15 единиц и пунктами A₂ и B₁ объемом 4 единицы. Продолжая действовать аналогичным образом и дальше, придем к плану перевозок табл.3.4.

В том, что полученный план перевозок допустимый, легко убе­диться, проверив, что суммы элементов в каждой отроке табл. 3.4 равны соответствующим запасам, а суммы по столбцам - заявкам. По­скольку число базисных (ненулевых) клеток равно m+n-1=8, а число свободных (нулевых) равно (n-1)(m-1)=12, где m=4, n=5, построенный план перевозок является не только допустимым, но и опорным. Затраты на реализацию этого плана составляют

11.10 + 4.6 + 3.8 + 24.7 + 22.5 + 2074 + 26.5 = 736.

Таблица 3.4

ПО ПН	B1	B2	B3	B4	B5	Запасы
A1	11 10	8	22 5	15 6	9
A2	4 6	7	8	6	26 5
A3	3 8	24 7	10	8	7
A4	9	5	20 4	6	8
Заявки bj

Рассмотренный способ построения опорного плана прост, но в ряде случаев приводит к опорному" решению, которое значительно от­личается от оптимального. Лучшего результата можно добиться c по­мощью метода наименьшей стоимости. Из всех цен за единицу перевоз­ки выбираем наименьшую – 4 (A₄-B₃). В эту клетку включаем максимально возможную перевозку из пункта A₄- 20. Во всех ос­тальных клетках этой отроки будут нули, т.к. в пункте A₄ ниче­го не осталось. Пункт B₃ нуждается в 42 ед., 20 он уже получил. В этом столбце следующая минимальная стоимость перевозки – 5(A₁-B₃). В это место нужно поставить недостающее количество груза (22), поставив в остальных клетках этого столбца нули. Продолжая в этом же духе, получим следующую таблицу.

Таблица 3.5