Геометрическая интерпретация задачи ЛП и графо-аналитический метод ее решения.

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

Взаимодействие линий уровня с ОДР позволяет найти оптимальный план (решения) задачи ЛП - .

Пусть задача ЛП в имеет вид:

(1)

ОДР - выпуклое множество. Каждое из неравенств (2) определяет полуплоскость (выпуклое множество). Пересечение этих множеств дает область , которая будет выпуклым множеством.

Множество называется выпуклым, если выполняется условие:

, (4), где - точки, принадлежащие множеству, а - точка, находящаяся на отрезке .

(5)

 

 

 

 

В - также выпуклое множество (выпуклый многогранник).

Семейство линий уровня целевой функции в имеет вид:

Находим вектор и далее находим .

В пространстве целесообразно говорить о семействе гиперплоскостей уровня. Взаимодействие этих гиперплоскостей с ОДР позволяет найти оптимальный план .

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

- выпуклый многоугольник.

Оптимальные планы находятся в вершинах выпуклого многоугольника.

 

 

- выпуклый многоугольник.

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

 

Целевая функция неограниченна.

 

 

ЛК №6

08.10.2003

 

 

Основная теорема линейного программирования (ОТЛП).

 

Теоремы о свойствах решения задачи ЛП.

Представим задачу ЛП в виде:

(1)

где , , …, , .

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

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

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

Предположим, что , т.е. 1-е уравнений (2) линейно-независимы. В этом случае системы векторов содержит в себе подсистему линейно-независимых векторов . Переменные , соответствующие векторам , называются линейно-независимыми (базисными) переменными (БП). Поскольку они соответствуют линейно-независимым векторам, образующим базис, по которым может быть разложен любой вектор . Остальные переменные называются свободными переменными (СП).

Если положить СП равными нулю и при этом , , т.е. БП – неотрицательны, то вектор

представляет опорное решение (план) задачи ЛП.

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

Доказательство см. в [5].

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

 

ОТЛП легко наблюдаема при усмотрении 1-го и 2-го случая геометрической интерпретации задачи ЛП в .

 

 

 

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

Доказательство см. в [5].

 

Симплексный метод решения задачи ЛП.

Симплексный метод (СМ) – универсальный аналитико-численный эффективный метод решения задач ЛП.

 

Идея СМ.

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

Эта теорема позволяет сформулировать основные этапы алгоритма прямого метода решения задач ЛП:

1) нахождение координат крайних точек многогранника решений;

2) вычисление значений в указанных выше точках;

3) нахождение минимального (максимального) значения и, соответственно, и .

Неэффективность этого метода очевидна, особенно с ростом размерности пространства.

Симплексный метод (метод последовательного получения планов), также как и прямой метод, состоит из 3-х этапов:

1) построение начального опорного плана;

2) формулировка критерия оптимальности опорного плана;

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

Эффек­тивность СМ значительно выше эффек­тивности " прямого" ме­тода. Универ­сальность СМ в сочетании с эффективно­стью позво­ляют исполь­зовать его в ре­шении значи­тельной части за­дач ЛП кроме наиболее легких.

Идея СМ легко понимаема при графической интерпретации задачи ЛП.

 

ЛК №7

15.10.2003

 

Из решения видно, что прямой метод предполагает вычисление в точках . Среди этих 6-ти значений – 2 экстремальных, которые легко находятся и .

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

СМ " выбирает" оптимальную траекторию поиска экстремальных точек во множестве крайних точек многогранника планов.

 

3.6.1. Построение начального опорного плана.

Пусть каноническая задача ЛП имеет систему линейных уравнений ограничений вида:

(1)

Для того, чтобы найти начальный опорный план , необходимо (1) представить в предпочтительном виде.

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

.

Заметим, что переменные называются предпочтительными переменными, переменные - свободными (независимыми) переменными.

Полагая , т.е. , , получаем: , , .

Начальный опорный план: .

Легко понять, что предпочтительная переменная – базисная переменная, в соответствии с определением опорного плана.

Предположим, что система ограничений задач ЛП имеет вид:

. (2)

Известно, что вводя дополнительные (балансовые) переменные: , линейных неравенств

 

 

Поскольку дополнительные (балансовые) переменные входят в каждое уравнение системы с коэффициентом, равным 1 и входят в другие уравнения с коэффициентом, равным 0.

 

 

(3)

Система (3) имеет предпочтительный вид: каждая СП равными 0:

Предположим, что система неравенств ограничения имеет вид:

(4)

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

(5)

Начальный опорный план вида: не может быть допустимым опорным планом из-за отрицательности балансовых переменных.

Рассмотрим случай, когда в системе линейных уравнений ограничений ни одно из уравнений не имеет предпочтительного вида:

(6)

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

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

Итак, с введением искусственного базиса исходная каноническая задача ЛП преобразуется в расширенную задачу ЛП -типа:

(2)

 

 

Знак " " относится к задаче на " ", " ".

-задача ЛП с искусственным базисом реализуется методом, получившим название " СМ с искусственным базисом".

Очевидно, что начальный опорный план (7) имеет вид:

.

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

Пусть - оптимальный план -задачи, а - оптимальный план исходной задачи, только в случае, если

 

3.6.3. Симплексные таблицы. Признак оптимальности опорного плана.

Как известно, корректно сформулированную задачу ЛП всегда можно представить в канонической форме вида:

(1)

(2)

Заметим, что целевая функция представляется как функция только СП: .

, ;

, .

При решении (1), (2), (3) СМ целесообразно представить ее с помощью таблицы, которая называется симплексной таблицей (СТ).

 

 

БП

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

 

ЛК №8

22.10.2003

 

 

СМ - итерационный метод и каждому опорному плану будет соответствовать своя СТ.

 

Как видно, СТ состоит из строки и столбцов.

Значительную часть СТ занимает система уравнений ограничений экономической задачи ЛП. Система представлена в предпочтительном виде:

.

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

.

Величина называют оценками свободных переменных (СП), потому что они не равны нулю только для СП: ; для базисных переменных (БП): - эти величины равны нулю, т.е. .

.

Заметим, что из СТ с очевидностью вытекает структура вектор-столбца :

.

 

 

;

;

;

;

.

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

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

 

Признак оптимальности опорного плана.

Теорема 1: Пусть решается задача ЛП на максимум. Если для некоторого опорного плана все оценки СП неотрицательны, т.е. , то опорный план оптимален.

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

.

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

.

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

Теорема 2: Пусть решается задача ЛП на минимум. Если для некоторого опорного плана все оценки СП неположительны, т.е. , то опорный план оптимален.

 

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

.

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

.

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

Каждому опорному плану соответствует своя СТ, т.е. СМ – итерационный метод. В связи с этим, если рассматриваемый опорный план не оптимален, то следует перейти от него к нехудшему опорному плану.

 

3.6.4. Переход к нехудшему опорному плану; симплексное преобразование.

Пусть каноническая задача ЛП – задача на максимум имеет вид:

(1)

Известно, что система уравнений ограничений (2) имеет предпочтительный вид, поэтому начальный опорный план легко определить: .

Если в последней строке СТ все , (4), то начальный опорный план будет оптимальным: , . Далее предположим, что для некоторого столбца , . (5)

Вектор-столбец называется решающим столб-

 

ЛК №9

29.10.2003

 

 

цом СТ, а соответствующая ему переменная называется перспективной переменной.

Пусть все свободные переменные (кроме ) равны нулю, т.е.: , тогда выражение для целевой функции будет равно:

(7)

Причем , а .

Из (7) следует, что увеличивая СП , можно увеличить значение целевой функции, таким образом, переходя к нехудшему опорному плану (с большим значением целевой функции).

Однако, увеличивать перспективную переменную нужно " осторожно", чтобы не нарушить основное условие: , .

Рассмотрим в связи с этим (2), зная, что все СП (кроме ) равны нулю:

, , (9)

(9')

Из (9') при следует, что увеличение может привести к нарушению условия (8) (т.е. к отрицательности , ).

Перепишем (9') в виде:

(10)

, (11)

(12) - минимальное симплексное отношение.

. (13)

Выражение (12) позволяет найти разрешающую строку в СТ и соответственно разрешающий (ключевой) элемент СТ.

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

 

 

(14)

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

Соответственно, будет введена в множество СП, а из него выведена:

(15)

Как изменятся элементы СТ при перестановке вида (15)? Выясним детально этот вопрос, используя так называемое симплексное преобразование.

Исходными являются уравнения системы ограничений:

, (16)

Выделим из (16) уравнение и математически " реализуем" схему (15):

(17)

Далее подставим выражение для в (16) при условии :

(17а)

Итак, найденное для выражение (17а) подставляем в (16) при условии, что :

, (18)

где , .

 

ЛК №10

05.11.2003

 

После элементарных преобразований (18) преобразуется к виду:

(18а)

Система уравнений (18а) соответствует новой СТ, представляющей нехудший опорный план .

Легко понять, что ( ) этой новой СТ должны определяться по формуле:

(19)

(20)

Элементы строки (строки целевой функции) новой СТ легко найти, если воспользоваться известным выражением для целевой функции:

(21)

(22)

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

(23)

(24)

Совершив симплексные преобразования, получили аналитические выражения (17), (18а), (19), (20), (23), (24), позволяющие относительно просто заполнить новую СТ нехудшего опорного плана.

Основные правила заполнения новой СТ:

1) Элементы разрешающей строки исходной (старой) СТ: , для новой СТ должны быть найдены по формулам:

, ; .

Заметим, что элемент .

 

 

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

3) Элементы , , , , исходной (старой) СТ для новой СТ должны быть вычислены по формулам:

, , , , (19')

Приведем простую вычислительную схему для нахождения элементов (19').

4) Отметим, что структура формул, определяющих элементы новой СТ для , ,

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

5) Следует отметить, что элементы строки можно найти для новой СТ двумя способами: первый способ предполагает использовать (23) и (24), а второй – известных формул вида:

, .

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

Представляет интерес найти на каждом шаге итерации СМ приращение целевой функции:

, - номер итерации.

Как известно , .

 

,

где - наименьшее симплексное отношение (СО) на -той итерации.

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

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

 

3.6.5. Теорема бесконечности множества оптимальных планов задачи ЛП.

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

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: