Основные понятия теории оптимизации

 

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

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

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

Этап 1. Вводятся искусственные переменные, необходимые для получения стартовой точки. Записывается новая целевая функция, предусматривающая минимизацию суммы искусственных переменных при исходных ограничениях, видоизменённых за счёт искусственных переменных. Если минимальное значение новой целевой функции равно нулю (т.е. все искусственные переменные в оптимуме равны нулю), то исходная задача имеет допустимое решение и переходим к Этапу 2.

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

Рассмотрим на примере.

Этап 1.

Минимизация

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

							Решение

 

Т.к. , можно переходить к Этапу 2.

Этап 2. Исходную задачу сформулируем следующим образом:

минимизировать

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

Теперь, приравняв x3=0, получим НДБР

Для решения задачи необходимо подставить в целевую функцию выражения для базисных переменных x1 и x2:

 

4. Двойственность

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

Прямая задача ЛП в  стандартной форме:

максимизировать (минимизировать)

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

В состав включаются избыточные и остаточные переменные.

 

 

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

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

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

 

Прямая задача в стандартной форме.	Двойственная задача
Целевая функция	Целевая функция	Ограничения	Переменные
Максимизация	Минимизация		Не ограничены в знаке
Минимизация	Максимизация		Не ограничены в знаке

 

Рассмотрим пример:

Прямая задача:

максимизировать

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

Прямая задача в стандартной форме:

максимизировать

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

Двойственная задача:

минимизировать

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

(означает, что y1>0). y1, y2 не ограничены в знаке.

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Библиографический список

 

      1.Онегов, В.А. Исследование операций. Задачи, методы, алгоритмы. – Киров: ВГПУ, 2001.

2. Сборник задач и упражнений по высшей математике: мат.  программирование: Учеб. Пособие/ А.В. Кузнецов, В.А. Сакович, Н.И.  Холод; Под. общ. ред. А.В. Кузнецова – Мн.: Выш. шк., 2002

3. Ф. П. Васильев, А. Ю. Иваницкий Линейное программирование -  Издательство: Факториал Пресс, 2003.

      4.  Н. И. Глебов, Ю. А. Кочетов, А. В. Плясунов,  Методы оптимизации  учебное пособие , Новосибирск: Новосибирский государственный  университет, 2000

      5. http://simplex-metod.narod.ru/