Математическое программирование

Математическое программирование

Симплексной форме ЗЛП соответствует симплекс - матрица : 1 0 ... 0 ... 0 a 1,r+1 ... a 1s ... a 1n b 1 0 1 ... 0 ... 0 a 2,r+1 ... a 2s ... a 2n b 2 ................................................................. 0 0 ... 1 ... 0 a i,r+1 ... a is ... a in b i ................................................................. 0 0 ... 0 ... 1 a r,r+1 ... a rs ... a rn b r 0 0 ... 0 ... 0 c r+1 ... c s ... c n b 0 Заметим, что каждому базису (системе базисных неизвестных ) соответствует своя симплекс - матрица , базисное решение х = ( b 1 ,b 2 , ... ,b r , 0, ... ,0) и базисное значение целевой функции f(b 1 ,b 2 , ... ,b r , 0, ... ,0) = b 0 ( см.

Последний столбец !). Критерий оптимальности плана . Если в последней (целевой) строке симплекс-матрицы все элементы неположительны, без учета последнего b 0 , то соответствующий этой матрице план оптимален, т.е. с j 0 (j = r+1, n) => min f (b 1 , ... ,b 2 ,0, ... ,0) = b 0 . Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец ( S -й), в котором последний элемент с s > 0, a все остальные элементы неположительны, то ЗЛП не имеет оптимального плана, т.е. с s > 0 , a is 0 ( i= 1,r ) = > min f = - . Если в симплекс-матрице не выполняются оба критерия, то в поисках оптимума надо переходить к следующей матрице с помощью некоторого элемента a is > 0 и следующих преобразований (симплексных): 1) все элементы i -й строки делим на элемент a + is ; 2) все элементы S -го столбца, кроме a is =1, заменяем нулями ; 3) все остальные элементы матрицы преобразуем по правилу прямоугольника, что схематично показано на фрагменте матрицы и дано в формулах: a kl ` = a kb a is - a il a ks = a kl - a il a ks ; a is a is b k ` = b k a is - b i a ks ; c l ` = c l a is - c s a il a is a is Определение . Элемент a is + называется разрешающим, если преобразование матрицы с его помощью обеспечивает уменьшение (невозрастание) значения, целевой функции ; строка и столбец, на пересечении которых находится разрешающий элемент, также называются разрешающими.

Критерий выбора разрешающего элемента. Если элемент a is + удовлетворяет условию b i = min b k a is 0 a ks 0 + где s 0 - номер выбранного разрешающего столбца, то он является разрешающим. 4. Алгоритм симплекс-метода (по минимизации). 1) систему ограничений и целевую функцию ЗЛП приводим к симплексной форме ; 2) составим симплекс-матрицу из коэффициентов системы и целевой функции в симплексной форме ; 3) проверка матрицы на выполнение критерия оптимальности ; если он выполняется, то решение закончено ; 4) при невыполнении критерия оптимальности проверяем выполнение критерия отсутствия оптимальности ; в случае выполнения последнего решение закончено - нет оптимального плана ; 5) в случае невыполнения обоих критериев находим разрешающий элемент для перехода к следующей матрице, для чего : а) выбираем разрешающий столбец по наибольшему из положи тельных элементов целевой строки ; б) выбираем разрешающую строку по критерию выбора разрешающего элемента ; на их пересечении находится разрешающий элемент ; 6) c помощью разрешающего элемента и симплекс-преобразований переходим к следующей матрице ; 7) вновь полученную симплекс-матрицу проверяем описанным выше способом (см. п. 3) Через конечное число шагов, как правило получаем оптимальный план ЗЛП или его отсутствие Замечания. 1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения при симплекс-преобразованиях. 2) преобразования - вычисления удобно начинать с целевой строки ; если при этом окажется, что выполняется критерий оптимальности, то можно ограничиться вычислением элементов последнего столбца. 3) при переходе от одной матрицы к другой свободные члены уравнений остаются неотрицательными ; появление отрицатель ного члена сигнализирует о допущенной ошибке в предыдущих вычислениях. 4) правильность полученного ответа - оптимального плана - проверяется путем подстановки значений базисных неизвестных в целевую функцию ; ответы должны совпасть. 5. Геометрическая интерпретация ЗЛП и графический метод решения (при двух неизвестных) Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы.

Целевая функция f = c 1 x 1 + c 2 x 2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с 1 ,с 2 ). Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают. На этих утверждениях основан графический метод решения ЗЛП. 6. Алгоритм графического метода решения ЗЛП. 1) В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений ; 2) найти полуплоскости решения каждого неравенства системы (обозначить стрелками) ; 3) найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей ; 4) построить вектор n (с 1 ,с 2 ) по коэффициентам целевой функции f = c 1 x 1 + c 2 x 2 ; 5) в семействе параллельных прямых целевой функции выделить одну, например, через начало координат ; 6) перемещать прямую целевой функции параллельно самой себе по области решения, достигая max f при движении вектора n и min f при движении в противоположном направлении. 7) найти координаты точек max и min по чертежу и вычислить значения функции в этих точках (ответы). 7. Постановка транспортной задачи.

Приведем экономическую формулировку транспортной задачи по критерию стоимости: Однородный груз, имеющийся в m пунктах отправления (производства) А 1 , А 2 , ..., А m соответственно в количествах а 1 , а 2 , ..., а m единиц, требуется доставить в каждый из n пунктов назначения (потребления) В 1 , В 2 , ..., В n соответственно в количествах b 1 , b 2 , ..., b n единиц.

Стоимость перевозки (тариф) единицы продукта из A i в B j известна для всех маршрутов A i B j и равна C ij (i=1,m; j=1,n) . Требуется составить такой план перевозок, при котором весь груз из пунктов отправления вывозиться и запросы всех пунктов потребления удовлетворяются (закрытая модель), а суммарные транспортные расходы минимальны.

Условия задачи удобно располагать в таблицу, вписывая в клетки количество перевозимого груза из A i в B j груза X ij > 0 , а в маленькие клетки - соответствующие тарифы C ij : 8. Математическая модель транспортной задачи. Из предыдущей таблицы легко усматривается и составляется математическая модель транспортной задачи для закрытой модели Число r = m + n - 1 , равное рангу системы (1), называется рангом транспортной задачи. Если число заполненных клеток ( X ij ¹ 0) в таблице равно r , то план называется невырожденным, а если это число меньше r , то план вырожденный - в этом случае в некоторые клетки вписывается столько нулей (условно заполненные клетки), чтобы общее число заполненных клеток было равно r . Случай открытой модели а i ¹ b j легко сводится к закрытой модели путем введения фиктивного потребителя B n+1 c потребностью b n+1 = a i - b j , либо - фиктивного поставщика А m+1 c запасом a m+1 = b j - a i ; при этом тарифы фиктивных участников принимаются равными 0. 9. Способы составления 1-таблицы (опорного плана). I. Способ северо-западного угла (диагональный). Сущность способа заключается в том, что на каждом шаге заполняется левая верхняя клетка (северо-западная) оставшейся части таблицы, причем максимально возможным числом: либо полностью вывозиться груз из А i , либо полностью удовлетворяется потребность B j . Процедура продолжается до тех пор, пока на каком-то шаге не исчерпаются запасы a i и не удовлетворяются потребности b j . В заключение проверяют, что найденные компоненты плана X ij удовлетворяют горизонтальным и вертикальным уравнениям и что выполняется условие невырожденности плана. II. Способ наименьшего тарифа.

Сущность способа в том, что на каждом шаге заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф; в случае наличия нескольких таких равных тарифов заполняется любая из них. В остальном действуют аналогично предыдущему способу. 10. Метод потенциалов решения транспортной задачи.

Определение: потенциалами решения называются числа a i ® A i , b j ® B j , удовлетворяющие условию a i + b j = C ij (*) для всех заполненных клеток ( i,j) . Соотношения (*) определяют систему из m+n-1 линейных уравнений с m+n неизвестными, имеющую бесчисленное множество решений; для ее определенности одному неизвестному придают любое число (обычно a 1 =0), тогда все остальные неизвестные определяются однозначно.

Критерий оптимальности. Если известны потенциалы решения X 0 транспортной задачи и для всех незаполненных клеток выполняются условия a i + b j C i j , то X 0 является оптимальным планом транспортной задачи. Если план не оптимален, то необходимо перейти к следующему плану (таблице) так, чтобы транспортные расходы не увеличились.