Производственной процесс и его элементы

 

 Табл. 5  

– Там, где я  добавлял тонну, стоит знак плюс, а  где убирал – минус. А набор  клеток, в которых мы произвели изменения, давай назовём циклом ^*. Итак, что же это нам даст? Провоз одной тонны по маршруту (1,1) – 80 долларов. Их надо добавить. А 150 долларов – провоз тонны на маршруте (1,3) – наоборот, долой, как и 60 с маршрута (2,1). Ну и 90 придётся прибавить за лишнюю тонну на маршруте (2,3). Итого, транспортные расходы изменятся на

80 + 90 –  150 – 60 = –40

долларов.

– Здорово! 40 долларов можно сберечь! – восхитился Джо. – Но это мы поставили на маршрут (1,4) только тонну. Давай поставим 100 тонн и сбережём 4000, или нет, поставим 400 тонн и тогда ещё нам будут доплачивать!

В глазах Джо  загорелся огонек алчности, но тут  же потух:

– Нет, здесь  что-то не так.

– Ясное дело, не так, – согласился Бэйт. – Ведь сколько мы добавим на маршрут (1,1), столько же придётся снять с (1,3) и (2,1). А оттуда самое большее можно снять 35 тонн. Ведь не хочешь же ты везти мануфактуру обратно на склад!

– Ещё бы!

– Значит, самое  большее удастся провезти по маршруту (1,1) 35 тонн; это позволит сэкономить 40 × 35 = 1400 долларов, и новый план перевозок будет таким, как в таблице 6. В клетках, которые не вошли в цикл, всё осталось по-старому. 
 
 

 

 Табл. 6  

– 1400 долларов –  кругленькая сумма! Давай проверять  другие пустые клетки. Может набредём на маршрут, который тоже стоит использовать. Вот, например, начнём с клетки (1,2). Для неё расходы изменятся на

120 + 60 –  70 – 80 = 30 > 0.

Тысяча чертей! Маршрут (1,2) использовать не стоит. А, может  быть, воспользоваться...

– Не трудись, Джо. Я уже проверял: больше из этого  плана не выжмет ни доллара сам  Данциг.

– Данциг, Данциг... это не тот ли, который обчистил «Бэнк оф...»?

– Нет, Джо, он не из наших. Это тот малый, который  придумал этот метод. Правда, ещё до него какие-то красные...

... Инспектор  Клифф сидел у себя в кабинете  на Авеню-стрит, снова и снова  всматриваясь в вещественные улики: три мастерски взломанных замка и пепел от тщательно сожжённого календаря в гостинице, где совещались грабители. И больше ничего. И всё-таки... это напоминает почерк Бэйта, за которым он, Клифф, охотится уже столько лет! К примеру календарь. Зачем он? Может, на нём делались выкладки? Возможно. Но где же искать Бэйта?

– Сержант! Усиленные  наряды во все бары города! – крикнул  он, осознавая в то же время полную безнадёжность своего приказа: в  барах Бэйта не будет. На столе  инспектора зазвонил телефон. Клифф снял трубку, послушал и закричал:

– Сержант, отставить! Оцепить научную библиотеку штата! Мне – машину и набор наручников!

Немного теории

Что же позволило  сэкономить на транспортных расходах 1400 долларов? Проследим за действиями ловких гангстеров. Сначала Бэйт нашёл допустимый план перевозок. Метод, которым он при этом воспользовался называется методом минимального элемента и понятно почему: в нём перевозки всё время ставятся на маршруты с минимальными тарифами, а если будут два маршрута с одинаковым тарифом, то предпочтение, естественно, нужно отдать тому из них, для которого возможная перевозка больше.

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

Пусть имеется  m поставщиков (складов) и n потребителей, a_i – емкость i-го склада, а b_j – потребность j-го потребителя. Пусть x_ij – перевозка от i-го поставщика к j-му потребителю. Допустимы только такие планы перевозок, для которых ^**

 

то есть из каждого  склада вывозится всё, что там  есть, и каждому потребителю привозится всё, что ему требуется. Кроме  того, заданы тарифы c_ij , то есть стоимости перевозки единицы груза от i-го поставщика к j-му потребителю. В задаче требуется отыскать такой допустимый план перевозок, для которого сумма стоимостей перевозок

минимальна.

Сформулированная  задача – это частный случай задачи линейного программирования, так  как «целевая функция» (2), выражающая транспортные расходы, и ограничения (1) линейны.

Сущность распределительного метода состоит в том, что для  каждой свободной клетки находится  цикл, в который входят, кроме  неё, только заполненные клетки. С  помощью этого цикла определяют, на сколько изменятся транспортные расходы, если ввести в свободную клетку единицу груза. Эта величина k_ij называется индексом свободной клетки (i, j). Если k_ij < 0, то в клетку вносится максимально возможная перевозка (она равна минимальной перевозке в «отрицательных» клетках цикла), а если k_ij ≥ 0, то маршрут (i, j) использовать не стоит и проверяется следующая клетка. Процесс заканчивается, когда выясняется, что для всех свободных клеток k_ij ≥ 0.

Оптимальный план следует искать среди планов, в  которых заполненные клетки не образуют циклов. Обычно в транспортной задаче число заполненных клеток в точности равно m + n – 1, и цикл можно построить единственным образом (например, в рассмотренной задаче число заполненных клеток равно 3 + 4 – 1 = 6). Если включить в цикл свободные клетки со знаком «+», то после изменения плана в нём может оказаться больше m + n – 1 заполненных клеток и план будет содержать циклы. Убедиться в этом можно, попытавшись в таблице 5 построить цикл (1,1) → (1,4) → (2,4) → (2,1).

Если число  заполненных клеток меньше m + n – 1 (такая задача называется вырожденной), то для того, чтобы построить цикл, к заполненным клеткам нужно добавить пустые так, чтобы они с уже заполненными не образовывали циклов. Например, пусть таблицей 7 задан вырожденный план перевозок (в нём не хватает 1 заполненной клетки).

 

 Табл. 7  

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

Расходы по первому плану перевозок составят

z₁ = 25×3 + 30×2 + 40×4 + 50×6 = 595.

Найдём индексы  свободных клеток:

По маршруту (2,1) возить выгодно, но сколько можно  по нему провезти? min(25,0) = 0. Стало быть, на маршрут (2,1) можно поставить лишь перевозку 0, получится таблица 8.

 

 Табл. 8  

Расходы по этому  новому плану останутся прежними: z₂ = 595. Но, тем не менее, операция перенесения нуля не бессмысленна: теперь изменятся индексы. Действительно, теперь

k₁₃ = 3 + 3 – 3 – 4 = –1 < 0.

То есть теперь оказывается выгодным маршрут (1,3). Его  использование с перевозкой 25 тонн приведёт к транспортным расходам в сумме z₃ = 595 – 25 = 570.

Математическая  модель, которую применил Бэйт, –  модель транспортной задачи линейного  программирования, – сейчас очень  широко применяется в экономике  и управлении производством. Именно с помощью подобных моделей во многих местах управляют перевозкой продуктов в магазины и кирпича на стройки, добиваясь большого сокращения транспортных расходов.

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

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

Задача  о назначениях

Два немолодых  джентльмена чинно сидели в научной  библиотеке штата.

– ... Уверен, ищейки сюда не сунутся. Итак, в банке 4 входа. Каждый из парней согласен занять любой, но они им кажутся по-разному опасными: у одного входа дежурит полицейская машина, другой выходит на людную улицу, в третьем слишком узкая дверь. Их требования в долларах сведены в таблицу 9.