Основные предпосылки метода динамического программирования. Понятие динамического программирования. Самый дешёвый путь
ГМ состоит из двух этапов.
2) Среди всех решений необходимо найти такое решение при котором Z достигает своего либо max или min.
Grad показывает наискорейшее возрастание функции. (С – коэффициент) (линии уровня)
1. задача имеет единственное решение.
2. Задача имеет – бесконечно много решений.
3. Задача не имеет решений а) нет ОДР б) в случаи когда zmax - ф-ия не ограниченной сверху линией уровня и наоборот.
Графический метод можно применять если имеется только две переменные или задача может быть приведена с помощью эквивалентных преобразований к задаче с двумя переменными.
Свойства допустимых планов.
1) Выпуклая линейная комбинация точек. х1 х2 …хk сумма вида α1х1+ α2х2+ ...+ αkxk , где αi =1 (αi>=0 αi – коэффициент линейной комбинации).
2) Выпуклым множеством называется такое множество т. Д на плоскости, когда вместе с любыми двумя точками Х1є Д; Х2 є Д принадлежащим множеству Д. Ему принадлежит и их выпуклая Л.К. х=tx1+(1-t)x2 є Д 0<=t<=1
3) Крайняя точка – т.Х выпуклого множества называется крайней если она не может быть представлена в виде выпуклой Л.К. любых двух точек этого множества (n=2)
Опорное решение – это допустимое базисное решение имеющая не более чем m положительных элементов, и причем векторы столбца матрицы соответственно положительны координатам вектора линейны независимы.
Свойства допустимых планов.
Теорема №1
Множество допустимых планов З.Л.П. выпукла если оно не пусто.
Дано: Д- не является пустым множеством – ОДР
Доказать Ж Д- выпуклое множество.
Х1 єД; Х2 єД,то оно удовлетворяет системе ограничений в З.Л.П. Z=cx->max Ax=b X>=0
Ax1=b 0<=t<=1
Ax2=b (1-t) => tAx1+(1-t)Ax2=bt+b(1-t) = A=b
x1; x2>=0 => x>=0
Ax=b X- решение задачи.
Х = tx1+(1-t)x2 0<=t<=1, согласно опр. Имеем выпуклое множество – Д, т.к. с любыми двумя точками ему принадлежит и их выпуклая Л.К.
Теорема № 2
Если целевая функция имеет максимум на выпуклом многограннике решений, то это максимум достигается в вершине многогранника..
Дано: Zmax->X 0 Док-ть X 0- вершина.
Док-во: Дан многогранник. А,В,С,Д,Е – вершины. (Док-во проведем от противного)
X 0 – не вершина, тогда согласно опр. Крайней точки, X 0 – не крайняя точка, и может быть представлена в виде выпуклой Л.К. точек хi є ОДР
C X 0 >Cxi (т.к. С X 0 ->max)
X 0 = αiXi αi=1 αi>=0
Найдем значение функции Z=C X 0 =CαiXi=αiCXi<αiCX 0 =CX 0 αi=CX 0
В каждом слагаемом сменим Xi на Х 0
СХ 0 Теорема №3 Об альтернативном оптимуме. Если целвевая функция достигает своего оптимального значения в нескольких вершинах (т)
х1 х2 хk , то она достигает оптимального значения в их выпуклой линейной комбинации.
Дано: Док-ть: х= αiXi Xi , i:=1,k αi=1 αi>=0 CX=d Найдем Z=СХ=CαiXi=αiCXi=αid=dαi=d Теорема № 4 Вектор Х является опорным решением тогда и только тогда, если он является вершиной многогранника. Если переменных n>3 то говорят гиперплоскость, положение точек в т – мерном пространстве.
ИДЕЯ СИМПЛЕКС МЕТОДА. Симплекс метод является универсальным. Симплекс метод – аналитический метод. 1. Находятся первоначальное, опорное решение. А)система ограничений должна быть записана в виде равенств (каноническая форма) Б)Преобразовать что бы bi >=0 i=1,m С)Привести систему к единичному базисному виду с неотрицательной правой частью. Поэтому за разрешающий элемент выбирается строго положительный элемент. Д)Приравниваем свободные к 0 , получаем первоначальное базисное неотрицательное решение, которое является опорным решением данной задачи и соответствует вершине. 2. Рассматривая функцию цели выясняем является ли полученное решение оптимальным. 3. Если полученное решение не является оптимальным, то необходимо перейти к следующей вершине (опорному решению) Переход осуществляется по определенному правилу по которому: только одна изи базисных переменных должна перейти в свободную и только одна из свободных перейти в базисную. Алгебра симплекс метода. На начальном этапе решения транспортной задачи необходимо получить первоначальный опорный план. Как это сделать, подробно описано в статье Как решить транспортную задачу
. После получения опорного плана необходимо проверить его на невырожденность. Что же делать, если количество заполненных ячеек опорного плана меньше необходимого? На некотором шаге получения первоначального плана может сложиться ситуация, когда одновременно удовлетворяются потребности магазина и опустошается склад. В этом случае происходит "потеря" базисной клетки. Это приводит к тому, что система определения потенциалов имеет не единственное решение. Чтобы обойти эту ситуацию, добавим к базисным ячейкам недостающее количество ячеек с нулевыми значениями. Нулевое значение поставим в клетку, стоящую рядом с базисной клеткой, которая обусловила "пропажу" базисного значения. Построить первоначальный план для следующей ситуации: Количество поставщиков (складов) = 3, количество потребителей (магазинов) = 4 60 + 30 + 40 = 40 + 50 + 10 + 30 - спрос равен предложению - задача закрытая.
Методом северо - западного угла получим опорный план. Начинаем с самой верхней левой ячейки. Потребности первого магазина выполнены полностью, но на складе еще остался груз. Заполняем дальше. Остатки груза с первого склада 60 - 40 = 20 перевозим в магазин второй. При этом, первый склад опустел, но потребности магазина не выполнены полностью. Переходим ко второму складу. Все 30 единиц груза переносим в магазин второй, потребности которого совпали с предложением склада 50 - 20 = 30. При данном распределении склад опустошается и потребности второго магазина выполняются полностью. Происходит потеря базисной клетки!
В данном случае необходимо к базисным клеткам добавить клетку с нулевым значением, расположенную рядом с только что заполненной, которая обусловила потерю. Продолжим. С третьего склада направим 10 единиц груза в магазин 4 для полного выполнения его потребностей. На 3-м складе остается 40 - 10 = 30 единиц груза, которые перенесем в последний магазин. Опорный план составлен. Количество базисных ячеек равно 6 = 3 + 4 - 1. Условие невырожденности выполнено! Три торговых склада поставляют продукцию в четыре магазина. Наличие продукции на складах и потребности магазинов приведены в следующей таблице. Построим первоначальный план транспортной задачи: Задача закрытая: 12 + 10 + 14 = 36 4 + 18 + 8 + 6 = 36 Первоначальный план получим методом северо - угла. Начнем с заполнения ячейки (1;1). Запасы первого склада распределили по первому и второму магазину, при этом запасы склада исчерпаны, а потребность второго магазина не удовлетворена. Переходим ко второму складу. Все 10 единиц груза направляем во второй магазин, потребности которого на данный момент равны 18 - 8 = 10. Заметим, что на данном шаге одновременно удовлетворяются потребности второго магазина и закончились запасы второго склада. Произошла потеря одного базисного значения. Ничего страшного, если вы упустите этот момент при получении опорного плана. Главное не забыть проверить условие невырожденности перед проверкой плана на оптимальность. Проанализировав уже полученное распределение груза, нетрудно найти момент, когда была "потеряна" базисная клетка. Чтобы компенсировать потерю, мы должны ввести нулевую ячейку, рядом с заполненной. Можем поместить ее правее, левее или ниже значения 10. Закончим заполнение таблицы: Получили первоначальный план методом северо - западного угла. Количество базисных ячеек равно 4 + 3 - 1 = 6. Можно приступать к решению задачи методом потенциалов! Система основана на понятии приведенной стоимости
,принятом в бухучете. Системы только лишь сравнивающие факт со сметой не в состоянии измерить, что действительно удалось сделать на затраченные средства. Такие системы не принимают во внимание параметр времени
в управлении. Фирма, занимающаяся высокими технологиями
, внедряет проект НИОКР
. В первоначальный план включено завершение проекта за 10 месяцев со стоимостью примерно в $200 000
в месяц при общей стоимости в $2 млн
. Через пять месяцев после начала работ топ-менеджмент решает оценить статус проекта. В наличии следующая информация: Менеджмент может прийти к выводу, что затраты превысили плановые показатели на $300 000
.Это может быть, а может и не быть правильным выводом. Возможно, ход работ опережает график, и $300 000
- это зарплата за труд с опережением графика. А возможно, есть и превышение затрат, и отставание от графика. То есть, данные не раскрывают ситуацию полностью. Используя тот же пример с другими исходными данными, мы опять увидим, что данные не могут дать нам адекватного вывода о состоянии проекта за 5 месяцев: Эти данные могут привести к выводу, что проект обходится дешевле планируемого на $200 000
. Так ли это? Если проект отстает от графика, то $200 000
могут обозначать запланированные работы, к которым еще не приступили. Может быть, что проект и отстает от графика, и затраты превышены. Из этих двух примеров видно, почему системы, использующие только показатели фактических и запланированных затрат, могут ввести менеджмент и заказчика в заблуждение при оценке хода и выполнения работ. Приведенная стоимость
помогает преодолеть описанные проблемы через отслеживание графиков и сметных расходов во времени. Тщательное выполнение пяти шагов обеспечивает целостность системы
стоимость/график. Шаги 1-3 выполняются на стадии планирования. Шаги 4 и 5 последовательно выполняются на стадии выполнения проекта. Кумулятивные значения этих смет станут основой и будут называться сметной стоимостью работ
(BCWS
). Сумма должна быть равной сметным величинам для всех пакетов работ в счете издержек. Эти затраты будут называться фактической стоимостью выполненной работы
(ACWP
). Сложите сметные величины фактически выполненных работ. Они будут называться приведенной стоимостью
или сметной стоимостью выполненных работ
(BCWP
). На рис. 6.3 представлена схема интегрированной системы сбора и анализа информации.
Опорный план - это конкретный документ-обязательство; это запланированная стоимость и ожидаемые сроки выполнения работ, с которыми сравнивают фактическую стоимость
и фактические сроки выполнения. Расположение наборов работ по операциям в сетевом графике
, как правило, указывает время начала выполнения этих наборов; оно также распределяет по времени сметы
затрат, привязанных к наборам работ. Распределенные по времени сметы
добавляются по временной шкале проекта для создания опорного плана. Кумулятивная сумма всех этих распределенных по времени смет должна равняться сумме всех пакетов работы, определенных в счете издержек. На рис. 6.4 показаны отношения между данными, использующимися для создания опорного плана. Опорный план BCWS
- это сумма счетов издержек, а каждый счет издержек - это сумма издержек наборов работ, входящих в этот счет. Четыре типа затрат обычно включают в опорный план - затраты на труд и затраты на оборудование, затраты на материалы и затраты, возникающие в ходе работы над проектом (LOE
). LOE обычно закладывают в прямые накладные расходы по проекту. Такие операции, как административная поддержка, компьютерная поддержка, юридические операции, PR и т.д. существуют для пакета работы, сегмента проекта, продолжительности проекта и представляют собой прямые проектные накладные расходы. Обычно отделяют затраты LOE от затрат на труд, материалы, оборудование и высчитывают для них отдельные колебания. Возможность контролировать затраты LOE
минимальна, поэтому их включают в прямые проектные накладные расходы. Затраты LOE
также можно привязать к "подвешенной" операции, покрывающей сегмент проекта. Когда затраты LOE привязаны к пакетам работ, не имеющим измеряемых показателей, их затраты вносят в смету
как величину на единицу времени (например, $200/день
). Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения, или, как мы будем говорить, опорного плана. В отличие от общего случая ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует. Действительно, из чисто физических соображений ясно, что хоть какой-то допустимый план существовать должен. Среди допустимых планов непременно имеется оптимальный (может быть, не один), потому что линейная функция L - стоимость перевозок заведомо неотрицательна (ограничена снизу нулем). В данном параграфе мы покажем, как построить опорный план. Для этого существуют различные способы, из которых мы остановимся на простейшем, так называемом «способе северо-западного угла». Пояснить его проще всего будет на конкретном примере. Пример 1. Условия ТЗ заданы транспортной таблицей (см. табл. 10.1). Требуется найти опорное решение ТЗ (построить опорный план). Решение. Перепишем табл. 10.1 и будем заполнять ее перевозками постепенно, начиная с левой верхней ячейки (1,1) («северо-западного угла» таблицы). Будем рассуждать при этом следующим образом. Пункт подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте и запишем перевозку 18 в клетке (1,1). После этого заявка пункта й, удовлетворена, а в пункте осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта назначим пункту . В составе заявки пункта остались неудовлетворенными 39 единиц. Таблица 10.1 Из них 30 покроем за счет пункта , чем его запас будет исчерпан, и еще 9 возьмем из пункта . Из оставшихся 18 единиц пункта выделим пункту оставшиеся 6 единиц назначим пункту что вместе со всеми 20 единицами пункта покроет его заявку (см. табл. 10.2). На этом распределение запасов закончено: каждый пункт назначения получил груз согласно своей заявке. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является не только допустимым, но и опорным решением транспортной задачи. Таблица 10.2 Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию Остальные клетки - свободные (пустые), в них стоят ненулевые перевозки, их число равно Значит, наш план - опорный и поставленная задача построения опорного плана решена. Возникает вопрос: а является ли этот план оптимальным по стоимости? Разумеется, нет! Ведь при его построении мы совсем не учитывали стоимостей перевозок Естественно, план не получился оптимальным. Действительно, стоимость этого плана, которая найдется, если умножить каждую перевозку на соответствующую стоимость, равна . Таблица 10.3 Попробуем улучшить этот план, перенеся, например, 18 единиц из клетки (1,1) в клетку (2,1) и, чтобы не нарушить баланса, перенеся те же 18 единиц из клетки (2,3) в клетку (1,3). Получим новый план, приведенный в табл. 10.3. Нетрудно убедиться, что стоимость нового плана равна т. е. на 126 единиц меньше стоимости плана, приведенного в табл. 10.3. Таким образом, за счет циклической перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана. На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации плана перевозок. Остановимся на одной особенности плана перевозок, которая может встретиться как при построении опорного плана, так и при его улучшении. Речь идет о так называемом «вырожденном» плане, в котором некоторые из базисных перевозок оказываются равными нулю. Рассмотрим конкретный пример возникновения вырожденного плана. Пример 2. Дана транспортная таблица (без стоимостей перевозок, так как речь идет только о построении опорного плана) - см. табл. 10.4. Таблица 10.4 Таблица 10.5 Таблица 10.6 Составить опорный план перевозок. Решение. Применяя способ северо-западного угла, получим табл. 10.5. Опорный план составлен. Особенностью его является то, что в нем только шесть, а не восемь отличных от нуля перевозок. Значит, некоторые из базисных перевозок, которых должно быть оказались равными нулю. Нетрудно заметить, отчего это произошло: при распределении запасов по пунктам назначения в некоторых случаях остатки оказывались равными нулю и в соответствующую клетку не попадали. Такие случаи «вырождения» могут возникать не только при составлении опорного плана, но и при его преобразовании, оптимизации. В дальнейшем нам удобно будет всегда иметь в транспортной таблице базисных клеток, хотя в некоторых из них, может быть, будут стоять и нулевые значения перевозок. Для этого можно ничтожно мало изменить запасы или заявки, так чтобы общий баланс не нарушился, а лишние, «промежуточные» балансы уничтожились. Достаточно в нужных местах изменить запасы или заявки, например, на величину , а после нахождения оптимального решения положить Покажем, как перейти от вырожденного плана к невырожденному на примере табл. 10.5. Изменим слегка запасы в первой строке и положим их равными . Кроме того, в третьей строке проставим запасы . Чтобы «свести баланс», в четвертой строке ставим запасы 20 - 2е (см. табл. 10.6). Для этой таблицы строим опорный план способом северо-западного угла. В табл. 10.6 уже содержится столько базисных переменных, сколько требуется: . В дальнейшем, после оптимизации плана, можно будет положить .Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество поставщиков, n - количество потребителей транспортной задачи.
Вырожденность опорного решения транспортной задачи - пример 1:
Вырожденность опорного решения транспортной задачи - пример 2:
Пример
Краткое изложение интегрированной системы стоимость/график
Рис.
6.3.
Разработка опорного плана проекта
Рис.
6.4.
Какие затраты включены в опорный план!
