Метод деформируемого многогранника.

Краткие выводы к РАЗДЕЛУ 2.

1. Изучены ЧМ одномерной минимизации (частный случай метода 0-го порядка): МД, МЗС, МФ.

2. детально исследованы основные ЧМ многомерной безусловной оптимизации 0-го, 1-го и 2-го порядков.

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

Вначале, используя методы 0-го порядка целесообразно найти в грубом приближении локальные и глобальные экстремумы. Затем, учитывая характерные особенности минимизируемой функции следует точно найти необходимые локальные экстремумы, используя более эффективные методы оптимизации 1-го и 2-го порядков.

 

ЛК №4

24.09.2003

 

 

РАЗДЕЛ 3

Линейное программирование (ЛП).

В этом разделе будут изучены экстремальные свойства линейных функций переменных вида:

(1)

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

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

Отметим, что значительная часть практически важных задач формируется как задачи ЛП.

К их числу относятся:

1) задача о рациональном размещении ресурсов;

2) задача об оптимальном выборе технологий;

3) задача о смесях;

4) задача о раскрое материалов;

5) транспортная задача.

За разработку симплексного метода решения задач ЛП группе математиков-экономистов в 70-х годах 20 в. Была присвоена нобелевская премия.

 

Формы записи задач ЛП.

А. Общая задача ЛП (ОЗЛП).

(1)

- целевая функция – линейная функция переменных;

- численные вещественные коэффициенты.

 

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

В ЛП называется оптимальным планом.

 

Б. Симметричная задача ЛП.

Существуют 2 вида задач:

1) (1)

2) (4)

 

В. Классическая (основная) задача ЛП.

(4)

 

Переход от симметричной формы записи ЛП к канонической.

Осуществляем путем введения неотрицательных дополнительных (балансовых) переменных: , . (1)

В симметрической задаче 1-го вида (задачи на max) в систему неравенств, определяющих дополнительная переменная вводится следующим образом:

.

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

 

(курс АтГ (часть 1))

 

АтГ (часть 1)

 

.

Целевую функцию дополнительные (балансовые) переменные вводят с коэффициентом равным нулю (т.е. не учитываются).

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

, где - матрица коэффициента

; ; ;

.

 

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

(1)

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

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

 

 

Прямой ход метода Гаусса.

 

ЛК №5

01.10.2003

 

 

(5)

Коэффициенты и определенным образом зависит от и .

Поскольку , то из (5) система линейных (6) неравенств вида:

, (7)

Из (7) ОДР представимо системой линейных неравенств, что свойственно задаче ЛП в симметричной форме.

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

, (8)

Отметим, что переменные , как известно, называются свободными (независимыми), а переменные называются базисными (зависимыми).

Подобно (7), которое содержит только свободные независимые переменные, выразим целевую функцию только через свободные переменные.

(9)

; ;

; , где , .

(10) – выражение, представляющее целевую функцию только как функцию свободных переменных.

 

 

См ПЗ весеннего семестра 2002/2003 учебного года.

 

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

(11)

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

 

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

Поделиться: