Экономический смысл двойственных оценок

n- количество продуктов производится.

Cj- цена j продукта

m- ресурсов используется.

Bi – наличие i-ого ресурсов

Aij-i –ая единица ресурса, надо для 1 единицы jого продукта

c- вектор стоимости

b-вектор ресурсов

А - технологическая матрица

Вводим переменную y – теневая цена

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

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

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

F(x)=Z(y) или .

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

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

Следствие1. Пусть оптимальное значение некоторой переменной двойственной задачи строго положительно

.

Тогда из условия (1) получим:

или

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

Следствие2. Пусть для оптимального значения некоторой переменной xi прямой задачи выполняется условие строгого неравенства

.

Тогда основываясь на том же первом условии (1) можно заключить, что yi=0.

Экономически это означает, что если в оптимальном плане какой-то ресурс используется не полностью, то его объективно обусловленная оценка обязательно равна нулю.

Теневые цены: если купить 1 единицу дополнительного ресурса, насколько увеличится прибыль. Если p(цена ресурсов) - не выгодно покупать

77. Управление проектами: сетевые графики проектов, метод критического пути.

Сетью называют ориентированный граф G (V,E), вершинам и дугам кот. приписаны числовые параметры: V вершины – события, E дуги – работы.

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

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

Направление дуги – отношение предшествования.

Сетевой график проекта удовлетворяет условиям:

-имеется одно начальное и одно заключительное события

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

Метод критического пути:

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

Алгоритм:

1) нумеруем события, проводим дуги из вершин с меньшим номером к большим

2)

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

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

Поздний срок наступл. cобытия – это наиболее поздний срок наступления события j, который не влияет на ранний срок окончания всего проекта в целом (критическое время).

Резерв времени – макс время, на которое можно задержать наступление события без увеличения раннего срока окончания проекта (= T поздн – T ранн)

Поздний срок последнего события n равен раннему сроку окончания проекта = максим длине пути из 1 до n. Этот путь называется критическим путем, а его длина – критическим временем.

3)Рассчитывают дополнительные показатели для руководства проекта:

- суммарный резерв времени (макс задержка работы без задержки срока выполнения всего проекта)

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

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

- независимый резерв

4) строим таблицу:

работа дуга продолжит Ранний срок: нач Ранний срок: оконч Поздний срок: нач Поздний срок: оконч Резервы

A (1,2) 5 0 5 2 7 2,0,0,2

B (1,3) 4 0 3 1 4 1,0,0,4

…N

5) Строится временная диаграмма выполнения работ

78.Универс. методы ИСО: ветвей и границ, динамич. программир. Отыскание мно-ва Парето.

Метод ветвей и границ – это универсальный метод, кот. Сводит решение исходной задачи к решению 2х и более ее подзадач. Базовой структурой метода явл. дерево поиска. Корень дерева соответствует исходной задаче. Процесс ветвления – создание подзадач для одной из родительских задач с добавлением 1 или более ограничений. Важно не потерять допустимые решения в процессе ветвления: объединение допустимых областей задач «сыновей» должно давать допустимую область их родителя.

Рассм. На примере задачи лин. программир.:

CXmax

AX<= b

a<=x<=b

xэZ

решили задачу и получили значение целевой фун-и Z* - это будет оценкой/границей

(чем ближе к Z* тем лучше)

Ветвимся: выбрасываем условие xэZ (x – целое) ветви: если решения x* оказались целыми – все, конец задачи – это и есть решения, если не целое: делим на 2 подзадачи: 1) X*<= целая часть X снизу 2) x*>= целая часть сверху и решаем 2 подзадачи. Из решений выбираем лучшее.

Одна из главных идей в методе ветвей и границ в том, чтобы не давать дереву поиска разрастаться путем «отсечении» бесперспективных ветвей, сравнивая рекордными решениями. Рекордное решение – лучшее из найденных, при котором значение целевой функции наилучшее (max/min). Рекорд – значение целевой ф-и с рекордными значениями. Если оценка для подзадачи меньше рекорда – ее можно сразу отсечь, т.к. в ней не будет решения лучше рекордного.

Метод динамического программирования Как и метод ветвей и границ, сводит решение исходной задачи к решению нескольких меньших подзадач. Отличие: нет оценок. Все подзадачи решаются точно.

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

Применение метода динамич. пр-я разнообразны, и не позволяют сформулировать общую задачу. Пример: задача о рюкзаке (наполнить рюкзак максим стоимости, но объем не должен превышать нек заданное число) – вычисляется по рекуррентной формуле F(b)=max (F(b-a)+c; Fb t-1)