Решение задач линейного программирования в среде Maple (стр. 2 из 3)
x1>=0; x2>=0; x3>=0;
Данные задачи заносим в симплекс таблицу.
| x1 | x2 | x3 | x4 | x5 | x6 | значения | базис | оценка |
| 3 | 1 | 3 | 1 | 0 | 0 | 5 | x4 | 5/3 |
| 5 | 4 | 4 | 0 | 1 | 0 | 12 | x5 | 3 |
| 2 | 1 | 2 | 0 | 0 | 1 | 8 | x6 | 4 |
| 2 | 3 | 4 | 0 | 0 | 0 | 0 | - f |
В этой таблице первая, вторая и третья строки соответствуют ограничениям задачи, последняя строка – функция цели. Это оценочная строка. Значение функции цели берём 0. Выделяем базисные переменные. Эта переменная находиться в столбце, для которой имеется одна единица, остальные нули. В столбце «базис» отмечаем одноимённые переменные в той строке, где расположена эта единственная единица. Остальные переменные называются свободными.
По заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные переменные равны 0. Базисные переменные и значение функции находим из таблицы. Они представлены в столбце «значение». Отметим, что значение функции цели берём с противоположенным знаком. Итак, x° = (0,0,0,5,12,8) f° = 0.
В оценочной строке имеются положительные числа. Значит, решение можно улучшить. Выбираем наибольшее из положительных чисел. Если таких чисел несколько – берём любое из них. Соответствующий столбец называют ведущим. По ведущему столбу и столбцу «значения» определяем оценку для каждой строки. Число из столбца «значение» делим на строку. По условию задачи это положительное число. Объявляем ведущей строку ту, оценка у которой наименьшее положительное число.
В первой таблице ведущая строка и столбец выделен цветом. На их пересечении находится ведущий элемент. В нашем случае это 3.
Переходим к первой итерации. Её суть состоит в том, чтобы свободную x3 сделать базисной, а базисную переменную x4 - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получим:
| x1 | x2 | x3 | x4 | x5 | x6 | значения | базис | оценка |
| 1 | 1/3 | 1 | 1/3 | 0 | 0 | 5/3 | x3 | 5 |
| 1 | 8/3 | 0 | -4/3 | 1 | 0 | 16/3 | x5 | 2 |
| 0 | 1/3 | 0 | -2/3 | 0 | 1 | 14/3 | x6 | 14 |
| -2 | 5/3 | 0 | -4/3 | 0 | 0 | -20/3 | - f |
Из таблицы находим базисные переменные и значение функции x¹= (0,0,5/3,0,16/3,14/3) f¹ = 20/3. Этот результат можно проверить. Полученные результаты должны удовлетворять функции цели в канонической (стандартной) задаче линейного програмирования. В оценочной строке имеются положительные числа. Значит, решение можно улучшить. Аналогично строим следующую таблицу:
| x1 | x2 | x3 | x4 | x5 | x6 | значения | базис | оценка |
| 5/8 | 0 | 1 | 1/2 | -1/8 | 0 | 1 | x3 | - |
| 3/8 | 1 | 0 | -1/2 | 3/8 | 0 | 2 | x2 | - |
| -1/8 | 0 | 0 | -1/2 | -1/8 | 1 | 4 | x6 | - |
| -21/8 | 0 | 0 | -1/2 | -5/8 | 0 | -10 | - f |
f* = 10 x* = (0,2,1)
§5. Пример решения Транспортной задачи
Метод потенциалов представляет из себя модификацию симплекс-метода, учитывающую специфику транспортной задачи, поэтому его алгоритм не отличается от алгоритма симплекс-метода, за исключением шага проверки целевой функции на неограниченность на множестве решений. Отсутствие указанного шага в методе потенциалов обусловлено теоремой о том, что закрытая ТЗ всегда разрешима. Итак, алгоритм метода потенциалов для решения ТЗ состоит из следующих шагов:
ШАГ 1. Построение начального плана перевозок.
ШАГ 2. Проверка текущего плана на оптимальность.
Если план оптимален, то алгоритм завершен.
ШАГ 3. Улучшение плана перевозок. Переход к шагу 1.
Опишем алгоритм по шагам, иллюстрируя каждый шаг
ШАГ 1. Построение начального плана перевозок.
Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:
Клетка ( i , j ) таблицы соответствует коммуникации, связывающей i-го поставщика сj-м потребителем.
Построить начальный план перевозок означает - назначить объемы перевозок в клетки таблицы таким образом, чтобы:
а)число заполненных клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);
б)сумма перевозок в любой строке должна быть равна запасу соответствующего поставщика, а сумма перевозок в каждом столбце равна потребности потребителя. (Условие выполнения ограничений ТЗ). Существует несколько способов нахождения начального решения, которые отличаются только выбором клетки, в которую назначается очередная перевозка. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, что в большинстве случаев (но не всегда) приводит к более дешевому (а значит и более близкому к оптимальному) начальному плану перевозок.
Мы будем пользоваться способом минимальной стоимости (МС).
Изложим теперь алгоритм нахождения начального решения.
ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j- номер потребителя).
ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из aiи потребности bj.
xij = min{ai,bj}
ШАГ З. Уменьшим запас ai и потребность bjна величину перевозки xij, т.е.
ai = ai - xij,
bj =bj -xij
ШАГ 4. При исчерпании запаса (ai = 0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности
(bj =0) запрещаем такие же клетки вj-ом столбце.
В случае одновременного исчерпания запасов потребностей (ai =bj= 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n-1.
Получим новую текущую таблицу, в которую не входят заполненные и запрещенные клетки. Если таблица не пуста, переходим к шагу 1. (При исчерпании таблицы - конец).
Способ минимальной стоимости
1.Клетки с минимальной ценой (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем способе).
2 . x32= min{50,60} = 50
3. a'3 =50-50=0, b'2 = 100-50=50
4.Запрещаем строку 3.
1. Клетка с min ценой ~ (2,3)
2. x23 = min{70,80} = 70
3. a2=70-70=0, b'3 = 80-70=10
4. Запрещаем строку 2.
| 1 | 2 | 3 | |
| 60 | 560 | 10 | 12 |
| Χ | 8- | 6- | 470 |
| Χ | 0 | 050 | 0- |
| 50 | 10 |
1. Клетка с min ценой ~ (1,1)
2. x 11=min{120,60} = 60
3. a 1'=120-60 = 60, b1'= 0
4.В первом столбце запрещать уже нечего. Текущая таблица содержит две клетки (1,2) и (1,3).
1.Выбираем клетку (1,2)
2.x12 =min{110,100} = 100
3.a1 =110-100 = 10, b'1 = 0
4.Текущая таблица содержит одну клетку (1,3).
1. Выбираем последнюю клетку(1,3)
2. x13=min{10,10} = 10
3.a1' = b3 = 0
4.Таблица исчерпана. Конец.
Переходим к описанию следующего шага метода потенциалов.
ШАГ 2. Проверка текущего плана на оптимальность.
Признаком того, что текущий план перевозок является оптимальным, служит условие
(1)ui +vj -cij≤0
которое выполняется для всех клеток таблицы. Неизвестные здесь величины uiи vj(называемые потенциалами) определяются из условий
(2)ui + vj = cij
Условие (1) означает невозможность появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")
Так как заполненных клеток в таблице (m+n-1) штук, а неизвестных и (m+n) штук, то для их определения имеется система из (m+n-1) уравнений относительно (m+n) неизвестных. Чтобы найти решение (хотя бы какое-нибудь) такой системы, достаточно положить одно из неизвестных (произвольное) равным некоторому произвольно выбранному числу. Тогда остальные определяются единственным образом. Можно решать эту систему непосредственно (продолжаем работать с нашим "старым" примером и найдем потенциалы для начального плана, построенного способом МС).
Заполненные клетки Уравнения
(1,1) u1 + v1 =5
(1,2) u1 + v2 =10
(1,3) u1 + v3 =12
(2,3) u2 +v3 =4
(3,2) u3 +v2 =0
Положим, например, неизвестное u1 равным 0 (через него можно из первых трех уравнений найти v1, v2 и v3). Последовательно из них находим u2 ,u3.