g6 (542469), страница 2

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

Текст из файла (страница 2)

строка - целевая функция

строки-ограничения

Эти равенства можно свести в следующую симплекс - таблицу, в которой правая часть(ПЧ) соответствует их правым частям.

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

Базисные переменные отмечены в таблице слева, а значения базисных переменных записаны в правой части таблицы.

Эта таблица содержит всю информацию, необходимую для завершения первого шага симплекс метода.

Если процесс прекращается, то есть текущая точка является оптимальной.

В противном случае:

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

где

- вектор

- матрица

- вектор

- скаляр

Если - то процесс прекращается - значение целевой функции неограниченно.

Если , то

так как записаны под ПЧ и соответственно, то следуя ( 6.4 .0 ) легко вычислить .

Базисная переменная , соответствующая минимальному отношению в ( 6.4 .0 ), выводится из базиса, а вводится в базис.

Далее проводим ведущее преобразование:

Строка, соответствующая (выводимая переменная из базиса) - ведущая строка.

Столбец, соответствующий (вводимая переменная в базис) - ведущий столбец.

1. Разделить ведущую строку(соответствующую ) на ведущий элемент ;

2. Умножить новую r - ую строку на и результат вычесть из i - ой строки ограничений для всех

3. Умножить новую r - ую строку на и результат вычесть из строки целевой функции.

Пример:

Графически:

A(4/3, 11/3)

(0,3)

(0,0) (5,0)

Оптимальной является точка . Значение функции

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

Возьмем в качестве В матрицу

Так как ,

то найдена экстремальная точка:

- выводится из базиса

- вводится в базис

Новый базис

Теперь:

- выводится из базиса

- вводится в базис.

Новый базис

Так как , то получено оптимальное решение.

6.4.2Выбор начальной экстремальной точки.

Для использования симплекс - метода необходимо задать некоторую начальную экстремальную точку.

Из теоремы(о характеристиках экстремальных точек) нахождение начальной экстремальной точки связано с разбиением матрицы A на ,

где В - матрица m x m полного ранга, называемая базисом.

N - матрица m x (n-m) ,

так чтобы . В предыдущем примере начальная точка определялась легко. В практических задачах определить начальную точку не так - то легко. Для этого используются различные приемы.

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

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

1. Двухэтапный метод:

• на первом этапе решения задачи вводится вектор - вектор искусственных переменных размерности m.

где - вектор, все компоненты которого равны единице.

После окончания первого этапа:

либо , либо

Если исходная система несовместна, то есть допустимая область пуста.

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

• на втором этапе начиная из полученной точки решается задача минимизации целевой функции.

1. M - метод:

В этом методе также вводятся искусственные переменные и каждой искусственной переменной назначается большой положительный штраф M (больше любого c_i )

Задача линейного программирования принимает вид:

Если в оптимальном решении , то это означает, что получено решение исходной задачи.

Если , то это означает, что система ( ) не имеет решения.

Замечание 1.

(зацикливание)

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

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

• отказ от точки для которой ;

• случайный выбор новой угловой точки

и так далее.

Характеристики

Список файлов книги