Курсовая работа: Решение задач линейного программирования в среде Maple
.
Неизвестные потенциалы 
и 
(их общее количество равно m + n) могут быть найдены (и именно так отыскиваются) из условия равенства нулю оценок для базисных переменных (заполненных клеток таблицы) ТЗ (таких равенств (m+n - 1), что следует из замечания ниже).
,
для заполненных клеток (i,j) таблицы ТЗ.
Решение полученной системы (содержащей неизвестных на единицу больше, чем число уравнений) ищется, когда одно из неизвестных (вообще говоря, любое) полагается равным некоторому числу (тоже, вообще говоря, любому). После этого оставшаяся система имеет единственное решение.
§4. Пример решения задача линейного программирования
Решим задачу линейного программирования симплекс – методом :
f(x) = 2 x 1 + 3 x 2 + 4 x 3 → max
3x1 + x2 + 3x3 <=5
5 x 1 + 4 x 2 + 4 x 3 <=12
2 x 1 + x 2 + 2 x 3 <=8
x 1 >=0; x 2 >=0; x 3 >=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.
Переходим к первой итерации. Её суть состоит в том, чтобы свободную x 3 сделать базисной, а базисную переменную x 4 - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получим:
| 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. Построение начального плана перевозок.
Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид: