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

Математическая модель задачи.

Переменные задачи. Обозначим количество видов сырья, которые будут перевозиться из склада i в цеха j как X _ij (i = 1, 2, 3; j = 1, 2, 3, 4). Это переменные задачи, значения которых должны быть определены в процессе решения. Например, X ₂₃ – это количество видов сырья, которое должно быть перевезено из склада № 2 (пункт 2) в сырьевой цех отделения сырокопченых колбас (пункт 3).

В задаче содержится 3·4=12 переменных.

Ограничения на переменные задачи. Очевидно, что все переменные задачи не отрицательные и целые числа, т.е.

X_ij 0, (2.1)

X_ij – целые числа, (2.2)

где i = 1, 2, 3; j = 1, 2, 3, 4.

Кроме этого, должны быть удовлетворяться следующие условия. Количество видов сырья, вывозимых из склада № 1 равно 15, поэтому:

X₁₁ + X₁₂ + X₁₃ + X₁₄ = = 15. (2.3)

Аналогично для склада № 2:

X₂₁ + X₂₂ + X₂₃ + X₂₄ = = 25. (2.4)

И для склада № 3:

X₃₁ + X₃₂ + X₃₃ + X₃₄ = = 5. (2.5)

По условию задачи для приготовления крупнокусковых полуфабрикатов (пункт 1) требуется 5 ингредиентов, поэтому:

X₁₁ + X₂₁ + X₃₁ = = 5. (2.6)

Аналогично, для приготовления вареных колбас (пункт 2):

X₁₂ + X₂₂ + X₃₂ = = 15 (2.7)

Для приготовления сырокопченых колбас (пункт 3):

X₁₃ + X₂₃ + X₃₃ = = 15. (2.8)

Для приготовления рубленых полуфабрикатов (пункт 4):

X₁₄ + X₂₄ + X₃₄ = = 10. (2.9)

Целевая функция. Транспортные расходы на перевозку сырья для приготовления каждого вида продукции вычисляется по формуле:

Z = C_ijX_ij = 10X₁₁ + 0X₁₂ + 20X₁₃ +... +18X₃₄. (2.10)

Окончательно транспортная задача имеет вид (табл. 2.2). Нужно найти такие значения переменных X_ij (i = 1, 2, 3; j = 1, 2, 3, 4) при которых целевая функция, определяемая формулой (2.10), будет иметь минимальное значение и будут выполнены ограничения (2.1) - (2.9):

X _ij 0, где X _ij – целые числа (i = 1, 2, 3; j = 1, 2, 3, 4).

; .

; .

;

.

Шаг 1. Проверка на сбалансированность.

Общее число запасов на складах 15 + 25 + 5 = 45.

Общая потребность 5 + 15 + 15 + 10 =45.

Задача является сбалансированной (закрытой) [1] (суммы чисел в последнем столбце и нижней строке таблицы равны). Если транспортная задача не сбалансирована, то в таблицу добавляется еще одна строка или столбец. Причем, стоимости перевозки в добавленных ячейках принимают равные нулю.

Шаг 2. Поиск начального решения. Метод северо-западного угла.

Запишем настоящую задачу в виде транспортной таблицы (табл. 2.4). В верхней строке перечислим потребности потребителей по порядку номеров. В левом столбце перечислим имеющиеся запасы на складах. На пересечении j- го столбца и i -й строки будем записывать количество продукции, поставляемое с i- го склада j -му потребителю. Пока начальное решение не найдено, оставим эти клетки пустыми.

Таблица 2.4

Введем вспомогательные строку и столбец, в которых будем отмечать оставшиеся нераспределенные запасы и, соответственно, потребности (остатки). Изначально их содержимое равно исходным запасам и потребностям, так как еще ничего не распределялось. На рисунке они представлены серым цветом.

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

Таблица 2.5

Итерация 1.

Заполним клетку a ₁, b ₁. Сравним значения остатков для склада a ₁ и потребителя b ₁.

Нераспределенных остатков по потребностям для b ₁ меньше (см. табл. 2.5 выше, жирный курсив), запишем меньшее число в клетку a ₁, b ₁ одновременно вычитая его из обеих клеток остатков (см. табл. 2.6). При этом клетка остатков по потребностям обнулится, указывая, что все потребности для b ₁ удовлетворены (см. табл. 2.6). Поэтому исключим столбец b ₁ из дальнейшего рассмотрения (темно-серый фон).

Ненулевое значение остатка по запасам для a ₁ показывает, сколько единиц продукции осталось на складе не потребленной.

Таблица 2.6

Итерация 2.

Заполним клетку a ₁, b ₂. Сравним значения остатков для склада a ₁ и потребителя b ₂. Нераспределенных остатков по запасам для a ₁ меньше (см. табл. 2.6, жирный курсив), запишем меньшее число в клетку a ₁, b ₂ одновременно вычитая его из обеих клеток остатков (см. табл. 2.7). При этом клетка остатков по запасам обнулится, указывая, что все запасы со склада a₁ использованы (см. табл. 2.7). Поэтому исключим строку a ₁ из дальнейшего рассмотрения (темно-серый фон).

Ненулевое значение остатка по потребностям для b ₂ показывает, сколько единиц продукции ему еще требуется.

Таблица 2.7

Итерация 3.

Таблица 2.8

Итерация 4.

Таблица 2.9

Итерация 5.

Таблица 2.10

Итерация 6.

Таблица 2.11

Получено допустимое начальное решение (опорный план[2]) (см. табл. 2.12), удовлетворенны нужды всех потребителей и использованы все запасы со складов.

Таблица 2.12

Шаг 3. Проверка полученного опорного плана на невырожденность[3].

Количество заполненных клеток N должно удовлетворять условию N = n + (m -1). В нашем случае N = 6, n + m =4 + 3 = 7, что удовлетворяет условию невырожденности плана.

Шаг 4. Расчет общих затрат на перевозку всей продукции.

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

Таблица 2.13

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

Шаг 5. Проведение поэтапного улучшения начального решения. Метод потенциалов.

Итерация 1.

Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек (см. таблицу 2.13) путем переноса только тех ячеек P _ij, которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми. Кроме того, введем вспомогательный столбец, в который внесем значения неизвестных U₁... U₃ (3, это m - число складов) и вспомогательную строку, в которую внесем значения неизвестных V₁... V₄ (4, это n - число потребителей). На рисунке они представлены серым цветом заливки. Эти n+m неизвестных должны для всех (i, j), соответствующих загруженым клеткам, удовлетворять линейной системе уравнений

U _i + V _j = P _ij (2.11)

Эту систему всегда можно решить следующим способом. На первом шаге полагают V₄ = 0. Если на k -м шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k +1)-м шаге из уравнения (2.11), так как значение другой неизвестной в этом уравнении уже известно. То, какую неизвестную можно найти на (k +1)-м шаге, определяют методом проб. Переменные U_i и V_j называются симплекс-множителями или потенциалами. Рабочая матрица затрат с рассчитанными потенциалами представлена в табл. 2.14.

Таблица 2.14

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

1) Пусть V₄ = 0;

2) U₂ = P_2,4 - V₄;

3) U₃ = P_3,4 - V₄;

4) V₂ = P_2,2 - U₂;

5) V₃ = P_2,3 - U₂;

6) U₁ = P_1,2 - V₂;

7) V₁ = P_1,1 - U₁;

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки S_ij, по формуле S_ij = P_ij – U_i - V_j (курсив). Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются), то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции. Если же среди оценок нет отрицательных, то план является оптимальным.

Рабочая матрица затрат с заполненными оценками клетками, представлена в табл. 2.15.

Таблица 2.15

Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю (жирный курсив), так как ее воздействие на общие затраты является максимальными. В нашем случае такая оценка находится в ячейке а ₃, b ₁ (жирный курсив). В соответствующую ячейку транспортной таблицы необходимо переместить некоторое количество продукции, т.е. загрузить ее. Отметим в транспортной таблице ячейку а ₃, b ₁ знаком +. Пометим знаками - и + другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков + будет равно числу знаков -. Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному + и -. То есть, помеченные знаками клетки должны образовывать цикл[4] (табл. 2.16).

Таблица 2.16

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

Число M при этом составляет 5.

Переход к новой транспортной таблице разбивается на следующие шаги:

а) в ячейку а ₃, b ₁ новой таблицы записывается число M;

б) ячейка а ₁, b ₁ остается пустой;

в) в остальных ячейках, помеченных знаками - или +, число M соответственно вычитается из стоящего в ячейке числа или складывается с ним. Результат вносится в соответствующую ячейку новой таблицы;

г) непомеченные числа переносятся в новую таблицу без изменений. Остальные ячейки новой таблицы остаются пустыми (табл. 2.17).

Таблица 2.17

Итерация 2.