Лекция МПС №3 от 30.10.2012

Линейное программирование

Нахождение начального опорного плана задач линейного программирования
\
Пусть в системе ограничений имеется единичный неотрицательный базис. Например, задача ЛП имеет вид:
Целевая функция 13 EMBED Equation.3 1415 (2.21)
Система ограничений
13 EMBED Equation.3 1415 (2.22)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.23)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.24)
Говорят, что ограничение-равенство канонической задачи ЛП имеет предпочтительный вид, если при неотрицательности его правой части левая часть содержите переменную с единичным коэффициентом, которая во все остальные ограничения входит с коэффициентами, равными 0. Если каждое ограничение канонической задачи имеет предпочтительный вид (т.е. система ограничений приведена к единичному неотрицательному базису), то начальный опорный план (т.е. неотрицательное базисное решение) строится следующим образом. Предпочтительные переменные выбираются в качестве базисных, а все остальные - в качестве свободных переменных. Свободные переменные приравниваются нулю: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, тогда базисные переменные будут равны свободным членам: 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. Начальный опорный план задачи будет иметь вид:
13 EMBED Equation.3 1415
Пусть задача ЛП представлена в симметричном виде, т.е.
13 EMBED Equation.3 1415 (2.25)
13 EMBED Equation.3 1415 (2.26)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.27)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.28)
Привести систему ограничений к единичному неотрицательному базису можно, прибавляя к левым частям ограничительных неравенств неотрицательные элементы 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415 (2.29)
13 EMBED Equation.3 1415 (2.30)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.31)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.32)
Полученная система ограничений эквивалентна исходной и имеет предпочтительный вид. Аналогично свободные переменные приравниваются нулю, а предпочтительные (базисные) переменные равны свободным членам. Начальный опорный план задачи будет иметь вид:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Пусть задача ЛП представлена в следующей симметричной форме, т.е.
13 EMBED Equation.3 1415 (2.33)
13 EMBED Equation.3 1415 (2.34)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.35)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.36)
Привести задачу к каноническому виду можно, рассматривая целевую функцию с противоположным знаком и вычитая из левых частей системы ограничений балансовые переменные 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415:
13 EMBED Equation.3 1415 (2.37)
13 EMBED Equation.3 1415 (2.38)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.39)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.40)
Тогда начальный план
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Пусть задача ЛП приведена к каноническому виду, однако система ограничений не имеет единичного неотрицательного базиса:
13 EMBED Equation.3 1415 (2.41)
13 EMBED Equation.3 1415 (2.42)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.43)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.44)
Для получения предпочтительного вида вводят неотрицательные искусственные переменные и рассматривают вспомогательную w-задачу:
13 EMBED Equation.3 1415 (2.45)
13 EMBED Equation.3 1415 (2.46)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, (2.47)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.48)
Ее начальный план будет
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
Симплекс-метод решения задач линейного программирования
\Одним из универсальных методов решения задач ЛП является симплекс-метод или метод последовательного улучшения плана. Если задача разрешима, то ее оптимальный план совпадает, по крайней мере, с одним из опорных решений системы ограничений. Именно этот опорный план и отыскивается симплекс-методом в результате упорядоченного перебора опорных решений. Упорядоченность понимается в том смысле, что при переходе от одного опорного плана к другому соответствующие им значения целевой функции возрастают (не убывают). Так как общее число опорных решений конечно, то через определенное число шагов будет либо найден опорный план, либо установлена неразрешимость задачи. Чтобы получить новый опорный план, первоначальный базис преобразовывают в новый. Для этого из первоначального базиса удаляют некоторую базисную переменную и вместо нее вводят другую из группы свободных.
С геометрической точки зрения перебор опорных планов можно толковать как переход по ребрам от одной вершины многогранника решений к другой по направлению к вершине 13 EMBED Equation.3 1415, в которой целевая функция достигает оптимального значения.
Этапы решения задачи ЛП симплекс-методом:
Задача должна быть приведена к каноническому виду, притом все элементы столбца свободных членов должны быть неотрицательными.
Найден начальный опорный план задачи.
Целевая функция выражена через свободные члены и максимизирована.
По симплексному методу находится оптимальный план задачи.
Нахождение оптимального опорного плана
Пусть система ограничений имеет предпочтительный вид, т.е. найден начальный опорный план задачи. Не ограничивая общности, предположим:
13 EMBED Equation.3 1415 (2.49)
13 EMBED Equation.3 1415 (2.50)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.51)
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415. (2.52)
Исключим базисные переменные из целевой функции. Для этого выразим их через свободные переменные из ограничительных уравнений:
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415,
и подставим в выражение функции Z. Получим приведенные коэффициенты целевой функции:
13 EMBED Equation.3 1415.
Составим исходную симплекс-таблицу, записывая приведенные коэффициенты целевой функции в z-строку с противоположными знаками, а константу 13 EMBED Equation.3 1415 со своим знаком.
Симплекс-таблица:

Если в z-строке симплекс-таблицы, содержащей некоторый опорный план, нет отрицательных элементов (не считая свободного члена 13 EMBED Equation.3 1415), то данный план оптимален и задача решена. К тому же, если в z-строке симплекс-таблицы, содержащей оптимальный план, нет нулевых элементов (не считая 13 EMBED Equation.3 1415 и элементов соответствующих базису), то оптимальный план единственный. В противном случае задача ЛП имеет бесконечное множество решений.
Если в z-строке есть хотя бы один отрицательный элемент (не считая 13 EMBED Equation.3 1415), а в любом столбце есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отрицательным элементом 13 EMBED Equation.3 1415 в z-строке берут за разрешающий (если в z-строке отрицательных элементов несколько, то за разрешающий выбирают столбец с наименьшим элементом). Следовательно, столбец с номером m+k станет ведущим или разрешающим и переменная 13 EMBED Equation.3 1415будет включена в базис.
Среди элементов ведущего столбца находят положительные. Если таковых нет, то задача не имеет решений в силу неограниченности целевой функции 13 EMBED Equation.3 1415.
Для положительных элементов 13 EMBED Equation.3 1415 подсчитывают симплексные отношения (отношения свободных членов к соответствующим положительным элементам ведущего столбца) 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415, и выбирают среди них наименьшее. Пусть минимальное отношение будет в строке l. Строка с номером l станет ведущей (разрешающей), а элемент 13 EMBED Equation.3 1415 - ведущим. Переменная 13 EMBED Equation.3 1415 выйдет из базиса.
Выполняют одну итерацию по замещению базисной переменной методом Жордана-Гаусса. Строят новую симплексную таблицу и переходят к первому пункту.
Опорное решение называется невырожденным, если все его компоненты положительные, в противном случае оно называется вырожденным. Задача ЛП называется невырожденной, если все ее опорные планы невырожденные. Если среди опорных решений есть хотя бы одно вырожденное, то задача называется вырожденной. В это случае возможен вариант, когда значение целевой функции при переходе от одного плана к другому не улучшится и может произойти зацикливание. Для избежания этого фактора изменяют последовательность вычислений путем изменения разрешающего столбца.

Пример 4.
Решить задачу из примера 1 симплекс-методом:
Решение.
задача приведена к каноническому виду, причем все элементы столбца свободных членов неотрицательны
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
найден начальный опорный план задачи 13 EMBED Equation.3 1415, 13 EMBED Equation.3 1415.
целевая функция выражена через свободные переменные и максимизирована 13 EMBED Equation.3 1415.
составим исходную симплекс-таблицу, определяем ведущий столбец и ведущую строку и выполняем шаг метода Жордана-Гаусса



продолжаем так же до тех пор, пока в z-строке все элементы не станут неотрицательными

13 EMBED Equation.3 1415, но свободной переменной 13 EMBED Equation.3 1415 соответствует нулевой элемент в z-строке, поэтому продолжаем
получаем

13 EMBED Equation.3 1415
Для исходной задачи
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415
13 EMBED Equation.3 1415

Root EntryEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeHлEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeEquation NativeРисунок 1422Рисунок 1423Рисунок 1436Equation NativeEquation Native

Приложенные файлы

  • doc 8981826
    Размер файла: 325 kB Загрузок: 0

Добавить комментарий