Реферат: Содержание

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

Часть I


Содержание:
Линейное программирование 1

Содержание: 2

1. Основные понятия 3

1.1. Примеры моделей, приводящих к задачам линейного программирования 3

1.2. Стандартная и каноническая формы задачи линейного программирования 8

1.3. Геометрическая интерпретация задач линейного программирования 16

2. Симплекс-метод 24

2.1. Выпуклые множества и многогранники 24

2.2. Вершины выпуклого многогранника 29

2.3. Переход от вершины к вершине 35

2.4. Переход к новому базису 38

2.5. Отыскание оптимального плана 40

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

2.7. Метод искусственного базиса 51

3. Двойственные задачи 56

3.1. Постановка двойственных задач 56

3.2. Свойства двойственных задач 59

3.3. Двойственный симплекс-метод 66

4. Транспортная задача 67

4.1. Постановка задачи 67

4.2. Простейшие свойства транспортной задачи 69

4.3. Методы определения первоначального опорного плана 71

4.3.1. Построение исходного опорного плана (метод северо-западного угла) 71

4.3.2. Метод минимального (максимального) элемента 76

4.3.3. Метод аппроксимации Фогеля 78

4.3.4. Метод двойного предпочтения 80

4.4. Методы проверки опорного плана на оптимальность 82

4.4.1. Потенциалы. Критерий оптимальности плана 82

4.4.2. Дельта-метод 87

4.5. Алгоритм улучшения плана 89

4.6. Снятие вырожденности 95

4.6.1. Эпсилон-прием 95

4.6.2. 0-подстановка 100
^ 1. Основные понятия 1.1. Примеры моделей, приводящих к задачам линейного программирования
Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. В общей постановке задачи этого раздела выглядят следующим образом.

Имеются какие-то переменные и функция этих переменных , которая носит название целевой функции. Ставится задача: найти экстремум (максимум или минимум) целевой функции при условии, что переменные x принадлежат некоторой области G:



В зависимости от вида функции и области G и различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Подробнее об этом будет сказано в заключении.

^ Линейное программирование характеризуется тем, что

а) функция

является линейной функцией переменных ;

 

б) область G определяется системой линейных равенств или неравенств.

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

^ Задача о диете

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

Предположим, что в нашем распоряжении имеется n продуктов питания (сено, зерно, комбикорм, соль и т.д.). Обозначим эти продукты через

. Предположим, что

есть стоимость единицы веса (например,




стоимость одного килограмма) продукта .

Рациональная диета должна доставлять животному определенные компоненты (белки, жиры, углеводы, витамины, микроэлементы и т.д.). Обозначим эти компоненты через . Тогда можно составить таблицу - справочник, указывающую, какое количество каждого компонента имеется в единице веса каждого продукта.

 





...



 ...









...



...









...



...



...

...

...

...

...

...

...







...



...



...

...

...

...

...

...

...







...



...



 

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

^ Рацион кормления должен указать, какое количество i-го продукта должно быть скормлено животному за определенный срок (скажем, за месяц). Он означает, что за этот срок животное должно получить единиц первого

продукта,

единиц второго, ... ,

единиц n-го продукта.

Что же требуется от рациона? Во-первых, должны быть выполнены определенные медицинские требования, которые заключаются в том, что за указанный срок животное должно получить не менее определенного количества каждого компонента (не менее определенного количества белков, жиров, витаминов и т.д.). Обозначим через то минимальное количество j-го компонента, которое должно получить животное. Тогда рацион кормления должен удовлетворять ограничениям



(1.1)




Кроме того очевидно, что все переменные

неотрицательны, т.е.






...

 

(1.2)




Пусть стоимость единицы веса i-го продукта равна .

Тогда весь наш




рацион будет стоить

(1.3)

Мы, естественно, хотели бы понести минимальные затраты на содержание животных. Поэтому задача приобретает вид: найти рацион минимальной стоимости при выполнении медицинских ограничений (1.1) и естественных ограничений (1.2). Математически это выглядит так:



(1.4)

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

Рассмотрим теперь другую классическую задачу.



^ Задача о составление плана производства


Рассмотрим деятельность некоторой производственной единицы (цеха, отдела и т.д.). Пусть наша производственная единица может производить




некоторые товары

 




Для производства этих товаров приходится использовать некоторые сырьевые ресурсы. Пусть число этих ресурсов есть m; обозначим их через .
Tехнологией производства товара назовем набор чисел , показывающий, какое количество i-го ресурса необходимо для производства единицы товара . Это можно записать в виде технологической матрицы, которая полностью описывает технологические потребности




производства и элементами которой являются числа .

 

 





...



...









...



...









...



...



...

...

...

...

...

...

...







...



...



...

...

...

...

...

...

...







...



...



 

Пусть у нас имеется запасов каждого ресурса и мы планируем произвести единиц i-го товара. Так как мы не можем выскочить за пределы имеющихся у нас ресурсов, то наш план производства должен удовлетворять ограничениям



(1.5)




при очевидных условиях не отрицательности переменных :

 






...

.

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



(1.6)

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

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

,

а в задаче о плане производства  вид

.

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

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

, ,

и т.д. Обозначение

будет означать, что




Соответственно, запись

означает, что

 

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



(1.7)

Введем вектора

; ; ,

a также вектора

,

и матрицу

.

Заметим, что комбинация есть не что иное, как скалярное произведение векторов и . Поэтому в векторной форме задача (1.7) примет вид



(1.8)

Можно использовать и матричные обозначения. Тогда комбинация

есть произведение

и задача (1.7) примет вид






(1.9)

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



(1.10)

В векторной форме эта задача имеет вид



(1.11)

и в матричной форме - вид



(1.12)

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



(1.13)

В векторной форме эта задача имеет вид



(1.14)

 

и в матричной форме - вид



(1.15)

Во всех этих задачах функцию называют целевой функцией. Вектор называют вектором коэффициентов линейной формы, вектор  вектором ограничений.

Матрицу

называют матрицей коэффициентов.

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

^ Правила приведения задач линейного программирования к стандартной и канонической формам

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

^ 1. Превращение мах в min и наоборот.

Если целевая функция в задаче линейного программирования задана в виде

,

то, умножая её на (- 1), приведем её к виду

,

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

на .




Аналогично можно заменить

на .


^ 2. Смена знака неравенства.

Если ограничение задано в виде

,

то, умножая на (- 1), получим:

.

Аналогично, неравенство вида больше либо равно можно превратить в неравенство вида меньше либо равно .

^ 3. Превращение равенства в систему неравенств.

Если ограничение задано в виде

,

то его можно заменить эквивалентной системой двух неравенств

,

,

или такой же системой неравенств со знаками больше либо равно .

Указанные выше приемы позволяют приводить задачи линейного программирования к стандартной форме.


^ 4. Превращение неравенств в равенства.

Пусть исходная форма задачи линейного программирования имеет вид







(1.16)





Здесь первые r ограничений имеют вид неравенств со знаком меньше либо равно



затем идет группа неравенств со знаком больше либо равно



и, наконец, группа ограничений со знаком = .

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







(1.17)



,

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

В целевую функцию эти дополнительные переменные включают с коэффициентом 0, т.е. фактически они в целевой функции отсутствуют.

Получив решение задачи (1.17), т.е. решение задачи в канонической форме, для получения решения исходной задачи (1.16) надо просто выбросить из решения значения введенных дополнительных переменных.

Пример

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



Введем дополнительные переменные . Переводя мах в min, запишем задачу в виде



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

^ 5. Ограничения на неотрицательность переменных.

Во всех приведенных выше формах требуется, чтобы все переменные были

неотрицательны, т.е.

 




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




неотрицательности какой-то переменной

может отсутствовать вообще.

Рассмотрим, как поступать в этих случаях.

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



После этого, заменив в исходной задаче на мы получим задачу линейного программирования в канонической форме.

б) Пусть на наложено двустороннее ограничение вида .Введем переменную . Тогда будет , что дает ограничения в стандартной форме.

Вводя дополнительную неотрицательную переменную , можно записать двустороннее ограничение в виде



(1.18)

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

Задачи

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

1.



2.




3.



4.






Б. Напишите задачи 1,2 в стандартных формах.
^ 1.3. Геометрическая интерпретация задач линейного программирования
Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n =2 и n =3.

Наиболее наглядна эта интерпретация для случая n =2, т.е. для случая двух переменных и . Пусть нам задана задача линейного программирования в стандартной форме



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



Обратим прежде всего внимание на ограничения и . Они из всей плоскости вырезают лишь её первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида . Сначала рассмотрим область, соответствующую равенству . Как Вы, конечно, знаете, это прямая линия. Строить её проще всего по двум точкам.

Пусть . Если взять , то получится . Если взять , то получится . Таким образом, на прямой лежат две точки и . Дальше через эти две точки можно по линейке провести прямую линию (смотри рисунок 2).




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

соответствующее ему значение .

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной её части , а в другой наоборот . Узнать, в какой полуплоскости какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т.е. точка (0,0).

Пример

Определить полуплоскость, определяемую неравенством .

Решение

Сначала строим прямую . Полагая получим или . Полагая получим или . Таким образом, наша пря- мая проходит через точки (0, -1/2) и (3/4, 0) (см. рис. 3)

Теперь посмотрим, в какой полуплоскости лежит точка (0,0), т.е. начало координат. Имеем , т.е. начало координат принадлежит полуплоскости, где . Тем самым определилась и нужная нам полуплоскость (см. рис. 3).



Вернёмся теперь к задаче линейного программирования. Там имеют место m неравенств



(1.20)

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

естественно, надо добавить ограничения и ).

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

Пример

Найти допустимую область задачи линейного программирования, определяемую ограничениями



(1.21)

 



Решение

Рассмотрим прямую . При , а при . Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4а.

Рассмотрим прямую . При , а при . Таким образом, эта прямая проходит через точки (0, -1/2) и (1,0). так как 4.б).

Наконец, рассмотрим прямую . Она проходит через точки (0,3) и (3,0) и так как 0+0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.в).



Сводя все вместе и добавляя условия, получим рисунок 5, где выделена область, в которой выполняются одновременно все ограничения (1.21). Обратите внимание на то, что получившаяся область имеет вид выпуклого многоугольника.

Вернемся теперь к общему случаю, когда одновременно выполняются неравенства



(1.22)

Не приводя строгих доказательств, укажем те случаи, которые тут могут получится.

Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника ( см. рис. 6).

2. Неосновной случай  получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение . Оставшаяся часть будет неограниченным выпуклым многоугольником.



Наконец, возможен случай, когда неравенства (1.22) противоречат друг другу, и допустимая область вообще пуста.

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



Рассмотрим прямую. Будем увеличивать L. Что будет происходить с нашей прямой?

Легко догадаться, что прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором , так как это  вектор нормали к нашей прямой и одновременно вектор градиента функции .

А теперь сведем всё вместе. Итак, надо решить задачу





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

Увеличивая L мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (см. рис. 9). В конце концов, эта прямая выйдет на границу допустимой области,  как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение



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


Пример

Решить задачу



(1.23)


Решение

Допустимую область мы уже строили  она изображена на рис. 5.

Повторим еще раз этот рисунок, оставив только допустимую область и

нарисовав дополнительно прямые

(см. рис. 10).



Пусть, например, L=2. Тогда прямая проходит через точки (2,0) и (0,1) и изображена на рис. 10. Будем теперь увеличивать L. Тогда прямая начнёт двигаться параллельно самой себе в направлении, указанном стрелкой. Легко догадаться, что максимальное значение L получится тогда, когда прямая пройдет через вершину многоугольника, указанную на рисунке, и дальнейшее увеличение L приведет к тому, что прямая выйдет за пределы многоугольника и её пересечение с допустимой областью будет пустым.

Выделенная вершина лежит на пересечении прямых



и поэтому имеет координаты . Это и есть решение нашей задачи, т.е. есть оптимальный план задачи (1.23). При этом значение целевой функции , что и дает её максимальное значение.

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




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

Подводя итог этим примерам, можно сформулировать следующие положения:

допустимая область  это выпуклый многоугольник;

оптимум достигается в вершине допустимой области (если допустимая область ограничена и не пуста);

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

Дальнейшее будет посвящено более строгому обоснованию этих утверждений и формулировке алгоритма решения.

^ Задачи

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


1> 2. Симплекс-метод


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

Рассмотрим n - мерное евклидово пространство  и пусть  точка в этом пространстве.

Рассмотрим две точки и , принадлежащие .Множество точек , которые могут быть представлены в виде



(в координатах это записывается так:

,

называется выпуклой комбинацией точек и

, или

отрезком, соединяющим точки и . Сами точки и называются концами отрезка. В случаях n =2 и n =3 это  отрезок в обычном понимании этого слова на плоскости или в пространстве (см. рис. 12). Заметим, что при  =0 , а при  =1 , т.е. при  =0 и  =1 получаются концы отрезка.



 

Пусть в

заданы k точек

. Точка

,

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

Пусть есть некоторая область в пространстве (другими словами,

G есть некоторое множество точек из

).

Определение. Множество (область) называется выпуклым, если из того, что и следует, что для   [0,1]. Другими словами, G  выпуклое множество, если оно, вместе с любыми двумя своими точками, содержит в себе отрезок, соединяющий эти точки.



 

На этих рисунках "а" и "б" - выпуклые множества, а "в" не является выпуклым множеством, так как в нём есть такая пара точек, что соединяющий их отрезок не весь принадлежит этому множеству.

Теорема 1. Пусть G  выпуклое множество. Тогда любая выпуклая комбинация точек, принадлежащих этому множеству, также принадлежит этому множеству.

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

Пусть

 точки, принадлежащие множеству G .

Докажем теорему методом математической индукции. При k =2 теорема верна, так как она просто переходит в определение выпуклого множества.

Пусть теорема верна для некоторого k. Возьмём точку и рассмотрим выпуклую комбинацию

,

где все

и .




Представим

в виде



Но коэффициенты

и

,

и, раз мы считаем, что для k теорема верна, точка

.

Но тогда является выпуклой комбинацией точек

и и, по определению выпуклого множества, .

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

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

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

В стандартной форме в матричных обозначениях допустимая область G определяется условием



Пусть

и

принадлежат G , т.е.



Но тогда для

имеем






т.е. x принадлежит G и, следовательно, выпукло.

 

В канонической форме область G определена условиями



Пусть и принадлежат G, т.е.

.

Но тогда для

имеем







т.е. и, следовательно, G выпукло. Теорема доказана.

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

многогранником в n - мерном пространстве

 

 

Теорема 3. Множество оптимальных планов задачи линейного программирования выпукло (если оно не пусто).

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

Если решение задачи линейного программирования единственно, то оно выпукло по определению  точка считается выпуклым множеством Пусть теперь и два оптимальных плана задачи линейного  программирования.

Тогда

и .




Рассмотрим .

В силу выпуклости области




допустимых значений, .

Но для этого плана





т.е. есть также оптимальный план и, в силу этого, множество оптимальный планов выпукло. Теорема доказана.

Теорема 4. Для того, чтобы задача линейного программирования имела решение, необходимо и достаточно, чтобы целевая функция на допустимом множестве была ограничена сверху (при решении задачи на максимум) или снизу (при решении задачи на минимум).
2.2. Вершины выпуклого многогранника
На примере задачи линейного программирования с n=2 мы видели, что особую роль играют вершины допустимой области. Но что понимать под вершиной выпуклого многогранника при n>3, когда не существует геометрически наглядного образа ?

Легко заметить, что при n=2 и n=3 вершина выпуклого многогранника  это такая точка, которая не является внутренней точкой никакого отрезка, концы которого принадлежат этому многограннику (см. рис 14). Этим свойством обладают только вершины .



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

Докажем теперь несколько важных теорем, касающихся вершин выпуклых многогранников.

Теорема 1. Любая точка выпуклого многогранника является выпуклой комбинацией его вершин.

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

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

Пусть n=2 и мы имеем выпуклый многогранник G (см. рис. 15) с вершинами .Возьмём любую его точку A и соединим отрезком с какой-то вершиной, скажем . Продолжим эту прямую до пересечения с какой-то стороной многогранника и обозначим точку этого пересечения через B

(см.рис. 15). Тогда A является выпуклой комбинацией точек

и B.




Но B лежит на отрезке

и поэтому B



Рис. 15

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

Поэтому A является




выпуклой комбинацией вершин

Аналогично обстоит дело и в случае n =3. Посмотрите на рисунок и попробуйте сами повторить те же рассуждения, что и выше. Выпуклой комбинацией, каких вершин является точка A , изображенная на правой части рисунка 15?

В общем случае выпуклого n-мерного многогранника рассуждения выглядят примерно так.

Берем любую внутреннюю точку A этого многогранника и соединяем её отрезком прямой с какой-то из вершин. Продолжим эту прямую до пересечения с какой-то из граней выпуклого многогранника. Пусть точка этого пересечения будет B .Тогда точка A будет выпуклой комбинацией этой вершины и точки B .

Но что такое грань выпуклого многогранника? Это тоже выпуклый многогранник, но только размерности (n  1). Поэтому весь процесс можно повторить для точки B , перейдя к многограннику размерности (n -2), затем (n -3) и т.д.

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

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

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

Обозначим вершины выпуклого многогранника через .

Пусть для определенности мы ищем минимум . Пусть оптимальный план есть . Это означает, что для всех из допустимой области.

Если  вершина, то первую часть теоремы можно считать доказанной.

Пусть теперь  не вершина. Тогда её можно представить как выпуклую комбинацию вершин



Поскольку

 линейный функционал, то



Обозначим через m минимум из всех значений , и пусть он достигается

в вершине

 

, т.е.



Но тогда, так как ,

то

 

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

Для доказательства второй части теоремы допустим, что принимает свое минимальное значение на нескольких вершинах сразу, например, на . Тогда Если  выпуклая комбинация этих вершин



то

принадлежит допустимой области и



что и доказывает теорему.

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

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

Теорема 3. Если известно, что система векторов линейно независима и такова, что где все , то точка является вершиной допустимой области.

Замечание. Заметим, что в отличны от нуля совсем не обязательно первые k компонент. Первыми мы написали их только для упрощения доказательства, а вообще речь идет о любых k компонентах из общего числа n компонент.

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

Предположим, что не вершина. Тогда найдутся два таких плана и

,что

является их выпуклой комбинацией, то есть



Так как все компоненты векторов и

неотрицательны и последние




nk компонент вектора

есть нули, то и соответствующие им




компоненты векторов и

тоже нули, то есть





Так как и

планы, то

,

.

Вычитая, их друг из друга, получим

.

Но в силу линейной независимости векторов это может быть лишь тогда, когда



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

Теорема 4. Если вершина, то вектора , соответствующие отличным от нуля компонентам , образуют линейно независимую систему.

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

Пусть не равными нулю являются первые k компонент вектора x

, так что




.

(1)

Докажем теорему методом от противного. Пусть система векторов линейно зависима . Тогда существуют такие числа , не все равные нулю, что

.

(2)

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



Выбирая  достаточно малым можно всегда добиться того, что будут больше нуля для всех (для этого достаточно взять , где минимум берется по всем тем i , для которых . Тогда мы получим два плана

,

.

Но тогда , что противоречит тому, что - вершина. Теорема доказана.

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


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

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

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

Пусть нам известен какой-то опорный план (вершина), соответствующий m векторам из первоначальной системы n векторов. Будем считать, что

этими векторами являются первые m векторов

из системы




векторов .

Опорный план имеет вид

,

где все .

Для него




.

(3)

Так как векторы линейно независимы, то они образуют базис

в m -мерном пространстве и любой из векторов

может быть разложен




поэтому базису, то есть для любого

верно разложение




,

(4)

где  коэффициенты разложения по базису (координаты вектора в базисе .

Возьмем какой-то вектор, не входящий в наш базис, скажем, вектор . Для него

.

(5)

Пусть хотя бы один из коэффициентов положителен. Возьмем некоторую величину , умножим на неё обе части равенства (5) и вычтем из (3). Тогда получим



Вектор



в случае неотрицательности всех своих компонент является планом. Те компоненты, где , будут автоматически неотрицательны. Чтобы остальные компоненты были неотрицательны, надо, чтобы



Отсюда имеем:



Возьмем

,

где минимум берется по всем тем индексам i , для которых . Очевидно, что если , то все компоненты плана будут неотрицательны.

Но давайте возьмем  в точности равным .

Пусть, например,






достигается при i =1, то есть .

Но тогда




компонента

обратится в ноль и мы получим план

,

где



(7)

который опять содержит ровно m отличных от нуля положительных компонент.

Докажем, что это - новая вершина, то есть это  новый опорный план. Действительно, этому новому плану соответствуют векторы . Допустим, что они линейно зависимы, то есть существуют такие числа , не все равные нулю, что векторы

уже были линейно независимы, поэтому . Но тогда ,где . Но раньше у нас было (см. (5))

.

Так как разложение по базису определяется однозначно, то должно быть, в частности, должно быть =0. Это противоречит тому, что >0. Значит, система векторов линейно независима и мы перешли к новой вершине, то есть получили новый опорный план.

Отметим следующее. Если все , то мы не в состоянии проделать эту процедуру. Зато, неограниченно увеличивая , мы можем получить план со сколь угодно большими компонентами. Зна