Графический метод.

ГМ состоит из двух этапов.

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. Если полученное решение не является оптимальным, то необходимо перейти к следующей вершине (опорному решению) Переход осуществляется по определенному правилу по которому: только одна изи базисных переменных должна перейти в свободную и только одна из свободных перейти в базисную.

Алгебра симплекс метода.

Система основана на понятии приведенной стоимости ,принятом в бухучете.

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

Такие системы не принимают во внимание параметр времени в управлении.

Пример

Фирма, занимающаяся высокими технологиями , внедряет проект НИОКР .

В первоначальный план включено завершение проекта за 10 месяцев со стоимостью примерно в $200 000 в месяц при общей стоимости в $2 млн .

Через пять месяцев после начала работ топ-менеджмент решает оценить статус проекта. В наличии следующая информация:

1. фактические затраты в первые пять месяцев составляют $1,3 млн ;
2. запланированные сметные затраты на пять месяцев составляют $1 млн .

Менеджмент может прийти к выводу, что затраты превысили плановые показатели на $300 000 .Это может быть, а может и не быть правильным выводом.

Возможно, ход работ опережает график, и $300 000 - это зарплата за труд с опережением графика. А возможно, есть и превышение затрат, и отставание от графика. То есть, данные не раскрывают ситуацию полностью.

Используя тот же пример с другими исходными данными, мы опять увидим, что данные не могут дать нам адекватного вывода о состоянии проекта за 5 месяцев:

• фактические затраты за первые пять месяцев составили $800 000 ;
• запланированные затраты за первые пять месяцев - $1 млн .

Эти данные могут привести к выводу, что проект обходится дешевле планируемого на $200 000 .

Так ли это? Если проект отстает от графика, то $200 000 могут обозначать запланированные работы, к которым еще не приступили. Может быть, что проект и отстает от графика, и затраты превышены.

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

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

Краткое изложение интегрированной системы стоимость/график

Тщательное выполнение пяти шагов обеспечивает целостность системы стоимость/график.

Шаги 1-3 выполняются на стадии планирования.

Шаги 4 и 5 последовательно выполняются на стадии выполнения проекта.

1. Определите работу. Сюда входит разработка документов, содержащих следующую информацию:
   • масштаб;
   • наборы работ;
   • подразделения;
   • ресурсы;
   • сметы для каждого набора работ.
2. Разработайте график работы и использования ресурсов.
   • распределите наборы работ по времени;
   • распределите ресурсы по операциям.
3. Разработайте смету , распределенную по времени, с использованием наборов работ, включенных в операции.

   Кумулятивные значения этих смет станут основой и будут называться сметной стоимостью работ (BCWS ).

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

4. На уровне наборов работы соберите все фактические затраты выполненных работ.

   Эти затраты будут называться фактической стоимостью выполненной работы (ACWP ).

   Сложите сметные величины фактически выполненных работ. Они будут называться приведенной стоимостью или сметной стоимостью выполненных работ (BCWP ).

5. Просчитайте отклонение по расписанию (SV = BCWP - BCWS ) и отклонение по стоимости (CV = BCWP - ACWP ).

На рис. 6.3 представлена схема интегрированной системы сбора и анализа информации.

Рис. 6.3.

Разработка опорного плана проекта

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

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

Распределенные по времени сметы добавляются по временной шкале проекта для создания опорного плана.

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

На рис. 6.4 показаны отношения между данными, использующимися для создания опорного плана.

Какие затраты включены в опорный план!

Опорный план BCWS - это сумма счетов издержек, а каждый счет издержек - это сумма издержек наборов работ, входящих в этот счет.

Четыре типа затрат обычно включают в опорный план - затраты на труд и затраты на оборудование, затраты на материалы и затраты, возникающие в ходе работы над проектом (LOE ).

LOE обычно закладывают в прямые накладные расходы по проекту.

Такие операции, как административная поддержка, компьютерная поддержка, юридические операции, PR и т.д. существуют для пакета работы, сегмента проекта, продолжительности проекта и представляют собой прямые проектные накладные расходы.

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

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

Затраты LOE также можно привязать к "подвешенной" операции, покрывающей сегмент проекта. Когда затраты LOE привязаны к пакетам работ, не имеющим измеряемых показателей, их затраты вносят в смету как величину на единицу времени (например, $200/день ).

Книга: Управление проектами - конспект лекций (УДПСУ)

2. Опорный план проекта

1. Система оценки и контроля в проекте

2. Опорный план проекта

4. Прогнозирование окончательной стоимости проекта

6. Мониторинг обновления строительства.

8. Предварительная и независимая экспертиза проектов

9. Постаудит проекта

10. Экспертиза государственных инвестиционных программ

2. Опорный план проекта

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

Опорный план сметной стоимости работ (BCWS) - это сумма счетов затрат, а каждый счет затрат - это сумма расходов наборов (пакетов) работ, что входят в этот счет. В опорный план включают три типа расходов - затраты на труд, затраты на оборудование и затраты на материалы. Расходы, возникающие в ходе работы над проектом (LOE) обычно закладывают в прямые накладные расходы по проекту. LOE включает такие операции, как административная поддержка, компьютерная поддержка, юридические операции, PR и т.д. Они... существуют для пакета работы, сегмента проекта, продолжительности проекта и представляют собой прямые проектные накладные расходы. Конечно отделяют расходы LOE от затрат на труд, материалы, оборудование и вычисляют для них отдельные колебания. Пакеты работ LOE должны составлять очень маленькую долю проектных расходов (от 1% до 10%).

Правила списания затрат в опорном плане

Главной причиной разработки опорного плана является необходимость контроля за ходом работ и учета движения наличности. Следовательно, необходимо объединить опорный план с системой измерения и оценки хода работ. Расходы нужно распределять по времени, согласно прогноза их возникновения. На практике интеграция достигается с использованием тех же правил приписывания затрат к опорному плану, что и для измерения хода работ. Ниже приводятся три правила, которые наиболее часто используются на практике. Первые два применяются для снижения накладных расходов на сбор подробной информации.

1. Правило 0/100%. За этим правилом всю стоимость за выполненные работы списывают, когда работы полностью завершены. Следовательно, 100% сметы освоено, когда объем работ вполне совершенный. Это правило используют для работ с очень короткой продолжительностью.

2. Правило 50/50. Этот подход позволяет списать 50% стоимости сметы работ, когда работа начата, и 50% - по завершении. Это правило используют применительно к наборам работ с короткой продолжительностью и небольшими общими затратами.

3. Правило процента выполнения. Этот метод наиболее часто используется управляющими на практике. По этому правилу лучшим методом списания затрат в опорном плане является проведение частых проверок на протяжении всего периода работ и установление процента их завершения в денежных единицах. Например, завершенные единицы могут быть использованы для обозначения основных затрат и, позже, для измерения хода работ. Единицами могут быть законченные чертежи, кубические метры залитого бетона, законченная модель и т.д. Такой подход добавляет “объективность” часто используемых подходов “субъективных мнений”. При измерении процента выполнения на стадии контроля проекта конечно процент выполнения ограничивают 80% до тех пор, пока пакет работы не будет завершен на 100%.

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

Эти правила используются для интеграции основного плана сметы с процедурой контроля над ходом выполнения проекта.

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

В основном этот метод измерения степени завершенности сосредоточен на двух ключевых оценках:

1. Сравнении приведенной стоимости с ожидаемой по графику стоимостью.

2. Сравнении приведенной стоимости с фактическими затратами.

Оценка текущего статуса проекта с использованием приведенной стоимости системы стоимость/график требует трех элементов данных - BCWS, БСВР и ACWP. На основе этих данных рассчитывают SV и CV, как показано в словаре. Положительное отклонение указывает на желаемое состояние, отрицательное - говорит о проблемах.

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

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

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

Рис. 2 - это вариант построения графика сметной стоимости работ на отчетный период. Обратите внимание, график фокусуе внимание на том, чего нужно достичь, и на любых благоприятных и неблагоприятных тенденциях. Оценка “сегодня” обозначает дату отчета (оценка 25) о том, на какой стадии находится проект. В связи с тем, что эта система иерархическая, подобные графики можно составить для разных уровней управления. Верхняя линия обозначает фактические расходы (ACWP) на работу над проектом на данный момент. Средняя линия обозначает опорный план (BCWS) и заканчивается на запланированной по графику продолжительности проекта (45). Нижняя линия обозначает сметную стоимость фактически выполненной работы на конкретную дату, на сегодня (БСВР) или приведенную стоимость. Пунктирная линия, продолжающая линию фактических затрат от отчетной даты до новой прогнозируемой даты завершения, представляет собой пересмотренные цифры ожидаемых фактических затрат; то есть дополнительная информация предполагает, что затраты при завершении проекта будут отличаться от запланированных. Обратите внимание, продолжительность проекта была увеличена и отклонение при завершении (VAC) негативные (ВАС - ЕАС).

В другой интерпретации данного графика используются проценты. В конце периода 25 по плану должно было быть выполнено 75% работы. В конце периода 25 фактически выполнено 50%. Фактическая стоимость выполненной работы на данный момент составляет $340, или 85% от общей сметы проекта. Из графика видно, что можно прогнозировать, что проект превысит стоимость на 12% и на 5 единиц отстанет от намеченных сроков. Текущий статус проекта показывает, что отклонение по стоимости (CV) превысит смету на $140 (БСВР - ACWP = 200 - 340 = -140). Отклонение графика срокам (SV) является отрицательной величиной $100 (БСВР - BCWS = 200 - 300 = - 100), что говорит об отставании проекта от сроков.

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

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

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

Поскольку ограничения в этой задаче образуют систему уравнений относительно переменных решения, можно было бы попытаться решить эту систему, чтобы найти значения переменных. Но переменных решения в нашей задаче 6, а независимых уравнений для их решения только 4. Можно произвольно положить значение двух каких -нибудь переменных решения равными 0 (например, Хп=0 и Х]2=0), тогда остальные переменные решения могут быть однозначно определены из системы уравнений, образованной ограничениями. Получившийся план перевозок, разумеется, необязательно будет оптимальным, но он обязательно является допустимым, поскольку удовлетворяет всем ограничениям.

Такой план называется опорным. От множества других допустимых планов он отличается тем, что число ненулевых переменных решения (ненулевых перевозок) точно равно количеству независимых ограничений в транспортной задаче или, иначе, сумме числа поставщиков и потребителей минус 1.

В нашей задаче число ненулевых перевозок в опорном плане равно

2 (количество поставщиков) + 3 (количество потребителей) -1=4.

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

Если, например, т = 10, а п = 20, то количество переменных будет 200, а количество ненулевых переменных в опорном плане - только 29.

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

Разумеется, опорных планов может быть много. В нашем примере нетрудно пересчитать, что существует 15 различных способов присвоить нули двум переменным из шести (т.е. имеется 15 опорных планов). В случае когда т = 10, п = 20, число различных опорных планов будет выражаться огромным числом 7,18*1034. Таким образом, о том, чтобы перебрать все возможные опорные планы и выбрать среди них оптимальный, в общем случае транспортной задачи, разумеется, не может быть и речи. Однако возможность осуществлять поиск только среди опорных планов все равносильно упрощает задачу по сравнению с общей задачей линейного программирования.

Опорным называется такой план, в котором количество ненулевых перевозок равно сумме количеств поставщиков и потребителей минус единица.

Оптимальный план перевозок следует искать только среди множества опорных планов.

Решение транспортной задачи, как и всякой задачи линейного программирования, начинается с нахождения опорного решения, или, как мы будем говорить, опорного плана. В отличие от общего случая ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует. Действительно, из чисто физических соображений ясно, что хоть какой-то допустимый план существовать должен. Среди допустимых планов непременно имеется оптимальный (может быть, не один), потому что линейная функция 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 уже содержится столько базисных переменных, сколько требуется: . В дальнейшем, после оптимизации плана, можно будет положить .