Построение первоначального опорного плана

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

Cтраница 1

Опорный план, отвечающий рассматриваемому базису, оптимален, если все AV неотрицательны.  

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

Опорный план территории поселения - картографическое отображение фактически сложившейся градостроительной и экологической ситуаций на территории поселения.  

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

Пусть теперь первый опорный план найден. Существует ряд методов проверки координат вершины на оптимальность.  

Находят опорный план расширенной задачи.  

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

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

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

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

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

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

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

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

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

Пример

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

В первоначальный план включено завершение проекта за 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/день ).

Наибольшее распространение для нахождения начальных опорных планов получили:

Метод северо- западного угла и

Метод минимального элемента.

Метод северо-западного угла используют для нахождения произвольного опорного плана ТЗ. Основную идею метода рассмотрим на конкретном примере.

Пример 1. Условия ТЗ заданы транспортной таблицей (табл. 3.1).

Таблица 3.1

Требуется найти опорное решение (построить опорный план).

Решение. Будем заполнять таблицу 3.1 перевозками постепенно, начиная с левой верхней ячейки(1.1) (северо-западного угла).Будем рассуждать при этом следующим образом.

Пункт В 1 подал заявку на 18 единиц товара. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте А 1 , и запишем перевозку 18 в клетке (1.1). После этого заявка пункта В 1 удовлетворена, а в пункте А 1 осталось еще 30 единиц товара. Удовлетворим за счет них заявку пункта В 2 (27 единиц), запишем 27 единиц в клетке (1,2); оставшиеся 3 единицы пункта А 1 назначим пункту В 3 . В составе заявке пункта В 3 остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А 2 , чем его запас будет исчерпан, и еще 9 возьмем из пункта А 3 . Из оставшихся 18 единиц пункта А 3 12 выделим пункту В 4 ; оставшиеся 6 единиц назначим пункту В 5 , что вместе со всеми 20 единицами пункта А 4 покроет его заявку (табл. 3.2).

Таблица 3.2

На этом распределение запасов закончено. Каждый пункт назначения получил согласно своей заявке. Это выражается в том, что сумма перевозок в каждой строке равна запасу, а в столбце – заявку.

Таким образом, нами составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является не только допустимым, но и опорным решением ТЗ.

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию r = n + m – 1 = 8. Остальные клетки -- свободные, в них стоят нулевые перевозки, их число равно (n – 1)(m – 1) = 12.Значит, составленный план -- опорный и поставленная задача построения опорного плана решена.

Но является ли этот план оптимальным? Нет, так как при его совершенно не учитывались стоимости перевозок с i j . И даже, если мы стоимость этого плана перевозок

18 10 + 27 8 + 3 5 + 30 8 + 9 10 + 12 8 + 6 7 + 20 8 = 1039

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

плана с целью получения оптимального.

Пример 2. Особенности построения «вырожденного плана»

План, в котором некоторые из базисных перевозок оказываются равными нулю, называют «вырожденным»

Дана транспортная таблица (табл.3.3) Построить опорный план.

Решение. Применяя метод северо-западного угла, получим таблицу 3.3.

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

быть m + n -- 1 = 8, оказались равными нулю.

Отчего это произошло? При распределении запасов по пунктам назначения

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

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

В дальнейшем нам удобно будет всегда в транспортной таблице m + n -- 1 базисных клеток, хотя в некоторых из них, может быть, будут стоять и нулевые значения перевозок. Для этого можно ничтожно мало изменить запасы или

Таблица 3,3

Таблица 3.4

Таблица 3.5

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

Как перейти от вырожденного плана к невырожденному можно понять на примере таблиц 3.4 и 3.5. Изменим слегка запасы в первой строке и положим их равными 20 + ε . Кроме того, в третьей строке проставим запасы 25 + ε. Чтобы «свести баланс» , в четвертой строке ставим запасы 20 -- 2 ε (табл. 3,5). Для этой таблицы строим опорный план методом северо-западного угла.

В табл. 3,5 уже содержится столько базисных переменных, сколько требуется:

m + n -- 1 = 8. В дальнейшем после оптимизации плана, можно будет положить

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

транспортной задачи и является вариантом метода северо-западного угла, учитывающего специфику матрицы С = c i j . В отличие от метода северо-западного угла данный метод позволяет сразу получит достаточно экономичный план, сокращая количество итераций.

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