Линейное программирование Основные определения и теоремы icon

Линейное программирование Основные определения и теоремы



НазваниеЛинейное программирование Основные определения и теоремы
Дата конвертации29.09.2012
Размер169.74 Kb.
ТипЗадача
1. /ЛЕКЦИИ_МО/Двойственность задач ЛП.doc
2. /ЛЕКЦИИ_МО/Линейное программирование.doc
3. /ЛЕКЦИИ_МО/Метод Пауэлла и сопряженные направления.doc
4. /ЛЕКЦИИ_МО/Методы второго порядка.doc
5. /ЛЕКЦИИ_МО/Методы перв_порядка.doc
6. /ЛЕКЦИИ_МО/Методы переменной метрики.doc
7. /ЛЕКЦИИ_МО/Методы штрафных функций.doc
8. /ЛЕКЦИИ_МО/Параметрическое программирование_Р1.doc
9. /ЛЕКЦИИ_МО/Прямые методы.doc
10. /ЛЕКЦИИ_МО/Статистические методы поиска.doc
11. /ЛЕКЦИИ_МО/Трансп. задача с огр..doc
12. /ЛЕКЦИИ_МО/Транспортная задача.doc
Двойственность задачи линейного программирования
Линейное программирование Основные определения и теоремы
Метод Пауэлла и сопряженные направления
Методы второго порядка
Методы первого порядка
Методы переменной метрики
Методы штрафных функций
Параметрическое линейное программирование
Прямые методы
Статистические методы поиска
Транспортная задача с ограничениями на пропускные способности
Методы решения транспортной задачи

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

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



Определение 1. Задача, в которой требуется минимизировать (или максимизи­ровать) линейную форму



при условии, что

, ,

или

, ,

и

, gif" name="object7" align=absmiddle width=49 height=18>,

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

Определение 2. Задача в матричной форме вида

(1)

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

Определение 3. Задача линейного программирования вида

(2)

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

Любую задачу линейного программирования можно привести к кано­ни­ческой форме.

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

,

то можно, введя дополнительные переменные, привести ее к виду

, , ,

где .

Если же ограничения в задаче заданы в форме

,

то

, , .

Рассмотрим задачу с ограничениями . Эту систему ограничений можно представить в виде системы

.

Введем следующие обозначения:

, ,…, , ,…, , .

Тогда задачу линейного программирования можно записать в виде:



,

.

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

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

Определение 4. Набор чисел , удовлетворяющий огра­ни­чениям задачи линейного программирования называется ее планом.

Определение 5. Решением задачи линейного программирования называется ее план, минимизирующий (или максимизирующий) линейную форму.

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

. (3)

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

Умножим (3) на слева

, (4)

и найдем отсюда :

. (5)

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

Если положить , то

. (6)

Решение (6) называют базисным решением системы из уравнений с неизвестными.

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

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

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

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

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

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

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

Теорема 1: (основная теорема линейного программирования):

  1. Линейная форма достигает своего минимума в угловой точке многогранника решений.

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

Доказательство: Доказательство теоремы основано на следующей лемме.

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

1) Пусть - некоторая внутренняя точка. Многогранник ограниченный замкнутый, имеет конечное число угловых точек. - допустимое множество.

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

, , .

Так как функция линейна, то

. (*)

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

.

Подставим данное значение функции в линейную форму (*) вместо и получим:

.

Так как - оптимальная точка, то получили противоречие: (!). Следовательно, , - угловая точка.

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

, и ,

то .

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


Теорема 2: Если известно, что системы векторов условий , линейно независима и такова, что

,

где все , то точка является угловой точкой многогранника решений.


Теорема 3: Если вектор является угловой точкой многогранника решений, то векторы условий, соответствующие положительным компонентам вектора , являются линейно независимыми.


Следствия: 1) Угловая точка многогранника решений имеет не более положительных компонент вектора .

2) Каждой угловой точке многогранника решений соответствует линейно независимых векторов из данной системы: .

Симплекс метод



Или метод последовательного улучшения плана. Метод предназначен для решения общей задачи линейного программирования.

Пусть имеем следующую задачу:

, (1)

с системой ограничений следующего вида:

. (2)

Разрешим эту систему относительно переменных :

. (3)

Векторы условий, соответствующие , образуют базис. Перемен­ные назовем базисными переменными. Остальные переменные задачи – небазисные.

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

.

Если приравнять небазисные переменные нулю –

,

то соответствующие базисные переменные примут значения

.

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

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

Пример 1: Пусть



.

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

.

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

,

которому соответствует .

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



.

Соответствующий опорный план и .

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



.

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


Пример 2: Пусть имеем задачу



.

Переменные - базисные, а - небазисные переменные. Опорный план , .

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



.

Опорный план , значение целевой функции .

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

Замечание: В процессе поиска допустимого плана может быть выявлена противоречивость системы ограничений.

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



Формализованный алгоритм симплекс метода состоит из двух основных этапов: 1) построение опорного плана; 2) построение оптимального плана.

Проиллюстрируем алгоритм на рассмотренном ранее примере:



.

.

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









1

=

1

-2

1

=

-2

1

2

=

3

1

3

=

-1

1

0


Она уже соответствует опорному плану (столбец сво­бодных членов).

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

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

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

.

– разрешающий (направляющий) элемент, строка – разрешающая.

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

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


Шаг модифицированного жорданова исключения над симплексной таблицей.

  1. На месте разрешающего элемента ставится 1 и делится на разрешающий элемент.

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

  3. Остальные элементы разрешающей строки делятся на разрешающий элемент.

  4. Все остальные элементы симплексной таблицы вычисляются по следующей формуле:

.








1




Разрешающий элемент,

который соответствует замене

базисной переменной на

небазисную переменную .



1

-2

1




-2

1

2



3

1

3



-1

1

0











1




Разрешающий элемент,

который соответствует замене

базисной переменной на

небазисную переменную .



-3

2

5



-2

1

2




5

-1

1



1

-1

-2











1




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



3/5

7/5

28/5



2/5

3/5

12/5



1/5

-1/5

1/5



-1/5

-4/5

-11/5

Построение опорного плана. Пусть необходимо решить задачу:



.

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

,

где .

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








….



.…



1

0





….



….





….

….

.…

….

.…

.…

.…

.…

0





….



….











….



….





….

….

….

….

….

….

….









….



….











….



….



0


Правила выбора разрешающего элемента при поиске опорного плана.

  1. При условии отсутствия “0-строк” (ограничений-равенств) и “сво­бодных” перемен­ных (т.е. переменных, на которые не наложено требование неотри­цатель­ности).

  • Если в столбце свободных членов симплексной таблицы нет отрицательных элементов, то опорный план найден.

  • Есть отрицательные элементы в столбце свободных членов, например . В такой строке ищем отрицательный коэф­фициент , и этим самым определяем разрешающий столбец . Если не найдем отри­цательный , то система ограничений несовместна (противо­речива).

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

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


2. В случае присутствия ограничений-равенств и “свободных” переменных поступают следующим образом.

  • Выбирают разрешающий элемент в “0-строке” и делают шаг модифицированного жорданова исключения, после чего вычеркивают этот разрешающий столбец. Данную последовательность действий продолжают до тех пор, пока в симплексной таблице остается хотя бы одна “0-строка” (при этом таблица сокращается).

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



Вырожденность в задачах линейного программирования



Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно положительных компонент, где – число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда (число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида . Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку.

Аналогично при в вы­рож­денной задаче в одной вершине пересекается более 3-х плоскостей .

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

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

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

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

Пусть переменную необходимо сделать базисной. Рассмотрим мно­жество индексов , состоящее из тех , для которых достигается . Множество индексов , для которых выполняется данное условие обозначим через . Если состоит из одного элемента, то из базиса исключается вектор условий (переменная делается небазисной).

Если состоит более чем из одного элемента, то составляется множество , которое состоит из , на которых достигается . Если состоит из одного индекса , то из базиса выводится переменная . В противном случае составляется множество и т.д.

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



Похожие:

Линейное программирование Основные определения и теоремы iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Линейное программирование Основные определения и теоремы iconДокументы
1. /33 Барсов А.С. - Что такое линейное программирование (1959).djvu
2. /Прочитай...

Линейное программирование Основные определения и теоремы iconДокументы
1. /33 Барсов А.С. - Что такое линейное программирование (1959).djvu
2. /Прочитай...

Линейное программирование Основные определения и теоремы iconОдобрен Советом Республики 30 июня 2011 года глава 1 общие положения статья Основные термины, используемые в настоящем закон
Для целей настоящего Закона используются следующие основные термины и их определения
Линейное программирование Основные определения и теоремы iconДокументы
...
Линейное программирование Основные определения и теоремы icon1. Исходя из определения, найдите сумму ряда. 2
Найдите радиус сходимости степенного ряда и сумму этого ряда, применяя теоремы о дифференцировании и интегрировании рядов
Линейное программирование Основные определения и теоремы iconТема урока: «Сумма углов треугольника»
Цель урока: доказательство теоремы о сумме углов треугольника с применением ранее изученного материала; применение теоремы для нахождения...
Линейное программирование Основные определения и теоремы iconМетодические рекомендации по подготовке учащихся, получивших неудовлетворительные оценки на егэ-2009 по математике
Кзамене 06. 09, необходимо организовать дополнительные занятия, на которых повторить основные разделы школьного курса алгебры и начал...
Линейное программирование Основные определения и теоремы iconИздания. Основные элементы термины и определения Издание неофициальное Москва
Цели и принципы стандартизации в Российской Федерации установлены Федеральным законом от 27 декабря 2002 г. №184-фз «О техническом...
Линейное программирование Основные определения и теоремы iconЗакон республики беларусь
Для целей настоящего Закона используются следующие основные термины и их определения
Линейное программирование Основные определения и теоремы iconВ. А. Ермеев 2007г. Тематический план
Основные понятия и определения: гипертекст, гиперссылка, браузер, язык html, теги, контейнеры
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов