Метод северо-западного угла
Выполнение начинается с верхней левой ячейки (северо-западного угла) транспортной таблицы, т.е. с переменной х11.
Шаг 1 Переменной х11 присваивается максимальное значение, допускаемое ограничениями на спрос и предложение.
Шаг 2 Вычеркивается строка (или столбец) с полностью реализованным предложением (с удовлетворенным спросом). Это означает, что в вычеркнутой строке (столбце) мы не будем присваивать значения остальным переменным (кроме переменной, определенной на первом шаге). Если одновременно удовлетворяется спрос и предложение, вычеркивается только строка или только столбец.
Шаг 3 Если не вычеркнута только одна строка или только один столбец, процесс останавливается. В противном случае переходим к ячейке справа, если вычеркнут столбец, или к нижележащей ячейке, если вычеркнута строка. Затем возвращаемся к первому шагу.
Если применить описанную процедуру к примеру 6.1, получим начальное базисное решение, показанное в таблице 6.2. В этой таблице стрелками показана последовательность определения базисных переменных.
Таблица 6.2
| мельницы | 1 | 2 | 3 | 4 | предло- | ||||||
| элеваторы | жение | ||||||||||
| 1 | 10 | 2 | 20 | 11 | |||||||
  5
|   10
| 15 | |||||||||
| 2 | 12 | 7 | 9 | 20 | |||||||
  5
|   15
|   5
| 25 | ||||||||
| 3 | 4 | 14 | 16 | 18 | |||||||
 10
| 10 | ||||||||||
| Спрос | 5 | 15 | 15 | 15 | 50 | ||||||
|
| |||||||||||
Остальные х ij =0. Суммарная стоимость перевозок равна
f=5*10+10*2+5*7+15*9+5*20+10*18=520.
Метод минимального элемента
Данный метод находит лучшее начальное решение, чем метод северо-западного угла, поскольку выбирает переменные, которым соответствуют наименьшие стоимости. Сначала по всей транспортной таблице ведется поиск ячейки с наименьшей стоимостью перевозок. Затем переменной в этой ячейке присваивается наибольшее значение, допускаемое ограничениями на спрос и предложение. (Если таких переменных несколько, то выбор произволен). Далее вычеркивается соответствующий столбец или строка и соответствующим образом корректируются значения спроса и предложений. Если одновременно выполняются ограничения по спросу и предложению, вычеркивается или строка, или столбец (точно так же как в методе северо-западного угла). Затем просматриваются невычеркнутые ячейки, и выбирается новая ячейка с минимальной стоимостью. Описанный процесс продолжается до тех пор, пока не останется лишь одна невычеркнутая строка или столбец.
Применим метод к нашему примеру 6.1.
1 Ячейка (1,2) имеет наименьшую стоимость (=2). Наибольшее значение, которое можно присвоить переменной х12, равно 15. В этом случае удовлетворяются ограничения, соответствующие первой строке и второму столбцу. Вычеркиваем второй столбец, предложение первой строки и спрос второго столбца принимают нулевые значения.
2 Следующей ячейкой с наименьшей стоимостью в незачеркнутой части таблицы будет ячейка (3,1). Присвоим переменной х31 значение 5 и вычеркнем первый столбец. Ограничение по предложению, соответствующей третьей строке, станет равным 10-5=5.
3 Продолжим процедуру, последовательно присваиваем переменной х23 значение 15, переменной х14 – значение 0; далее находим х34=5 и х24=10.
Процесс поиска начального решения представлен в таблице 6.3. Стрелками показана последовательность присвоения переменным значения.
Таблица 6.3
| мельницы | 1 | 2 | 3 | 4 | предло- | ||||||
| элеваторы | жение | ||||||||||
| 1 | 10 | 2 | 20 | 11 | |||||||
|  15
| 
|   0
| 15 | |||||||
| 2 | 12 | 7 | 9 | 20 | |||||||
|  15
|   10
| 25 | ||||||||
| 3 | 4 | 14 | 16 | 
| 18 | ||||||
 5
|  5
| 10 | |||||||||
| Спрос | 5 | 15 | 15 | 15 | 50 | ||||||
|
| |||||||||||
Соответствующее значение целевой функции равно
f=15*2+5*4+15*9+0*11+5*18+10*2 0=475.
Начальное решение, полученное методом минимального элемента, меньше, чем методом северо-западного угла.
Метод потенциалов
После определения начального решения с помощью одного из методов, описанных выше, применяется алгоритм, позволяющий найти оптимальное решение транспортной задачи.
Шаг 1 На основе симплексного условия оптимальности среди текущего множества небазисных переменных определяется вводимая в базис переменная, которая улучшит значение целевой функции. Если условие оптимальности выполняется для всех небазисных переменных, вычисления заканчиваются, в противном случае необходимо перейти ко второму шагу.
Шаг 2 С помощью симплексного условия допустимости определяется исключаемая из базиса переменная. Происходит изменение базиса и возврат к первому шагу.
При изменении базиса в данном случае не используются вычисления, выполняемые при реализации симплекс-метода, - специальная структура транспортной таблицы позволяет значительно упростить вычисления.
Решим транспортную задачу из примера 6.1, используя начальное решение, полученное методом северо-западного угла (таблица 6.2).
В методе потенциалов каждой i -й строке и каждому j -му столбцу транспортной таблицы ставятся в соответствие числа (потенциалы или двойственные переменные) ui и v j. Для каждой базисной переменной xij потенциалы ui и v j удовлетворяют уравнению ui + vj =cij.
В рассматриваемом примере имеем 7 переменных (потенциалов) и 6 уравнений, соответствующих шести базисным переменным. Чтобы найти значения потенциалов из этой системы уравнений, нужно присвоить одному из них произвольное значение (обычно полагают u1 =0) и затем последовательно вычислять значения остальных потенциалов.
Поскольку для базисных клеток верны равенства u1+ v 1 =с11=10 и u1+ v 2 =с12=2, то находим, что v1=10 и v 2 =2. Далее последовательно находим значения для u2 из равенства u2+ v 2 =с22=7. Оно будет равно u2=5. Далее легко находим потенциалы v 3, v 4 из равенств u2+ v 3 =с23=9 и u2+ v 4 =с24=20. То есть v 3 =4 и v4=15. И последний потенциал u 3 находим из условия, что u3+ v 4 =с24=18. Он равен u 3 =3.
Теперь вычислим выражения ui + vj - cij для всех небазисных переменных.
| Небазисные переменные | Значения ui + vj - cij |
| х13 | u1+v3-c13=0+4-20=-16 |
| х14 | u1+v4-c14=0+15-11=4 |
| x 21 | u2+v1-c21=5+10-12=3 |
| x31 | u3+v1-c31=3+10-4=9 |
| x32 | u3+v2-c32=3+2-14=-9 |
| x33 | u3+v3-c33=3+4-16=-9 |
Вычисленные значения совместно с нулевыми значениями для базисных переменных (поскольку ui + vj - cij =0 для любой базисной переменной х ij) фактически являются коэффициентами z-строки симплекс-таблицы.
| базис | x11 | x12 | x13 | x14 | x21 | x22 | x23 | x24 | x31 | x32 | x33 | x34 | |
| z | 0 | 0 | -16 | 4 | 3 | 0 | 0 | 0 | 9 | -9 | -9 | 0 |
Поскольку в транспортной задаче ведется поиск минимума стоимости перевозок, то вводимой в базис будет переменная, имеющая наибольший положительный коэффициент в z -строке. В данном случае вводимой будет переменная х31.
Описанные вычисления обычно выполняются непосредственно в транспортной таблице, как показано в таблице 6.4. Для потенциалов в таблицу добавляем еще один столбец справа и строку снизу. В этом случае нет необходимости в явном виде выписывать уравнения потенциалов. Вычисления в транспортной таблице начинаются с присвоения потенциалу u1=0. Затем находим v -потенциалы в первой строке. Потом, используя v 2, находим u 2 и так далее находим все потенциалы. После этого вычисляем для всех небазисных переменных величины ui + vj - cij и записываем их в правом нижнем углу соответствующей ячейки транспортной таблицы.
Определив вводимую в базис переменную x31, далее следует определить исключаемую переменную. Для этого строим цикл (маршрут перевозок, начинающийся и заканчивающийся во вводимой переменной). Цикл состоит из последовательности горизонтальных и вертикальных отрезков (но не диагональных), соединяющих ячейки, соответствующие текущим базисным переменным, и ячейку, соответствующую вводимой переменной. При этом все ячейки, в которых делается поворот, меняют значения. В нечетных вершинах цикла увеличиваем на q перевозки, а в нечетных уменьшаем на q. Значение q выбирается так, чтобы одна базисная переменная стала равной нулю там, где отнимается q и в ячейке, вводимой в базис, значение увеличится на q, т.е. она станет базисной.
Таблица 6.4
| мельницы | 1 | 2 | 3 | 4 | предло- | ||||||
| элеваторы | жение | ||||||||||
| 1 |    -
| 10 |   +
| 2 | 20 | 11 | u1=0 | ||||
| 5 | 10 | -16 | 4 | 15 | |||||||
| 2 | 12 |   -
| 7 | 9 |   +
| 20 | u1=5 | ||||
| 3 | 5 | 15 | 5 | 25 | |||||||
| 3 |   +
| 4 | 14 | 16 |  -
| 18 | u1=3 | ||||
| 9 | -9 | -9 | 10 | 10 | |||||||
| Спрос | 5 | 15 | 15 | 15 | 50 | ||||||
| v1=10 | v2=2 | v3=4 | v4=15 | ||||||||
Понятно, что q надо выбрать как минимум всех стоимостей перевозок с ij, находящихся на четных вершинах цикла. Тогда выполнятся два условия цикла (маршрута перевозок):
1 Должны выполняться ограничения на спрос и предложение.
2 Ни по какому отрезку маршрута не должны выполняться перевозки с отрицательными объемами грузов.
Подобный цикл представлен в таблице 6.4. Он начинается из ячейки (3,1) и там же заканчивается и перевозит по всем отрезкам цикла 5 единиц груза.
Таблица 6.5
| мельницы | 1 | 2 | 3 | 4 | предло- | ||||||
| элеваторы | жение | ||||||||||
| 1 | 10 |   -
| 2 | 20 |  +
| 11 | u1=0 | ||||
| -9 | 15 | -16 | 4 | 15 | |||||||
| 2 | 12 |  +
| 7 | 9 | -
| 20 | u1=5 | ||||
| -6 | 0 | 15 | 10 | 25 | |||||||
| 3 | 4 | 14 | 16 | 18 | u1=3 | ||||||
| 5 | -9 | -9 | 5 | 10 | |||||||
| Спрос | 5 | 15 | 15 | 15 | 50 | ||||||
| v1=1 | v2=2 | v3=4 | v4=15 | ||||||||
Цикл проходит через ячейки х31, х34, х24, х22, х12, х11 и х31. В каждой ячейке цикла изменяем значения на q =min(x34, х22, х11)=5. В нечетных прибавляем 5 единиц, а в четных ячейках уменьшаем на 5единиц. Получится таблица 6.5.
Новая суммарная стоимость перевозок равна
f=15*2+5*4+0*7+15*9+5*18+10*20=475.
В новой транспортной таблице 6.5, используя новые базисные переменные, находим новые потенциалы. Они все будут принимать прежние значения, кроме v1=1. Находим также в небазисных переменных разности ui + vj - cij и записываем в правом нижнем углу. Максимальное положительное значение находится в ячейке (1,4) (оно равно +4), следовательно, вводить будем переменную х14. Строим также цикл через ячейки х14, х12, х22 и х14, по которому перебросим 10 единиц груза. В результате получим транспортную таблицу 6.6.
Таблица 6.6
| мельницы | 1 | 2 | 3 | 4 | предло- | ||||||
| элеваторы | жение | ||||||||||
| 1 | 10 | 2 | 20 | 11 | u1=0 | ||||||
| -13 | 5 | -16 | 10 | 15 | |||||||
| 2 | 12 | 7 | 9 | 20 | u1=5 | ||||||
| -10 | 10 | 15 | -4 | 25 | |||||||
| 3 | 4 | 14 | 16 | 18 | u1= 7 | ||||||
| 5 | -5 | -5 | 5 | 10 | |||||||
| Спрос | 5 | 15 | 15 | 15 | 50 | ||||||
| v1= -3 | v2=2 | v3=4 | v4=1 1 | ||||||||
Новая суммарная стоимость перевозок равна
f=5*2+5*4+10*7+15*9+10*11+5*18=435.
Найдем для нового базисного решения потенциалы u i и vj. Теперь новые значения величин ui + vj - cij для всех небазисных переменных х ij отрицательные. Поэтому решение, представленное в таблице 6.6, оптимально.
На этом вычисления заканчиваются, и выписывается решение транспортной задачи:
| От элеватора | До мельницы | Количество зерновозов |
| 1 | 2 | 5 |
| 1 | 4 | 10 |
| 2 | 2 | 10 |
| 2 | 3 | 15 |
| 3 | 1 | 5 |
| 3 | 4 | 5 |
Минимальная стоимость перевозок равна 435 тысяч рублей.
Задача о назначениях
Задача о назначениях заключается в таком выборе распределения ресурсов по объектам, при котором минимизируется стоимость назначений. Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс.
Возможные применения задачи о назначениях можно видеть в таблице 6.7.
Таблица 6.7
| Ресурсы | Объекты | Критерии эффективности |
| Рабочие | Рабочие места | Время |
| Грузовые автомобили | Маршруты | Затраты |
| Станки | Участки | Объем переработанной продукции |
| Экипажи | Рейсы | Время простоя |
| Коммивояжер | Города | Товарооборот |
Матрица стоимостей имеет вид
,
где cij – затраты, связанные с назначением i -го ресурса на j -й объект, i, j =1,…,n,; n – число объектов или ресурсов.
Обозначим
Таким образом, решение задачи можно записать в виде матрицы
.
Допустимое решение называется назначением. Оно строится путем выбора ровно одного элемента в каждой строке матрицы Х и ровно одного элемента в каждом столбце этой матрицы.
Математическая постановка задачи:
Задача о назначениях является частным случаем транспортной задачи, в которой а i =bj =1 (i =1, …,n; j =1, …,n), поэтому ее можно решить с помощью метода потенциалов. Однако более эффективным является метод, учитывающий специфику математической модели и называемый венгерским методом. Рассмотрим его алгоритм:
Шаг 1 Цель данного шага – получение максимально возможного числа нулевых элементов в матрице С. Для этого из всех элементов каждой строки вычитается минимальный элемент соответствующей строки, а затем из всех элементов каждого столбца вычитается минимальный элемент соответствующего столбца.
Шаг 2 Если после выполнения первого шага в каждой строке и в каждом столбце матрицы С можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.
Шаг 3 Если допустимое решение, состоящее из нулей, не найдено, то надо провести минимальное число прямых через некоторые столбцы и строки матрицы С так, что все нули оказались вычеркнуты. Выбрать наименьший невычеркнутый элемент, этот элемент вычесть из каждого невычеркнутого элемента и прибавить к каждому элементу, стоящему на пересечении проведенных прямых.
Шаг 4 Если после проведения третьего шага решения не будет найдено, то процедуру проведения прямых следует повторять до тех пор, пока не будет получено допустимое решение.
При применении рассмотренного алгоритма нужно иметь в виду следующее:
· если исходная матрица С не является квадратной, то нужно ввести фиктивные ресурсы или фиктивные объекты так, чтобы матрица стала квадратной;
· если какой либо ресурс не может быть назначен на какой-то объект, то соответствующая ему стоимость должна быть выбрана равной достаточно большому значению;
· если исходная задача является задачей максимизации, то все элементы матрицы С следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала отрицательных элементов. Затем можно решить задачу минимизации;
· если число линий, необходимое для того, чтобы вычеркнуть нулевые элементы, равно числу строк или столбцов квадратной матрицы, то существует назначение нулевой стоимости.
Контрольные вопросы
1 Как открытую транспортную задачу свести к закрытой?
2 Какими методами можно найти начальное допустимое решение для транспортной задачи?
3 Каким образом при решении транспортной задачи методом потенциалов в текущей итерации находят вводимую в базис переменную?
4 Каким образом в транспортной задаче в текущей итерации находят исключаемую из базиса переменную?
5 Можно ли решить задачу о назначениях методом потенциалов?
6 Если при решении задачи о назначениях венгерским методом при вычеркивании нулей окажется, что вычеркнуты все строки и столбцы, что это означает?
Тема 7 Основы сетевого планирования
Основные понятия теории графов
Современное сетевое планирование начинается с разбиения программы работ на операции, далее определяются оценки продолжительности операций, а затем строится сетевая модель (график). Построение сетевой модели позволяет проанализировать все операции, входящие в проект, и внести улучшения в структуру модели до начала ее реализации.
Сетевая модель – графическое изображение плана выполнения комплекса работ, состоящего из нитей (работ) и узлов (событий), которые отражают логическую взаимосвязь всех операций. В основе сетевого моделирования лежит изображение планируемого комплекса работ в виде графа.
Граф – схема, состоящая из заданных точек (вершин), соединенных системой линий. Отрезки, соединяющие вершины, называются ребрами или дугами графа. Если указано, какая вершина является начальной, то отрезки называются дугами, а сам граф – ориентированным (орграфом). Если ориентация вершин не указана, то отрезки называются ребрами, а граф называется неориентированным.
Теория графов оперирует понятием пути, объединяющим последовательность взаимосвязанных ребер. Контур означает такой путь, у которого начальная вершина совпадает с конечной. Сетевой график – это ориентированный граф без контуров. В сетевом моделировании имеются два основных понятия – работа и событие.
Работа – это либо активный процесс, требующий затрат ресурсов, либо пассивный процесс (ожидание), приводящий к достижению намеченного результата.
Фиктивная работа – это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.
Событие – это результат (промежуточный или конечный) выполнения одной или нескольких предшествующих работ.
Путь – это любая непрерывная последовательность (цепь) работ и событий.
Критический путь – это путь, имеющий наибольшую продолжительность по времени; он включает самые напряженные работы комплекса.
Работы, расположенные на критическом пути, называются критическими. Все остальные работы называются некритическими и обладают резервом времени, который позволяет передвигать сроки их выполнения, не влияя на общую продолжительность выполнения всего комплекса работ.
При построении сетевых моделей необходимо соблюдать следующие правила:
1 Сеть изображается слева направо, и каждое событие с большим порядковым номером изображается правее предыдущего. Общее направление стрелок, изображающих работы, также в основном должно расположено быть слева направо, при этом каждая работа должна выходить из события с меньшим номером и входить в событие с большим номером.
2 Два соседних события могут объединяться лишь одной работой. Для изображения параллельных работ вводятся промежуточное событие и фиктивная работа (рисунок 7.1).
Рисунок 7.1 Изображение на сетевом графике параллельных работ
3 В сети не должно быть тупиков, т.е. промежуточных событий, из которых не выходит ни одна работа (рисунок 7.2)
Рисунок 7.2 В сетевом графике нет промежуточных событий без продолжения
4 В сети не должно быть промежуточных событий, которым не предшествует хотя бы одна работа (рисунок 7.3).
Рисунок 7.3 В графике нет висячих событий
5 В сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую сеть (рисунок 7.4).
Рисунок 7.4Не должно быть путей типа k ® j ® s ® k
6 Для правильной нумерации событий поступают следующим образом: нумерация событий начинается с исходного события (в него не входит ни одна работа, таких бывает только одно событие), которому дается номер 1 (рисунок 7.5 а). Из исходного события 1 вычеркиваются все исходящие из него работы; на оставшейся сети вновь находят событие, в которое не входит ни одна работа. Этому событию дается номер 2 (рисунок 7.5 б). Затем вычеркивают работы, выходящие из работы 2, и вновь находят на оставшейся части сети событие, в которое не входит ни одна работа – ему присваивается номер 3 (рисунок 7.5 в), и так продолжается до завершающего события (рисунок 7.5 г).
Рисунок 7.5 а) Рисунок 7.5 б)
Рисунок 7.5 г) Рисунок 7.5 д)
Построение сетевого графика начинается с составления списка работ, подлежащих выполнению. Их последовательность в списке произвольная, порядок нумерации осуществляется в соответствии с их последовательностью в списке. Перечень работ и событий тщательно продумывается и детализируется в зависимости от конкретных условий. Работы, включенные в список, характеризуются определенной продолжительностью, которая устанавливается на основании действующих нормативов или по аналогии с ранее выполнявшимися операциями. Такие временные оценки называются детерминированными (однозначными). Если нормативные данные временных оценок отсутствуют, то они определяются по экспертным оценкам специалистов и называются стохастическими (вероятностными).
После составления списка работ приступают к процедуре построения сетевого графа. Рассмотрим пример составления сетевого графика.
