Каноническая форма задачи линейного программирования. Переход к канонической форме злп
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
- если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
- если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
- если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
- если некоторая переменная x j
не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
x 3 = x 3 + - x 3 - , где x 3 + , x 3 - ≥ 0 .
Пример 1 . Приведение к канонической форме задачи линейного программирования:
min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.
Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".
2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.
Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:
2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x 1 = x 1 " - x 7 , где x 1 " ≥ 0, x 7 ≥ 0 .
Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:
L min = 2x 1 " + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1 " - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 " + x 2 - x 6 + 2x 7 = 3;
x 1 " ≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.
Условие оптимальности базисного плана канонической задачи ЛП. Симплекс-метод и его сходимость.
Симплексный метод является универсальным, так как позволяет решать практически любую задачу линейного программирования, записанную в каноническом виде.
Идея симплексногометода последовательного улучшения плана, заключается в том, что, начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по опорным решениям задачи к оптимальному.
Значение целевой функции при этом перемещении для задач на максимум не убывает.
Так как число опорных решений конечно, то через конечное число шагов получим оптимальное опорное решение.
Опорным решением называется базисное неотрицательное решение.
Алгоритм симплексного метода
1. Математическая модель задачи должна быть канонической. Если она неканоническая, то ее надо привести к каноническому виду.
2. Находим исходное опорное решение и проверяем его на оптимальность.
Для этого заполняем симплексную таблицу 1.
Все строки таблицы 1-го шагазаполняем по данным системы ограничений и целевой функции.
Возможны следующие случаи при решении задач на максимум:
1. Если все коэффициенты последней строки симплекс-таблицы Dj ³ 0, то найденное
решение оптимальное.
2 Если хотя бы один коэффициент Dj £ 0, но при соответствующей переменной нет ни одного положительного оценочного отношения, то решение задачи прекращаем , так как F(X) ® ¥ , т.е.целевая функция не ограничена в области допустимых решений.
Если хотя бы один коэффициент последней строки отрицателен, а при соответствующей переменной есть хотя бы одно положительное оценочное отношение, то нужно перейти к другому опорному решению.
4. Если отрицательных коэффициентов в последней строке несколько, то в столбец базисной переменной (БП) вводят ту переменную , которой соответствует наибольший по абсолютной величине отрицательный коэффициент.
5. Если хотя бы один коэффициент Dk < 0 ,то k - тый столбец принимаем за ведущий.
6. За ведущую строку принимаем ту, которой соответствует минимальное отношение свободных членов bi к положительным коэффициентам ведущего, k – того столбца.
7. Элемент, находящийся на пересечении ведущих строк и столбца, называется ведущим элементом.
Заполняем симплексную таблицу 2:
· заполняем базисный столбец нулями и единицей
· переписываем ведущую строку, разделив ее на ведущий элемент
· если ведущая строка имеет нули, то в следующую симплекс-таблицу можно перенести соответствующие столбцы
· остальные коэффициенты находим по правилу “прямоугольника”
Получаем новое опорное решение, которое проверяем на оптимальность:
Если все коэффициенты последней строки Dj ³ 0, то найденное решение максимальное.
Если нет, то заполняем симплексную таблицу 8-го шага и так далее.
Если целевая функция F(X) требует нахождения минимального значения , то критерием оптимальности задачи является неположительность коэффициентов Dj при всех j = 1,2,...n.
Сходимость симплекс-метода. Вырожденность в задачах ЛП. Важнейшим свойством любого вычислительного, алгоритма является сходимость, т. е. возможность получения в ходе его применения искомых результатов (с заданной точностью) за конечное число шагов (итераций).
Легко заметить, что проблемы со сходимостью симплекс-метода потенциально могут возникнуть на этапе выбора значения r (п. 2") в случае, когда одинаковые минимальные значения отношения
будут достигнуты для нескольких строк таблицы Т (q) одновременно. Тогда на следующей итерации столбец b(β(q+1)) будет содержать нулевые элементы.
Задачи МП
Общей ЗЛП называют <,=,>=}bi (i=1,n) (2) при условии xj>
Симметрической < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > Канонической смешенной .
min f(x) = -max(-f(x))
<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>
Геометрическая интерпретация целевой функции и ограничения ЗЛП. Геометрическая формулировка ЗЛП.
Пусть дана задача f=c1x1+c2x2-max (1)
a11x1+a12x2<=b1 }
am1x1+am2x2<=bm}
x1>=0, x2>=0 (3)
План задачи (х1,х2) – точка на плоскости. Каждое неравенство с-мы 2 предст. собой полуплоскость. Полуплоскость –выпуклое множество. Выпуклым наз-ся множество в которым точки отрезка соединяющие (х1 и х2) принадлежащие этому множеству то же принадлежат множеству. С-ма 2 представляет собой пересечение полуплоскостей. При пересечении могут получиться:
1)выпуклая многоугольная замкнутая область.
2) выпуклая открытая многоугольная область
3) единственная точка
4) пустое множество
5) луч и отрезок
Геометрическая интерпретация целевой функции: ф-ция 1 представляет собой семейство параллельных прямых, которые наз-ют линиями уровня(линиями постоянного значения целевой функции). Частные производные функции по х1 и х2 показывают скорость возрастания целевой функции вдоль координат осей. Вектор-градиент показывает направление найскорейшего возрастания целевой функции.Для задачи 1-3 вектор-градиент = (с1;с2) Выходит из точки (0,0) и направлен в точку с координатами (с1;с2). Вектор-градиент перпендикулярен линиям уровня. Пересечение полуплоскастей принято наз-ть областью допустимых рещений(ОДР) .
Основная теорема ЛП. Принципиальная схема решения ЗЛП, вытекающая из этой теоремы.
Если ЗЛП имеет решение, то целевая функция достигает экстремального значения хотя бы в одной из крайних точек многогранника плана. Если целевая функция достигает экстремального значения более чем в одной крайней точке то она достигает одно и то, являющейся их выпуклой линейной комбинацией.же значения в любой точке. При решении ЗЛП в ручную удобно использовать табличную запись.
| БП | СП -Xm+1 -Xm+2 -Xn | |
| х1 | b1o | b11 b12 b1n-m |
| х2 | b2o | b21 b22 b2n-m |
| хm | bm | bm1 bm2 bmn-m |
| f | boo | bo1 bo2 bon-m |
Алгоритм симплекс-метода.
1. привести модель задачи к канонической форме;
2. найти начальный опорный план;
3. записать задачу в симпл. таблицу;
5. перейти к новому опорному плану, к новой симп. таблице. Для того чтобы перейти к новому опорному плану достаточно заменить одну базисную переменную свободной. Переменную, включаемую в базис и соответствующей ей разрешающий столбец определяют по наибольшему по модулю отрицательному элементу f-строки. Переменную, исключающую из базиса и соответствующую ей разрешающую строку определяют по наименьшему симплексному отношению, т.е. отношению элементов единичного столбца к соответствующему элементу разрешающего столбца. Симплексное отношение – величина неотрицательная. На пересечении разрешающей строки и разрешающего столбца расположен разрешающий элемент, относительно которого выполняется симплексное преобразование по след. правилу: 1. элементы разрешающей строки делятся на разрешающий элемент; 2. элементы разрешающего столбца делятся на разрешающий элемент и меняют знак на противоположный; 3. остальные элементы таблицы перещитываются по правилу прямоугольника.:
bij bis bkj=(bkj*bis-bij*bks)/bi
Ая теорема двойственности.
если одна из двойственных задач имеет оптим план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограничена на множестве планов, то в двойственной задаче система ограничений несовместна.
Теорема о ранге матрицы ТЗ.
Ранг матрицы А трансп.задачи на единицу меньше числа уравнений: r(A)=m+n-1.
39. Алгоритм построения начального опорного плана ЗЛП.
Для нахождения начального опорного плана можно предложить следующий алгоритм:
1. записать задачу в форме жордановой таблицы так, чтобы все элементы столбца свободных членов были неотрицательными, т.е. выполнялось неравенство аio>=0 (i=1,m). Те уравнения с-мы, в которых свободные члены отрицательны, предварительно умножаются на -1.
| -x1 ….. -xn | ||
| 0= | a1o | a11 …. a1n |
| ….. | ….. | ……………………….. |
| 0= | amo | am1 ….. amn |
| f= | -c1 …. -cn |
Таблицу преобразовывать шагами жордановых исключений, замещая нули в левом столбце соответствующими х. При этом на каждом шаге разрешающим может быть выбран
любой столбец, содержащий хотя бы один положительный элемент. Разрешающая строка определяется по наименьшему из отношений свободных членов к соответствующем положительным элементам разрешающего столбца. Если в процессе исключений встретится 0-строка, все элементы которой- нули, а свободный член отличен от нуля, то с-ма ограничительных уравнений решений не имеет. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то с-ма ограничительных уравнений не имеет неотрицательных решений Если с-ма ограничительных уравнений совместна
, то через некоторое число шагов все нули в левом столбце будут замещены х и тем самым получен некоторый базис, а следовательно, и отвечающий ему опорный план.
40. Алгоритм построения оптимального опорного плана ЗЛП.
Начальный опорный план Хо исследуется на оптимальность.
Если в f-строке нет отрицательных элементов (не считая свободного члена), -план оптимален. Если в f- строке нет также и нулевых элементов, то оптимальный план единственный; если же среди элементов есть хотя бы один нулевой, то оптимальных планов бесконечное множество. Если в f-строке есть хотя бы один отрицательный элемент, а в соответствующем ему столбце нет положительных, то целевая функция не ограничена в допустимой области. Задача не разрешима. Если в f- строке есть хотя бы один отрицательный элемент, а в каждом столбце с таким элементом есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого столбец с отриц-ом элементом в f-строке берут за разрешающий ; опред-ют по минимальному симплексному отношению разрешающую строку и делают шаг жорданова исключения. Полученный опорный план вновь исследуется на оптимальность. Это повторяется до тех пор, пока не будет найден оптимальный опорный план либо установлена неразрешимость задачи.
Алгоритм метода Гомори.
1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2
2.Среди нецелых компонент следует выбрать ту, у которой дробная часть является наибольшей и по соответствующей этой строке симплексной таблицы сформулировать правильное отсечение по формуле
(n-m,s=1)∑ {αkm+1}Xm+1≥{βk}
3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом
4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2.
Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах.Метод Гомори имеет ограниченое применение. С его помощью целесообразно решать небольшие задачи, т.к. число интераций может быть очень большим.
Различные формы записи ЗЛП (общая, каноническая, симметрическая)
Задачи МП : определение оптимального плана, опред-е оптимального объема выпуска продукции, опред-е оптим-го сочитания посевов с/хоз-ых культур, формир-е оптим-го пакета активов, максимиз-щий прибыль банка и т.д.
Общей ЗЛП называют задачу максимизации (минимизации) линейной функции f=Σcj*xj-max(min) (1) при линейных ограничениях ∑aij *xj{=<,=,>=}bi (i=1,n) (2) при условии xj>=0(j=1,n1), xj-произвольное (j=n1+1,n)(3) где cj,aij, bi-постоянные числа.
Симметрической формой записи ЗЛП наз-ся задача максимизации функции (1) при линейных ограничениях в неравенствах со знаком < либо = и не отрицательных переменных и задача минимизации функции (1) при линейных ограничениях в неравенствах со знаком > либо = и неотрицательных переменных. Канонической формой записи ЗЛП наз-ся задача максимальной функции (1) при линейных ограничениях равенствах и неотрицательных переменных. Любая другая форма называется смешенной .
min f(x) = -max(-f(x))
Преобразование нерав-ва в уравнение и наоборот осущ-ся на основе Леммы: всякому решению х1…хn нерав-ва a1x1+…+anxn<=b (5)соответствует вполне определенное решение х1…хn, xn+1 уравненияa1x1+…+anxn+xn+1=b (6) при условии что хn+1>=0(7) и наоборот. Всякому решению x1…xn,xn+1 уравнения 6 и неравенства 7 соответствует решение x1…xn неравенства 5.
Чтобы от зад сим формы перейти к зад канонич вида, необходимо ввести балансовые (выравнивающие) переменные. Это основано на теореме о неравенстве: любое нерав-во можно представить в виде ур-я или простейшего нерав-ва.
канонической форме , если требуется максимизировать целевую функцию, все ограничения системы – уравнения и на все переменные наложено условие неотрицательности.
Задача линейного программирования задана в симметричной форме , если требуется максимизировать целевую функцию, все ограничения системы – неравенства «» (или минимизировать целевую функцию, все ограничения системы – неравенства «») и на все переменные наложено условие неотрицательности.
Набор чисел называется допустимым решением (планом) , если он удовлетворяет системе ограничений ЗЛП.
Множество всех допустимых решений называется областью допустимых решений (ОДР).
Допустимое решение , для которого достигается максимальное (минимальное) значение функции, называется оптимальным планом ЗЛП .
Термины «план» и «оптимальный план» возникли из экономических приложений.
Все три формы записи ЗЛП являются эквивалентными в том смысле, что имеются алгоритмы перехода от одной формы к другой. Таким образом, если имеется способ решения задачи в одной из форм, то всегда можно определить оптимальный план задачи, заданной в любой другой форме . Задача в симметричной форме решается графическим методом, а в канонической форме – симплекс–методом.
Рассмотрим алгоритмы перехода от одной формы к другой.
Симметричная каноническая. Переход осуществляется путем добавления в левую часть каждого неравенства дополнительной неотрицательной переменной. Если неравенство было «≤», то балансовая переменная добавляется в левую часть неравенства со знаком «+». Если неравенство было «», то балансовая переменная добавляется в левую часть неравенства со знаком «–». Вводимые новые переменные называются балансовыми . Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) и используют, что min Z = –max (–Z).
Каноническая симметричная. Для осуществления такого перехода находится общее решение системы уравнений – ограничений, целевая функция выражается через свободные переменные. Далее, воспользовавшись неотрицательностью базисных переменных, можно исключить их из задачи. Симметричная форма задачи будет содержать неравенства, связывающие только свободные переменные, и целевую функцию, зависящую только от свободных переменных. Значения базисных переменных находятся из общего решения исходной системы уравнений.
Общая каноническая. Каждая переменная, на которую не было наложено условие неотрицательности, представляется в виде разности двух новых неотрицательных переменных. Неравенства преобразуются в уравнения путем введения в левую часть каждого неравенства балансовой переменной таким же образом, как это было описано при переходе от симметричной к канонической форме. Задачу минимизации функции Z заменяют на задачу максимизации функции (–Z) таким же образом, как это было описано при переходе от симметричной к канонической форме..
Графический метод решения задачи линейного программирования
Множество точек называется выпуклым , если для любых двух точек множества оно содержит отрезок, их соединяющий.
Пример 1
Следующие множества точек на плоскости являются выпуклыми:
Следующие множества точек на плоскости не являются выпуклыми:
Теорема 1 Пересечение любого количества выпуклых множеств является выпуклым множеством.
Теорема 2 Пусть имеются две произвольные точки и в пространстве R n . Тогда для любой точки отрезка [PQ ] должно выполняться: .где .
Гиперплоскостью в пространстве R n называется множество точек, удовлетворяющее уравнению . Заметим, что в двумерном случае гиперплоскостью является прямая.
Полупространством называется множество точек, удовлетворяющее одному из неравенств или . Гиперплоскость делит точки пространства на два полупространства. В двумерном случае гиперплоскостью является полуплоскость.
Теорема 3 Полупространство является выпуклым множеством.
Следствие Пересечение любого количества полупространств является выпуклым множеством.
Многогранником называется пересечение одного или более полупространств. Многогранник в двумерном случае называется многоугольником.
Пример 2
Следующие множества являются многоугольниками.
Ограниченное множество
Неограниченное множество
Единственная точка
Пустое множество
Точка выпуклого множества называется угловой
, если она не лежит внутри никакого отрезка, соединяющего две другие точки из множества.
Пример 3
Угловыми точками треугольника являются его вершины (их три). Угловыми точками круга являются точки окружности, которая его ограничивает (их бесконечное число).
Угловая точка многогранника называется его вершиной .
Рассмотрим ЗЛП, заданную в симметричной форме.
Теорема 4 Оптимальный план ЗЛП соответствует вершине многогранника решений, определяемого ее системой ограничений.
В исходной постановке ЗЛП могут допускать различные формы записи. Так, в одних задачах требуется максимизировать целевую функцию, в других - минимизировать; некоторые линейные ограничения могут иметь вид равенств, другие - неравенств и т.д.
Для единообразия записи ЗЛП вводится так называемая каноническая форма записи.
Говорят, что ЗЛП записана в канонической форме, если она имеет следующий вид:
Отметим следующие особенности канонического вида:
1) требуется минимизировать целевую функцию;
2) все линейные ограничения, кроме требований неотрицательности переменных, имеют вид равенств;
на все переменные наложены требования неотрицательности.
Покажем, что любую ЗЛП можно привести к каноническому виду.
1) Если в ЗЛП требуется максимизировать целевую функцию f, то положим g = - f и потребуем минимизировать функцию g. Получится новая ЗЛП, которая эквивалентна исходной в том смысле, что каждое оптимальное решение исходной задачи будет оптимальным решением новой задачи и наоборот.
2) Предположим, что в ЗЛП есть линейное ограничение вида
Заменим такое ограничение следующими двумя ограничениями:
где z - новая переменная, которая в целевую функцию вводится с коэффициентом 0 (иначе говоря, переменная z не вводится в целевую функцию). Значение переменной z можно не учитывать после решения новой задачи.
Аналогично, ограничение вида заменяется двумя ограничениями:
3)
Предположим, что в ЗЛП не ко всем
переменным предъявлено требование
неотрицательности. Тогда каждую,
переменную
,
на которую не наложено требование
неотрицательности, представим в виде
разности двух неотрицательных переменных:
Каждое
вхождение переменной
в
целевую функцию или ограничения заменим
разностью
.
Решив новую задачу с помощью (2.6), вернемся
к прежним переменным.
Указанными приемами любая ЗЛП приводится к каноническому виду.
Пример. Привести к каноническому виду
Проделаем описанные действия.
Теперь получим ЗЛП в каноническом виде:
2.7. Понятие опорного плана злп.
Пусть ВЛП задана в каноническом виде (2.3 - 2.5). Предположим, что система уравнений (2.4) приведена к жордановой форме с неотрицательными правыми частями:
(2.6)
где
.
Приравняв к нулю свободные переменные, получим базисное решение системы (2.4)
В
силу условия
набор
значений переменных (2.7) удовлетворяет
и ограничениям (2.5). Поэтому (2.6) являетсядопустимым
решением ЗЛП
.
Допустимое
решение (2.7) называется базисным
допустимым
решением или опорным
планом ЗЛП.
При этом говорят, что переменные
образуют
допустимый базис.
Оказывается, что если ОДР изобразить геометрически, то каждый опорный план ЗЛП соответствует вершине многогранника. Поэтому справедлива следующая теорема.
Если ЗЛП разрешима, то существует оптимальный опорный план.
3. Симплексный метод решения злп
3.1. Общая характеристика и основные этапы симплекс – метода
Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.
Симплекс-методом можно решить любую ЗЛП или обнаружить ее неразрешимость. Многие специальные классы ЗЛП можно решить другими, более эффективными для этих классов методами. Однако преимущество симплекс-метода - его универсальность. Почти для всех ЭВМ разработаны стандартные программы для решения ЗЛП симплекс - методом.
Опишем общую идею симплекс-метода.
Считаем, что ЗЛП записана в каноническом виде и целевую функцию нужно минимизировать. Как мы уже знаем, оптимальный план следует искать среди опорных планов ЗЛП. Симплекс-метод не перебирает все опорные планы (что было бы часто невозможно из-за их огромного количества), а, начиная с некоторого исходного опорного плана, он последовательно переходит к другим опорным планам с уменьшением целевой функции. Симплекс-метод прекращает свою работу тогда, когда либо будет найден оптимальный опорный план, либо установлена неразрешимость задачи.
При решении ЗЛП симплекс-методом можно выделить следующие этапы:
1) приведение ЗЛП к каноническому виду;
2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;
3) исследование опорного плана на оптимальность;
4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;
5) переход к новому, "лучшему" опорному плану.
Cтраница 1
Каноническая форма задачи характеризуется следующими тремя признаками: 1) однородная система ограничений в виде системы уравнений; 2) однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче, и 3) максимизация, линейной функции. В данной задаче нарушены все эти три признака.
Каноническая форма задачи характеризуется следующими тремя признаками: 1) однородная система ограничений в виде системы уравнений; 2) однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче, и 3) максимизация линейной функции. В данной задаче нарушены все эти три признака.
Каноническая форма задачи линейного программирования удобна тем, что легко находится начальная вершина допустимой области.
Рассмотрим каноническую форму задачи линейного программирования и метод исключения Жордана - Гаусса.
Часто оказывается удобной каноническая форма задачи линейного программирования.
При преобразовании системы ограничений к канонической форме задачи линейного программирования неравенства (12) и (13) должны быть заменены равенствами. Для этого вводят дополнительные неотрицательные переменные.
Доказать, что попарно коммутирующие вещественные матрицы одновременно приводятся к канонической форме задачи 1128 преобразованием подобия посредством ортогональной матрицы.
По существу (4) - (5) можно рассматривать как каноническую форму задачи нелинейного программирования, поскольку методы, изложенные в гл. Обычно в задачах нелинейного программирования не выдвигается требование целочисленности переменных.
| Виды ограничений и методы их преобразования. |
Каноническая форма задачи характеризуется однородностью системы ограничений в виде системы уравнений; максимизацией целевой функции; условием неотрицательности всех переменных, участвующих в задаче.
Никаких дополнительных особенностей каноническая форма задач в рассматриваемую вычислительную схему не добавляет.
Рассмотрим сначала вторую каноническую форму задачи на минимум.
Алгоритм симплекс-мете да гложно разбить на два этапа. На первом этапе исключением переменных находят базисное решение. Если оно найдено, то мы имеем каноническую форму задачи для перехода ко второму этапу. На втором этапе проверяют, есть ли ограниченный оптимум. Если он существует то определяются допус - тимые базисные решанпя ив которых выбирается оптимальное.
Если решается задача в канонической форме, то используется лишь часть введенных во втором параграфе операций. Так, для канонической задачи на минимум реализуется только случай пункта 3.4.1, и нужны лишь операции циклической перестановки столбцов, прогонки столбца через зону вертикального окаймления, исправления структурных нарушений и часть операции усечения. Симметрично, при решении канонической задачи на максимум реализуется только случай пункта 3.4.2, и нужны операции циклической перестановки строк, прогонки строки через зону горизонтального окаймления, исправления структурных нарушений и другая часть операции усечения. В остальном никакой дополнительной специфики каноническая форма задачи не добавляет.
В первом параграфе введения было показано, как общую задачу линейного программирования можно свести к одной из канонических форм. Для канонически (же задач описание метода последовательного улучшения формально упрощается, так как отпадает необходимость рассматривать два варианта нарушения условий оптимальности и два варианта выхода в следующую вершину. Однако при этом увеличиваются размеры базисной матрицы А [ /, J ], которые в основном и определяют трудоемкость одного шата. Тем не менее, во многих случаях применение метода к каноническим формам задачи оказывается предпочтительным, и в этом параграфе мы остановимся на вариантах метода, получающихся для частных задач линейного программирования.
Страницы: 1
Статьи по теме
