8. Метод больших штрафов

На этом шаге мы рассмотрим М-метод решения задач линейного программирования. 

    Пусть задача линейного программирования записана в стандартной форме. Для любого равенства i в котором не содержится дополнительная остаточная переменная, введем искусственную переменную R_i, которая далее войдет в начальное базисное решение. Но поскольку эта переменная искусственная (другими словами, не имеет никакого "физического смысла" в данной задаче), необходимо сделать так, чтобы на последующих итерациях она обратилась в нуль. Для этого в выражение целевой функции вводят штраф.

    Переменная R_i, с помощью достаточно большого положительного числа М, штрафуется путем ввода в целевую функцию выражения –MR_i в случае максимизации целевой функции и выражения +MR_i — в случае минимизации. Вследствие этого штрафа естественно предположить, что процесс оптимизации симплекс-метода приведет к нулевому значению переменной R_i. Далее следует применить симплекс-метод.

    При использовании М-метода следует обратить внимание на следующие два обстоятельства.

1. Использование штрафа М может и не привести к исключению искусственной переменной в конечной симплекс-итерации. Если исходная задача линейного программирования не имеет допустимого решения (например, система ограничений несовместна), тогда в конечной симплекс-итерации, по крайней мере, одна искусственная переменная будет иметь положительное значение. Это "индикатор" того, что задача не имеет допустимого решения.

2. Теоретически применение М-метода требует, чтобы М → ∞. Однако с точки зрения компьютерных вычислений величина М должна быть конечной и, вместе с тем, достаточно большой. Величина М должна быть настолько большой, чтобы выполнять роль "штрафа", но не слишком большой, чтобы не уменьшить точность вычислений. На практике вы должны помнить о возможных ошибках машинного округления при выполнении вычислений, в которых совместно участвуют как большие, так и малые числа.

    На следующем шаге рассмотрим решение задачи линейного программирования М-методом.

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

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

Имеется 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) Число заявок превышает число запасов. В этом случае вво­дится фиктивный пункт производства с нулевыми стоимостями перевоз­ки. Задача решается также обычно, только некоторые пункты потребления не дополучат требуемое, но стоимость всей операции все равно получится минимальной.