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

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

Правило: количество базисных (заполненных) клеток в первоначальном плане ВСЕГДА должно быть равно m + n - 1, где m - количество поставщиков, n - количество потребителей транспортной задачи.

Что же делать, если количество заполненных ячеек опорного плана меньше необходимого?

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

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

Вырожденность опорного решения транспортной задачи - пример 1:

Построить первоначальный план для следующей ситуации:

Количество поставщиков (складов) = 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. Условие невырожденности выполнено!

Вырожденность опорного решения транспортной задачи - пример 2:

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

Задача закрытая:

12 + 10 + 14 = 36

4 + 18 + 8 + 6 = 36

Первоначальный план получим методом северо - угла.

Начнем с заполнения ячейки (1;1).

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

Все 10 единиц груза направляем во второй магазин, потребности которого на данный момент равны 18 - 8 = 10. Заметим, что на данном шаге одновременно удовлетворяются потребности второго магазина и закончились запасы второго склада. Произошла потеря одного базисного значения.

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

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

Закончим заполнение таблицы:

Получили первоначальный план методом северо - западного угла. Количество базисных ячеек равно 4 + 3 - 1 = 6.

Можно приступать к решению задачи методом потенциалов!

Предположим, что каноническая задача ЛП имеет не совсем специальный вид, а к примеру, правые части уравнений системы ограничений могут быть отрицательны.
Этот случай возникает при решении задачи о рационе . Канонический вид задачи выглядит так:

F = 20х 1 + 20х 2 + 10х 3 → min.

Запишем задачу в симплекс-таблицу (табл. 1).

Таблица 1

Базисное решение, соответствующее базису {x 4 , x 5 , x 6 } и равное (0; 0; 0; -33; 23; -12), не является допустимым ввиду отрицательности х 4 < 0, x 5 < 0, x 6 < 0.

Сформулируем правило нахождения допустимого опорного плана .
Если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2-5 .
Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. . Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом.
Проведем этот шаг для задачи о рационе. В качестве разрешающей строки табл. 1 нужно выбрать первую. А разрешающим элементом выберем, к примеру, элемент -4.

Таблица 2

базисные				свободные

Заметим, что переменная х 1 вошла в базис вместо х 4 , все вычисления осуществлялись по правилу 2-5. В правом столбце еще остался отрицательный элемент, воспользуемся правилом еще раз. Строка переменной х 6 - разрешающая, а в качестве разрешающего элемента возьмем, к примеру, 3 / 2 , здесь есть некоторая возможность выбора.

Таблица 2

базисные				свободные

Полученный базисный план х * = (х 1 , х 2 , х 3, х 4 , х 5 , х 6) = (7, 0, 5/2, 0, 1/2, 0) является допустимым и, к тому же, оказывается оптимальным, т.к. в индексной строке нет отрицательных элементов. Оптимальное значение целевой функции равно F* = 165. Действительно,
F = 20х 1 + 20х 2 + 10х 3 = 20 · 7 + 0 + 10· = 140 + 25 = 165.

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

Решение задачи о плане симплекс-методом

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

Таблица 3

Составим математическую модель. Пусть х 1 , х 2 , х 3 , х 4 - количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:

F = 3x 1 + 5x 2 + 4x 3 + 5x 4 → max.

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

Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х 5 , х 6 , х 7 в каждое из неравенств.
Очевидно, что, если первого ресурса необходимо для производства плановой продукции 5х 1 + 0,4х 2 + 2х 3 + 0,5х 4 , то х 5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х 6 и х 7 . Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Запишем задачу в таблицу 4, предварительно выписав ее каноническую форму:

I этап . Это задача специального вида, базис составляют переменные { х 5 , х 6 , х 7 }, правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) - опорный. Он соответствует симплекс-таблице.

Таблица 4

базисные					свободные

II этап . Проверим план на оптимальность. Так как в индексной F -строке есть отрицательные элементы, то план неоптимален, переходим к III этапу.

III этап . Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, но могли бы выбрать и второй, т.к. в обоих (-5). Остановившись на четвертом, выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум соотношений . С разрешающим элементом 1 проводим преобразование таблицы по правилам 2-5 (табл. 5).

Таблица 5

Полученный план опять неоптимален, т.к. в F -строке есть отрицательный элемент -5 . этот столбец разрешающий.

В качестве разрешающего элемента выбираем 5, т.к. .

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

Таблица 6

базисные					свободные

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

IV этап . Базисные переменные {x 5 , x 2 , x 4 } принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х * = (0, 40, 0, 100, 334, 0, 0) и F * = 700. Действительно, F = 3х 1 + 4х 3 + 5х 2 + 5х 4 = 5 · 40 + 5 · 100 = 700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV - вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х 5 = 334, х 6 = 0, х 7 = 0).

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

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

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

Пример

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

В первоначальный план включено завершение проекта за 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 показаны отношения между данными, использующимися для создания опорного плана.

Рис. 6.4.

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

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

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

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

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

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

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

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