шпаргалка

ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛП

[ Назад ]

3.4. Специальная задача ЛП.

Специальной задачей ЛП (СЦЛП) называется задача ЛП, удовлетворяющая условиям :

1. Это каноническая задача ЛП.

2. Система линейных ограничений есть система с базисом.

3. Целевая функция выражается только через небазисные переменные.

СЗЛП имеет таким образом следующий вид



Замечание о начальном базисном решении

Если в СЗЛП i=1,..., m, то вектор



является допустимым базисным решением СЗЛП.

Доказательство

1. х- допустим, так как х удовлетворяет всем линейным ограничениям и (так как все по условию)

2. х- базисное решение, так как система векторов столбцов



Замечание доказано.



Допустимой СЗЛП называется СЗЛП, в которой i=1,..., m.



Каждой СЗЛП соответствует симплексная таблица

Строка L называется индексной строкой.

Симплексная таблица называется допустимой, если все элементы b1,...,bm неотрицательны.Допустимой симплексной таблице соответствует допустимое базисное решение



Значение целевой функции



Две симплексные таблицы называются эквивалентными, если соответствующие им специальные задачи ЛП эквивалентны.



3.5Правила преобразования симплексных таблиц

Для решения СЗЛП применяется симплекс-метод Данцига (1974 г.).

Поскольку каждой допустимой СЗЛП соответствует допустимое базисное решение, то переходу от одного допустимого базиса к другому соответствует переход от одной СЗЛП к другой СЗЛП, или переход от одной симплекс-таблице к эквивалентной ей симплекс-таблице. Такой переход осуществляется до тех пор, пока не будет найдена СЗЛП с оптимальным базисным решением.

Таким образом, одна итерация симплекс-метода состоит в преобразовании допустимой симплекс-таблицы в эквивалентную ей допустимую симплекс-таблицу. Эти преобразования являются обычными гауссовскими преобразованиями строк системы линейных уравнений и состоят в том, что некоторая небазисная переменная



вводится в базис вместо некоторой базисной переменной

.

Столбец q и строка p называются ведущими и выбираются по следующим правилам.

Правило выбора ведущего столбца q

В базис вводится переменная



Правило выбора ведущей строки р.

Из базиса выводится переменная



для которой выполняется ключевое отношение :



Преобразование симплексной таблицы осуществляется по следующим правилам.

Формулы пересчета симплекс-таблицы



2) Ведущая строка p делится на ведущий элемент





3) Ведущий столбец q делится на ведущий элемент с противоположным знаком



4) Оставшиеся строки преобразуются по правилу : из строки вычитается поделенная на



строка р (или новая ведущая строка , j=m+1,...,n), умноженная на коэффициент



5) Индексная строка пересчитывается по тому же правилу :



Схему преобразования элементов симплекс-таблицы (кроме ведущей строки и ведущего столбца) называют схемой ”прямоугольника”.



Преобразуемый элемент



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



3.6 Пример

Убедимся на примере, что преобразования симплексной таблицы 1) -5) действительно соответствуют гаусовским преобразованиям системы уравнений.

Рассмотрим задачу ЛП



Этой задаче соответствует симплекс-таблица



Пусть переменная выводится из базиса, а переменная вводится в базис. Тогда строка ведущая, столбец ведущий, а элемент - ведущий элемент.

После преобразований 1)- 5) получим новую симплекс-таблицу

Гауссовские преобразования соответствующей системы уравнений состоят в следующем.

Из строки



выражается переменная , в результате получаем значение соответствующей ведущие строке симплексной таблицы :



Затем полученные значения подставляем во все ограничения и в целевую функцию для исключения из них переменной . К примеру, после подстановки выражения в первое уравнение



получим выражение



что соответствует строке для x1в новой симплекс-таблице. Не составляет особого труда проверка остальных строк симплекс-таблицы.

Таким образом, преобразования симплекс-таблицы соответствуют гауссовским преобразованиям соответствующей системы линейных уравнений.



3.7Теоретические основы симплекс-метода

Критерий оптимальности

Если в индексной строке допустимой симплексной таблицы то соответствующее допустимое базисное решение является оптимальным решением.

Доказательство.

На базисном решении



целевая функция имеет значение



Рассмотрим любое допустимое решение



Тогда



поскольку



Для любого допустимого решения х' получили неравенство

что означает оптимальность решения х.

Критерий доказан



3.8 Критерий неограниченности целевой функции.

Пусть существует для которого столбец



Тогда целевая функция L неограничена сниузу на допустимом множестве.

Доказательство.

Рассмотрим для t>0 вектор



, где

Для любого t>0 вектор допустим, так как



и выполняются ограничения-равенства А =b. Но значение целевой функции



неограниченно убывает при так как



Значит L(x) не ограничена снизу на допустимом множестве.

Критерий доказан



3.9Теорема о ключевом отношении

Если переменная вводится в базис вместо переменной , для которой выполняется ключевое отношение



, то в новой симплексной таблице все е.у. новая таблица является допустимой.

Доказательство.

Новой симплексной таблице с элементами



соответствует новое базисное решение



Докажем, что

i=1,..., m.



Теорема доказана



3.10Теорема об улучшении базисного решения

Если существует для некоторого i=1,..., m, то возможен переход к эквивалентной допустимой симплексной таблице, причем значение целевой функции на новом базисе не больше значения целевой функции на старом базисе.

Доказательство.

Значение целевой функции в исходной симплекc-таблице



Значение целевой функции в новой симплекс-таблице

Так как т.е. значение целевой функции при переходе к новому базису возрастает.

Теорема доказана



3.11Алгоритм симплекс-метода.

Подготовительный этап

Приводим задачу ЛП к виду





Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче :



Заметим, что этой таблице соответствует допустимое базисное решение



задачи ( I ). Значение целевой функции на этом решении





Шаг 1. Проверка на оптимальность.

Если среди элементов симплексной таблицы



нет ни одного положительного элемента



то оптимальное решение задачи ЛП найдено :



Алгоритм завершает работу.



Шаг 2. Проверка на неразрешимость.

Если среди элементов симплексной таблицы



есть положительный



а в соответствующем столбце



нет ни одного положительного элемента



то целевая функция L является неограниченной снизу на допустимом множестве. В этом случае оптимального решения не существует. Алгоритм завершает работу.



Шаг 3. Выбор ведущего столбца q.

Среди элементов симплексной таблицы



выбираем максимальный положительный элемент



Этот столбец объявляем ведущим (разрешающим).



Шаг 4. Выбор ведущей строки р.

Среди положительных элементов столбца



находим элемент



для которого выполняется равенство :



строку р объявляем ведущей (разрешающей). Элемент



объявляем ведущим (разрешающим).



Шаг 5. Преобразование симплексной таблицы.

Составляем новую симплексную таблицу, в которой :









д) оставшиеся элементы симплексной таблицы

преобразуются по следующей схеме “прямоугольника”.

Из элемента вычитается произведение трех сомножителей :

первый сомножитель - соответствующий ( в той же строке, где и преобразуемый элемент) элемент ведущего столбца;

второй сомножитель - соответствующий ( в том же столбце, где и преобразуемый элемент) элемент ведущей строки;

третий сомножитель - обратная величина ведущего элемента



Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами“прямоугольника”.



Шаг 6. Переход к следующей итерации осуществляется переходом к шагу 1.



3.12Пример.

Решить задачу ЛП, записанную в виде (17)



Составим соответствующую симплексную таблицу





Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение



не является оптимальным. Значение целевой функции для этого базиса L = 0.

Выбираем ведущий столбец - это столбец, соответствующий пере-

менной

Выбираем ведущую строку. Для этого находим



Следовательно, ведущая строка соответствует переменной

Проводим преобразование симплексной таблицы, вводя переменную в базис и выводя переменную из базиса. Получим таблицу



Одна итерация метода завершена. Переходим к новой итерации, Полученная таблица неоптимальна. Базисное решение, соответствующее таблице, имеет вид



Значение целевой функции на этом базисе L = -2.

Ведущий столбец здесь - столбец, соответствующий переменной Ведущая строка - строка, соответствующая переменной После проведения преобразований получим симплексную таблицу





Еще одна итерация завершена. Переходим к новой итерации.

Строка целевой функции не содержит положительных значений, значит соответствующее базисное решение



является оптимальным и алгоритм завершает работу.

Математическое программирование 1. Общая задача линейного программирования (ЗЛП): Здесь (1) называется системой ограничений , ее матрица имеет ранг r ? n, (2) - функцией цели (целевой функцией). Неотрицательное решение (х10, x20, ... , xn0) системы (1) называется допустимым решением (планом) ЗЛП. Допустимое решение называется оптимальным, если оно обращает целевую функцию (2) в min или max (оптимум). 2. Симплексная форма ЗЛП. Для решения ЗЛП симплекс - методом необходимо ее привести к определенной (симплексной) форме: (2') f+cr+1xr+1 + ... + csxs + ... + cnxn = b0 ® min Здесь считаем r < n (система имеет бесчисленное множество решений), случай r = n неинтересен: в этом случае система имеет единственное решение и если оно допустимое, то автоматически становится оптимальным. В системе (1') неизвестные х1, х2, ... , хr называются базисными (каждое из них входит в одно и только одно уравнение с коэффициентом +1), остальные хr+1, ... , xn - свободными. Допустимое решение (1') называется базисным (опорным планом), если все свободные неизвестные равны 0, а соответствующее ему значение целевой функции f(x10, ... , xr0,0, ... ,0) называется базисным. В силу важности особенностей симплексной формы выразим их и словами: а) система (1') удовлетворяет условиям : 1) все ограничения - в виде уравнений; 2) все свободные члены неотрицательны, т.е. bi ? 0; 3) имеет базисные неизвестные; б) целевая функция (2') удовлетворяет условиям : 1) содержит только свободные неизвестные; 2) все члены перенесены влево, кроме свободного члена b0; 3) обязательна минимизация (случай max сводится к min по формуле max f = - min(-f)). 3) Матричная форма симплекс-метода. Симплексной форме ЗЛП соответствует симплекс - матрица : 1 0 ... 0 ... 0 a1,r+1 ... a1s ... a1n b1 0 1 ... 0 ... 0 a2,r+1 ... a2s ... a2n b2 ................................................................. 0 0 ... 1 ... 0 ai,r+1 ... ais ... ain bi ................................................................. 0 0 ... 0 ... 1 ar,r+1 ... ars ... arn br 0 0 ... 0 ... 0 cr+1 ... cs ... cn b0 Заметим, что каждому базису (системе базисных неизвестных ) соответствует своя симплекс - матрица , базисное решение х = (b1,b2, ... ,br, 0, ... ,0) и базисное значение целевой функции f(b1,b2, ... ,br, 0, ... ,0) = b0 (см. Последний столбец !). Критерий оптимальности плана . Если в последней (целевой) строке симплекс-матрицы все элементы неположительны, без учета последнего b0, то соответствующий этой матрице план оптимален, т.е. сj ? 0 (j = r+1, n) => min f (b1, ... ,b2,0, ... ,0) = b0. Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец (S-й), в котором последний элемент сs > 0, a все остальные элементы неположительны, то ЗЛП не имеет оптимального плана, т.е. сs > 0, ais ? 0 ( i= 1,r ) => min f = -?. Если в симплекс-матрице не выполняются оба критерия, то в поисках оптимума надо переходить к следующей матрице с помощью некоторого элемента ais > 0 и следующих преобразований (симплексных): 1) все элементы i-й строки делим на элемент a+is; 2) все элементы S-го столбца, кроме ais=1, заменяем нулями; 3) все остальные элементы матрицы преобразуем по правилу прямоугольника, что схематично показано на фрагменте матрицы и дано в формулах: akl' = akbais - ailaks = akl - ailaks; ais ais bk' = bkais - biaks; cl' = clais - csail ais ais Определение. Элемент ais+ называется разрешающим, если преобразование матрицы с его помощью обеспечивает уменьшение (невозрастание) значения, целевой функции; строка и столбец, на пересечении которых находится разрешающий элемент, также называются разрешающими. Критерий выбора разрешающего элемента. Если элемент ais+ удовлетворяет условию bi = min bk ais0 aks0+ где s0 - номер выбранного разрешающего столбца, то он является разрешающим. 4. Алгоритм симплекс-метода (по минимизации). 1) систему ограничений и целевую функцию ЗЛП приводим к симплексной форме; 2) составим симплекс-матрицу из коэффициентов системы и целевой функции в симплексной форме; 3) проверка матрицы на выполнение критерия оптимальности; если он выполняется, то решение закончено; 4) при невыполнении критерия оптимальности проверяем выполнение критерия отсутствия оптимальности; в случае выполнения последнего решение закончено - нет оптимального плана; 5) в случае невыполнения обоих критериев находим разрешающий элемент для перехода к следующей матрице, для чего : а) выбираем разрешающий столбец по наибольшему из положи тельных элементов целевой строки; б) выбираем разрешающую строку по критерию выбора разрешающего элемента; на их пересечении находится разрешающий элемент; 6) c помощью разрешающего элемента и симплекс-преобразований переходим к следующей матрице; 7) вновь полученную симплекс-матрицу проверяем описанным выше способом (см. п. 3) Через конечное число шагов, как правило получаем оптимальный план ЗЛП или его отсутствие Замечания. 1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения при симплекс-преобразованиях. 2) преобразования - вычисления удобно начинать с целевой строки; если при этом окажется, что выполняется критерий оптимальности, то можно ограничиться вычислением элементов последнего столбца. 3) при переходе от одной матрицы к другой свободные члены уравнений остаются неотрицательными; появление отрицатель ного члена сигнализирует о допущенной ошибке в предыдущих вычислениях. 4) правильность полученного ответа - оптимального плана - проверяется путем подстановки значений базисных неизвестных в целевую функцию; ответы должны совпасть. 5. Геометрическая интерпретация ЗЛП и графический метод решения (при двух неизвестных) Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы. Целевая функция f = c1x1 + c2x2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с1,с2). Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают. На этих утверждениях основан графический метод решения ЗЛП. 6. Алгоритм графического метода решения ЗЛП. 1) В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений; 2) найти полуплоскости решения каждого неравенства системы (обозначить стрелками); 3) найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;



?

КАТЕГОРИИ:

Network | английский | архитектура эвм | астрономия | аудит | биология | вычислительная математика | география | Гражданское право | демография | дискретная математика | законодательство | история | квантовая физика | компиляторы | КСЕ - Концепция современного естествознания | культурология | линейная алгебра | литература | математическая статистика | математический анализ | Международный стандарт финансовой отчетности МСФО | менеджмент | метрология | механика | немецкий | неорганическая химия | ОБЖ | общая физика | операционные системы | оптимизация в сапр | органическая химия | педагогика | политология | правоведение | прочие дисциплины | психология (методы) | радиоэлектроника | религия | русский | сертификация | сопромат | социология | теория вероятностей | управление в технических системах | физкультура | философия | фотография | французский | школьная математика | экология | экономика | экономика (словарь) | язык Assembler | язык Basic, VB | язык Pascal | язык Си, Си++ |