Конспект лекций по теории систем управления (994584), страница 4

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

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

Пример: 2

F= 0.25x₁ + 0.3x₂ max

x ₁ + x₂  100

x₁ ≥ 80

x₂ ≥ 10

x₁  0; х₂  0

C ₂

x₂

100 f

A S

B C x₁

80 C₁

Рис. 11.

Решением является точка A.

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

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

, (0)

, (0)

где

- вектор размерности , ,

- матрица размера ранга ,

b - вектор размерности , .

Скалярное произведение называется целевой функцией. Коэффициенты целевой функции - это координаты вектора .

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

Задача (0) -называется задачей линейного программирования в каноническом виде.

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

Для решения задач линейного программирования применяют симплекс-метод и его модификации.

Симплексный метод.

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

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

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

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

Аналогично переменные , на которые не наложено требование не отрицательности переменных, представляются в виде:

Эти и некоторые другие преобразования используются для приведения задачи к каноническому виду. Подробное изложение симплекс-метода можно найти в [].

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

Теорема 1(теорема существования).

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

Теорема 2(теорема двойственности).

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

Теорема 3(теорема о дополняющей нежесткости).

Для того, чтобы допустимые векторы x*, y* являлись решениями двойственных задач, необходимо и достаточно, чтобы они удовлетворяли условиям дополняющей нежесткости, то есть:

Альтернативные варианты, возникающие при решении задач линейного программирования.

нет решений

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

При n=2 задачи линейного программирования можно решать графически.

F = c₁x₁ + c₂x₂  max (min)

a₁₁x₁ + a₁₂x₂  b₁

.

.

a_m1x₁ + a_m2x₂  b_m

x₁  0; х₂  0

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

Градиент целевой функции f, обозначаемый f

Для линейной функции градиент представляется в виде

Градиент f показывает направление наискорейшего возрастания функции. Антиградиент (-f) показывает направление наискорейшего убывания функции.

Линия уровня функции - это линия, где функция имеет одинаковые значения. Для линейной функции f линии уровня перпендикулярны градиенту f.

Пример: 1

F= 1x₁ + 2x₂ max

x ₁ + x₂  5

x₁  0; х₂  0

C₂

x₂

A f

5

f=10

S

5 B x₁

C₁

f=0

Рис. 10.

В точке А функция будет иметь максимальное значение.

Пример: 2

F= 1x₁ + 1x₂ max

x ₁ + x₂  5

x₁  0; х₂  0

C ₂

x₂

5 A f

S B

5 x₁

C₁

Рис. 11.

Решение задачи отрезок АВ

Пример: 3

f(x)=x₁+x₂max

x₁ + x₂  5

S x₁ + x₂  6

x₁  0; х₂  0

Рис. 12.

Решение нет, т.к. допустимая область S пуста.

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

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

Если исходная задача (прямая)

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

то двойственная задача представляет задачу на минимум

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

то есть в развернутом виде:

прямая:

двойственная:

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

Таблица для двойственных задач линейного программирования:

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

Устойчивость плановых решений (для модели однокритериального планирования)

Задача однокритериального планирования

f = c₁x₁ + c₂x₂  max (min)

a₁₁x₁ + a₁₂x₂  b₁

.

S .

a_m1x₁ + a_m2x₂ b_m

x₁  0; х₂  0

S – допустимая область решения

c
_i – весовые коэффициенты целевой функции, ,

Сначала рассмотрим влияние интервалов неопределенности параметров c_i на устойчивость решения исходной задачи:

f = c₁x₁ + c₂x₂  max (min)

a₁₁x₁ + a₁₂x₂  b₁

.

S .

a_m1x₁ + a_m2x₂ b_m

x₁  0; х₂  0

При проверке на устойчивость мы должны перейти к следующим задачам:

f₁ = c₁ min x₁ + c₂ max x₂  max (2)

x  S

f₂ = c₁ max x₁ + c₂ min x₂  max (3)

x  S

Рис. 13.

Решением всех трех задач будет точка А. Решение устойчиво.

Правило: Если решение исходной задачи (1), не совпадает с решением задачи (2) или с решением задачи (3), то решение исходной задачи (1) при интервальной неопределенности неустойчиво, в противном случае решение исходной задачи (1) устойчиво.

Пример: Исходная задача (1)

f = c₁x₁ + c₂x₂  max

2х₁ + 3х₂  6

S:

x₁  0; х₂  0

с₁ = 1; с₂ = 2

с₁  [0,5 ; 1,5] с₂  [1,5 ; 2,5]

Проверить решение исходной задачи на устойчивость

Рис. 14.

Решение исходной задачи (1) не устойчиво, т.к. решения задач (1) и (3) не совпадают.

2 случай

f= c₁x₁+c₂x₂ → max

a ₁₁x₁+a₁₂x₂ ≤ b₁

_.

_. (1)

_.

a_m1x₁+a_m2x₂≤ b_m

x₁≥0, x₂≥0

Рис. 15.

При такой интервальной неопределенности аji решение исходной задачи неустойчиво.

3 случай

f=c₁x₁ +c₂x₂ → max

a₁₁x₁+a₁₂≤b₁

_.

_.

a_m1x₁+a_m2x₂≤b_m

x₁≥0, x₂≥0

Рис. 16

Решение при такой интервальной неопределенности , решение задачи (1) неустойчиво.

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

.

.

a₁₁x₁ + a₁₂x₂  в₁

.

S .

a_m1x₁ + a_m2x₂ в_m

x₁  0; х₂  0

S – допустимая область решения

f_1…..f_l – частный критерий оптимальности

С^k_l – коэффициент частный критерий оптимальности

b

_j – запасы j-ого вида ресурса, предназначено для выполнения критериального плана,

a_ji- расход j-ого ресурса на выпуск единиц i-ого вида продукта.

Метод решения

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

(0)

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

Задачу (0) можно называть задачей многоцелевой оптимизации, предполагая, что одной цели соответствует один критерий.

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

• задача векторной оптимизации;

• многокритериальная задача оптимизации;

• задача многоцелевой оптимизации.

Дело в том, что реальные задачи, а особенно задачи, связанные с созданием АСУ, САПР, задачи системного анализа, теории больших систем и так далее, в основном многокритериальные, поэтому сама жизнь требует умения их решать, что подчеркивает актуальность проблемы.

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

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

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

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

Список файлов лекций