Алгоритм графического метода решения задач

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

Шаг 1. Построение допустимого множества.

Заметим, что каждое ограничение задачи определяет некоторую полуплоскость (в случае неравенства) или прямую (в случае равенства). Допустимым множеством является пересечение этих полуплоскостей и прямых. Таким образом, для построения допустимого множества нужно:

а) для каждого ограничения нарисовать прямую, соответствующую равенству ;

б) если ограничение задается неравенством вида  или , то определить полуплоскость, задаваемую данным неравенством. Это легко сделать, если подставить в него координаты точки, не расположенной на соответствующей прямой. Если неравенство оказывается справедливым, то выбрать полуплоскость, содержащую данную точку, в противном случае - выбрать противоположную полуплоскость.

в) найти пересечение полученных полуплоскостей и прямых.

Шаг 2. Решение задачи путем анализа допустимого множества и поведения целевой функции на этом множестве. 

а) Пусть допустимое множество оказалось пустым. Делается вывод: задача решений не имеет, поскольку нет ни одной допустимой точки.

б) Пусть допустимое множество оказалось не пустым. Выбрать два произвольных числа  и , . Нарисовать линии уровня целевой функции, соответствующие выбранным константам, т.е. прямые вида   и  ( это параллельные прямые, все точки которых обеспечивают значения целевой функции, равные соответственно  и ). Зафиксировать направление увеличения значений целевой функции от прямой с правой частью, равной , к прямой с правой частью, равной . Передвигать прямую    параллельно самой себе по допустимому множеству в обозначенном направлении (в противоположном направлении) до получения максимального значения   (минимального значения ), при котором прямая   пересекает допустимое множество. Зафиксировать на графике точки допустимого множества, обеспечивающие максимальное (минимальное) значение целевой функции или убедиться, что таких точек нет. Если допустимое множество ограничено (является многоугольником), то возможны два различных ответа: решение единственно или решений бесчисленное множество. При единственном решении на графике зафиксирована единственная точка (вершина многоугольника), являющаяся пересечением некоторых прямых. Необходимо выписать соответствующие уравнения прямых и, решив систему полученных уравнений, найти точку - решение задачи. В случае бесчисленного множества решений получен отрезок прямой, все точки которого обеспечивают максимальное значение целевой функции. Среди этих точек есть вершины многоугольника. Координаты вершин отыскиваются так, как указано в предыдущем случае. Если допустимое множество не ограничено, то возможны те же две ситуации, что и в случае ограниченного множества, и, кроме того, возможен случай отсутствия решений из-за неограниченности значений целевой функции на допустимом множестве.

 

Из анализа графического метода решения можно сделать выводы, которые являются справедливыми и для задач из Rⁿ.

1. Допустимое множество задачи линейного программирования, если оно не пусто, является многогранным ограниченным или неограниченным выпуклым множеством.

2. Если в задаче есть решение (оптимальная точка), то среди решений обязательно есть вершины допустимого множества. Часть оптимальных точек можно искать, перебирая только вершины допустимого множества.

Проиллюстрируем рассмотренный графический метод на примерах.

     Пример 1. Решить графически следующую задачу линейного программирования

(1)

  (2)

     (3)

.

Рис.1

     Решение. Строим область допустимых решений в соответствии с шагом 1 описанного выше алгоритма. В результате получим выпуклый многоугольник (рис 1.)

Следуя пункту 2 рассмотренного алгоритма, строим линии уровня целевой функции  и фиксируем направление увеличения значения целевой функции при переходе от одной линии уровня к другой. Перемещая прямую  параллельно самой себе в найденном направлении, пока она будет сохранять общие точки с допустимой областью, найдем, что в крайнем возможном положении линия уровня пройдет через точку . Этому положению линии уровня и соответствует . Для нахождения координат точки  необходимо решить систему уравнений:

.

     В результате получим искомое оптимальное решение   с значением целевой функции .

     Пример 2. Решить графически следующую задачу:

(1)

(2)

     (3)

.

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

	Рис. 2.

 

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

Пример 3. Решить задачу

(1)

    (2)

.

Решение. Допустимая область в данной задаче имеет вид

 

                                       Рис 3.       

Из рисунка видно, что допустимое множество неограниченно. Линии уровня целевой функции параллельны прямой , соответствующей первому ограничению. Перемещая линии уровня в направлении возрастания целевой функции, получаем, что линия уровня с максимально возможным значением целевой функции совпадает с прямой . Таким образом, целевая функция достигает своего максимального значения  во всех точках луча, выходящего из точки . Задача имеет бесчисленное множество решений. Для того чтобы выписать решение в общем виде, возьмем на луче еще одну точку . Уравнение луча записывается следующим образом: . Таким образом, любое решение данной задачи записывается в виде .  

     Пример 4. Решить графически задачу

(1)

(2)

   (3)

Решение. Допустимое множество данной задачи пусто. Это видно из следующего рисунка

                                              

Рис 4.

Поэтому данная задача неразрешима.

     Пример 5. Решить графически задачу

  (1)

 (2)

Решение. Допустимым множеством в данной задаче является выпуклый многогранник (рис. 5).

Рис.5

Линии уровня целевой функции параллельны прямой, соответствующей ограничению (2). Проводя рассуждения, аналогичные рассуждениям в примере 3, получим, что целевая функция достигает своего максимального значения  во всех точках отрезка, соединяющего точки  и . Задача имеет бесчисленное множество решений, которое записывается следующим образом 

.

Таким образом, любое решение данной задачи имеет вид .  

 

Задачи для самостоятельного решения

 

1.Решить графически:

1)                         2)

                                 

                         

                               

.                            

3)                         4)

                                

                      

                        

 5)                         6)

                                                                    

                                           

                                                        

                                .

 

2. Определить промежутки значений , при которых решение будет совпадать с одной и той же вершиной области допустимых решений. В каких промежутках задача не имеет решений? При каких значениях  будет бесчисленное множество решений?

1)                              2)  

                                   

                                    

                                              

                                    

 

3)                                 3)

                                      

                                          

                                        

                                        .

3. Привести пример графической интерпретации и составить на основании полученного чертежа математическую запись задачи, обладающей следующими свойствами:

1) имеется единственное оптимальное решение для задачи на минимум и для задачи на максимум;

2) максимальное значение целевая функция достигает в бесчисленном множестве точек, а минимальное значение в единственной точке;

3) на минимум задача неразрешима из-за неограниченности целевой функции, а максимальное значение достигается в единственной точке;

4) на максимум и на минимум задача неразрешима из-за неограниченности целевой функции;

5) минимальное значение целевой функции достигается в бесчисленном множестве точек, из которых только одна является вершиной.

 

1. Различные формы записи задачи линейного программирования 2. Алгоритм перебора базисных решений систем линейных уравнений   3. Алгоритм базового симплексного метода   4. Метод искусственного базиса и М-метод решения произвольной задачи линейного программирования

Глава 2

Симплексный метод

Различные формы записи задачи линейного программирования

 

В главе 1 приведена общая постановка задачи линейного программирования (ЗЛП). Часто для удобства исследования и при построении метода решения фиксируется та или иная запись задачи. Так, часто используется задача в следующей форме:

.

 

Такая форма записи ЗЛП называется стандартной или симметричной формой задачи линейного программирования. Кроме того, выделяют каноническую форму записи ЗЛП:

.

 

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

Определение 1. Две оптимизационные задачи называются эквивалентными, если они имеют одно и то же множество оптимальных точек.

 Однако так как при переходе от одного вида задачи к другому возможно изменение размерности задачи (увеличение числа переменных, увеличение числа ограничений), то следует в каждом конкретном случае аккуратно формулировать, как понимается эквивалентность данных задач. Сформулируем правила, позволяющие осуществить эквивалентные перезаписи задач.

1. Обеспечить нужное направление оптимизации целевой функции возможно с помощью умножения исходной целевой функции на -1.

2. Любое неравенство можно умножить на -1 и перейти к неравенству другого знака.

3. Ограничение-равенство  можно записать в виде системы двух неравенств

.

4. От ограничений неравенств можно перейти к равенствам, добавляя или отнимая неотрицательные новые переменные, которые в дальнейшем будут называться дополнительными переменными. Так, неравенство  эквивалентно системе . Аналогично неравенство  эквивалентно системе .

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

В качестве примера сформулируем факт эквивалентности двух следующих задач линейного программирования:

                                              

(1)                          (2)

                                         

     Утверждение 1. Если  является решением задачи (1), то найдется такое , что  является решением задачи (2). С другой стороны, если  является решением задачи (2), то  является решением задачи (1).

         

В связи с тем, что основной метод решения ЗЛП - симплексный метод предназначен для решения задач в канонической форме, мы проиллюстрируем работу описанных выше правил на примере приведения задачи к канонической форме.

     Пример 1. Пусть исходная задача задана в виде

при ограничениях

  

      

           .

Привести данную задачу к канонической форме.

Решение.

1. Умножим целевую функцию на -1. В результате получим

.

2. Из левой части первого неравенства вычтем неотрицательную переменную  и перейдем к ограничениям

.

3. К левой части второго неравенства добавим неотрицательную переменную и перейдем к ограничениям

.

 

4. Умножим обе части третьего равенства на -1

.

5. Осуществим замену переменных

                                                         

В результате задача принимает канонический вид

 

.

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

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

 

Задачи для самостоятельного решения

1. Привести к канонической форме следующие задачи линейного программирования:

     а)                   б)

                                  

                                

                               

          ;           ;

     в)

          

           

                    ;

     г)

       

             

               ;

2. Привести к симметричной форме следующие задачи линейного программирования:

     а)

         

          

     

            ;

б)

 

 

 

   Алгоритм перебора базисных решений

 систем линейных уравнений

Рассмотрим ЗЛП, заданную в канонической форме. В матричном виде данная задача может быть переписана следующим образом:

                                           (1)

                                                                                                 (2)

                                                      ,                                                      (3)

где

Очевидно, что решения задачи ЛП (1) - (3) находятся среди решений системы линейных уравнений Ax = b. Рассмотрим способ перебора решений данной системы для случая, когда ранг матрицы r(A) = m. Из курса линейной алгебры известно, что система (2) с помощью преобразований Жордана - Гаусса может быть приведена к виду

                                               ,                                             (4)

где E - единичная матрица размера m× m, матрица имеет размеры m×(n-m) и элементы , полученные в результате преобразований Жордана-Гаусса,  - вектор размера m, полученный из вектора   вследствие преобразований. Система уравнений (4) может быть переписана в координатной форме следующим образом:

                      (5)

где I - множество индексов зависимых переменных, J - множество индексов свободных переменных, . Формула (5) представляет собой формулу общего решения системы (2). Напомним, что любое частное решение системы может быть получено из формулы общего решения путем фиксирования любых значений свободных переменных с последующим вычислением по формуле (5) значений зависимых переменных. В дальнейшем нас будут интересовать частные решения вида , т.е. векторы, свободные переменные которых положены равными 0. Такие векторы называются базисными решениями системы линейных уравнений (2). Максимальное количество базисных решений не превосходит величины . Перебрать все базисные решения системы линейных уравнений можно, организовав перебор формул общего решения. Очевидно, что это можно осуществить с использованием метода Жордана-Гаусса, например, по следующей схеме.

Алгоритм перебора

 

Шаг 1. Получить методом Жордана-Гаусса произвольную формулу общего решения вида (5). Положить N=1.

Шаг 2. Запомнить множество . Положить

Шаг 3. Выбрать номер k из множества J. Заменить J на J\{k}.

Шаг 4. Выбрать  такой, что . Если таких номеров l в I нет, то перейти к шагу 7.

Шаг 5. Если множество  уже рассмотрено, то заменить I на и перейти к шагу 6, иначе перейти к шагу 8.

Шаг 6. Если I= Ø то положить  и перейти к шагу 7, иначе перейти к шагу 4.

Шаг 7. Если J=Ø, то останов - получены все возможные формулы общего решения, иначе перейти к шагу 3.

Шаг 8. Осуществить преобразования Жордана -Гаусса с направляющим элементом  до получения в k-м столбце единичного вектора. Заменить N на N+1. Положить . Перейти к шагу 2.

Пример 1. Найти базисные решения системы уравнений.

Решение. Здесь I={1,3},J={2}. Оформить процедуру решения удобно в виде следующей таблицы, где через A_j обозначены векторы-столбцы матрицы (столбцы коэффициентов при переменной x_j).

 

I	B	A 1	A2	A3	alk	коммент.
1 3	2 4	1 0	2 -1	0 1	k=2 a12 =2	J^1={2}
2 3	1 5	1/2 1/2	1 0	0 1	k=1 a21 -нет * a31 =1/2	J^2={1}
2 1	-4 10	0 1	1 0	-1 2	a23 -нет * a13 -нет*	ОСТАНОВ

 

* (выбор этого элемента порождает "старое" множество I)

На данных трех итерациях получены базисные решения системы соответственно x¹=(2,0,4), x²=(0,1,5), x³=(10,-4,0).

Как видно из рассмотренного примера, не все полученные в результате перебора базисные решения системы линейных уравнений являются допустимыми точками в соответствующей задаче линейного программирования (1) - (3), так как не удовлетворяют условию неотрицательности (3). Процедуру перебора можно модифицировать таким образом, чтобы перебирать только неотрицательные базисные решения. Изменения необходимо внести в 1, 3 и 4 пункты сформулированного алгоритма, которые приобретают следующий вид.

Шаг 1а. Получить произвольное неотрицательное базисное решение. Положить N=1.

3а. Выбрать  такое, что . Заменить J на J\{k}.

Шаг 4а. Выбрать  такое, что . Если таких номеров l в I нет, то перейти к шагу 7.

Пример 2. Найти неотрицательные базисные решения системы уравнений.

Решение.

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

Положим N=1. Тогда I ¹={3,4},J ¹={1,2}..

Как и в примере 1, оформим решение в виде в таблицы. Добавим столбец Θ, в который будем помещать отношение b_i / a_ik для a_ik >0

 

I	b	A 1	A2	A3	A4	Θ	alk	коммент.
3 4	11/4 3/4	7/2 -1/2	4 -1	1 0	0 1	11/16 -	k=2,l=3 a32 =4	J^1={1,2}
2 4	11/16 23/16	7/8 3/8	1 0	1/4 1/4	0 1	11/14 23/6	k=1,l=2 a21 =7/8	J^2={1,3}
1 4	11/14 8/7	1 0	8/7 -3/7	2/7 1/7	0 1		k=2 a12 -нет k=3 a13 -нет	ОСТАНОВ

 

На данных итерациях получены базисные решения системы соответственно .

 

Задачи для самостоятельного решения

1. Найти все базисные решения следующих систем уравнений:

     а)   

          ;

     б)

           ;

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

	а	в	с		а	в	с		а	в	с		а	в	с
1	3	6	-2	6	2	4	-4	11	3	2	0	16	6	5	-3
2	2	3	0	7	3	5	-2	12	4	5	-3	17	2	6	-1
3	5	4	-1	8	3	4	-1	13	5	2	-1	18	4	2	-4
4	6	2	-3	9	2	5	0	14	4	3	-4	19	5	6	0
5	5	3	-4	10	6	3	-3	15	6	4	-2	20	4	6	-2

 Симплексный метод

     Определение 1. Допустимая точка ЗЛП   называется базисной, если векторы-столбцы матрицы A: , соответствующие ее ненулевым координатам, являются линейно независимыми.

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

Пример 1. Пусть условия (2) некоторой задачи линейного программирования имеют вид

Проверить, является ли точка x=(1,0,0,1)^Т базисной.

Решение. Так как координаты точки неотрицательны и удовлетворяют заданной системе уравнений, то она по определению является допустимой. Введем в рассмотрение векторы - столбцы матрицы ограничений: . Тогда система уравнений после подстановки в нее координат проверяемой точки примет вид:

В соответствии с определением базисной точки, векторы A ₁ и A₄ следует проверить на линейную независимость. Из курса линейной алгебры известно, что векторы являются линейно независимыми, если ранг матрицы, составленной из этих векторов, равен их количеству. 

Так как определитель матрицы , то ее ранг равен 2, и векторы линейно независимы. Следовательно, точка (1,0,0,1)^Т является базисной.

 

Из определения следует, что число положительных координат базисной точки не может быть более чем m.

Определение 2. Если базисная точка содержит ровно m положительных координат, то она называется невырожденной, в противном случае - вырожденной. Задача называется невырожденной, если допустимое множество не имеет вырожденных базисных точек.

Как следует из соответствующих определений, базисные точки допустимого множества ЗЛП (1) - (3) совпадают с неотрицательными базисными решениями системы линейных уравнений (2). Таким образом, алгоритм перебора неотрицательных базисных решений системы совпадает с алгоритмом перебора базисных точек соответствующего допустимого множества. Следует отметить, что в начале перебора должна быть известна исходная базисная точка.

Определение 3. Пусть имеется базисная точка допустимого множества ЗЛП  Координаты  будем в дальнейшем называть базисными, - небазисными. Соответственно множество I - множеством базисных индексов, J - множеством небазисных индексов.

  В случае невырожденной задачи по каждой базисной точке восстанавливается соответствующий базис, состоящий из векторов . Обозначим его через B. Заметим далее, что каждая итерация метода Жордана-Гаусса соответствует переходу от одной базисной точки к другой при замене одной базисной (зависимой) переменной на одну небазисную (свободную). При этом выбору подлежит номер небазисной переменной k и жестко определяется номер базисной переменной l (смотри шаги 3а и 4а алгоритма).

Координаты новой базисной точки вычисляются следующим образом:

                                   (8)

Таким образом, ранее