Решение задач линейного программирования в среде Maple

Мы будем пользоваться способом минимальной стоимости (МС).

Изложим теперь алгоритм нахождения начального решения.

ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j - номер потребителя).

ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из a_i и потребности bj.

 

x_ij = min{ a_i, bj }

 

ШАГ З. Уменьшим запас a_i и потребность bj на величину перевозки x_ij, т.е.

 

a_i = a_i - x_ij,

bj =bj -x_ij

 

ШАГ 4. При исчерпании запаса (a_i = 0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности

(bj =0) запрещаем такие же  клетки вj-ом столбце.

В случае одновременного исчерпания запасов потребностей (ai =bj = 0) запрещаем  перевозки или в строке (тогда  считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас  равный нулю, который необходимо вывезти). Это делается для того, чтобы при  одновременном запрещении перевозок  в строке и столбце количество заполненных клеток таблицы не стало  меньшим, чем m+n-1.

Получим новую текущую  таблицу, в которую не входят заполненные  и запрещенные клетки. Если таблица  не пуста, переходим к шагу 1. (При  исчерпании таблицы - конец).

Способ минимальной  стоимости

1.Клетки с минимальной  ценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем  способе).

2 . x₃₂ = min{50,60} = 50

3. a ^'₃ =50-50=0, b ^'₂ = 100-50=50

4.Запрещаем строку 3.

 

 

1.  Клетка с min ценой ~ (2,3)

2.  x₂₃ = min{70,80} = 70

3.  a₂=70-70=0, b'₃ = 80-70=10

4.  Запрещаем строку 2.

 

	1	2	3
60	5 60	10	12
Χ	8 -	6 -	4 70
Χ	0	0 50	0 -
		50	10

 

1.  Клетка с min ценой ~ (1,1)

2.  x ₁₁=min{120,60} = 60

3.  a _1' =120-60 = 60, b_1' = 0

4.В первом столбце запрещать  уже нечего. Текущая таблица содержит  две клетки (1,2) и (1,3).

 

1.Выбираем клетку (1,2)

_2.x ₁₂ =min{110,100} = 100

3.a ₁ =110-100 = 10, b^'₁ = 0

4.Текущая таблица содержит  одну клетку (1,3).

 

 

1. Выбираем последнюю клетку(1,3)

2. x₁₃=min{10,10} = 10

3.a₁^' = b₃ = 0

4.Таблица исчерпана. Конец.

Переходим к описанию следующего шага метода потенциалов.

ШАГ 2. Проверка текущего плана на оптимальность.

Признаком того, что текущий  план перевозок является оптимальным, служит условие

 

(1)u_i +vj -c_ij ≤0

 

которое выполняется для  всех клеток таблицы. Неизвестные здесь  величины u_i и vj (называемые потенциалами) определяются из условий

(2)u_i + v_j = c_ij

 

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

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

Заполненные клетки Уравнения

 

(1,1) u₁ + v₁ =5

(1,2) u₁ + v₂ =10

(1,3) u₁ + v₃ =12

(2,3) u₂ +v₃ =4

(3,2) u₃ +v₂ =0

 

Положим, например, неизвестное u ₁ равным 0 (через него можно из первых трех уравнений найти v₁, v₂ и v₃). Последовательно из них находим u _{2 ,} u _3.

Этот метод можно сформулировать в виде единой правилы:

Неизвестный потенциал  находится вычитанием известного из цены перевозки в заполненной  клетке

Применим это правило  для определения u и v в нашем примере  и получим:

 

u₁ =0, u₂ =-8, u₃ =-6

v₁ =5, v₂ =10, v₃ =12

 

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

Проверим на оптимальность  имеющееся решение

 

(2,1) u₂+v₁-c₂₁=-8+5-8=-11<0

(2,2) u ₂ +v₂ -c₂₂=-8+10-6=-4<0

(3,1) u ₃ +v₁ -c₃₁=-10+ 5-0=-5<0

(3,3) u ₃ +v₃ -c₃₃=-10+12-0=2>0

 

Следовательно, условие оптимальности  нарушено в клетке (3,3).

Имеющийся план перевозок  можно улучшить.

Дадим описание заключительного  шага алгоритма метода потенциалов.

ШАГ 3 Улучшение плана перевозок.

Улучшение плана происходит путем назначения перевозки θ>0 в ту клетку (i , j) таблицы, в которой  нарушилось условие оптимальности. Но назначение ненулевой перевозки  нарушает условия баланса вывоза продукции от поставщика i (вывозит  весь запас и еще плюсθ>0 ) и  условия баланса привоза продукции  к потребителю j (получает все что  можно и еще плюс θ > 0). Условия  баланса восстанавливают путем  уменьшения вывоза от i-поставщика к  какому-то другому потребителю j (уменьшают  на θ перевозку в какой-то заполненной  клетке (i , j) строки i). При этом нарушается баланс привоза продукции к потребителю j (получает на θ меньше, чем ему  требуется). Восстанавливают баланс в столбце j, тогда он нарушается в некоторой строке i и т.д. до тех  пор, пока цикл перемещения перевозок  не замкнется на клетке, в которой  нарушалось условие оптимальности. Продемонстрируем эти рассуждения  на нашем примере.

 

 

120	60	50+ Ө	10- Ө
70	-	-	70
50	-	50- Ө	* + Ө
	60	100	80

 
 
 
 

120	60	60	-(0)
70	-	-	70
50	-	40	* 10
	60	100	80

 
 
 
 
 

1. Оптимальность нарушена  в клетке (3,3). Назначим в нее  перевозку θ>0 (+θ означает, увеличение  на θ).

2.Нарушается баланс вывоза  от поставщика 3 (вывозит 50+ θ, а  это больше его запаса!). Уменьшаем  на θ перевозку в заполненной  клетке строки 3 (вне заполненной  уменьшать нельзя, так как это  приведет к отрицательной перевозке).

Рассмотрим те клетки цикла  в которых уменьшаем на θ перевозку  и берём минимум из вычетаемых, у нас это min{10- θ ,50- θ }=10.

И данное число надо подставить в цикл

 

Список литературы

 

1. Матвеев В.А. Конечные  бескоалиционные игры и равновесия. Псков, 2004,176с.

2. Аладьев В.З., Богдявичюс  М.А. MAPLE 6: Решение математических, статистических  и физико – технических задач  – М.: Лаборатория Базовых Знаний,2001 – 824с..

3. Петросян Л.А., Зенкевич  Н.А., Семина Е.А. Теория игр.  М.:ВШ, Книжный дом «Университет», 1998.

4. Акулич И.Л. Математическое  программирование в примерах  и задачах. М.: Высшая школа, 1993.

5. Воробьёв Н.Н. Основы  теории игр. Бескоалиционные игры. М.: Наука, 1984.

6. Прохоров Г.В., Колбеев  В.В., Желнов К.И., Леденев М.А..Математический  пакет Maple V Release 4. М. 1998.