Практическое занятие №8 Усложненные задачи транспортного типа.

На практике классические задачи транспортного типа встречаются крайне редко. Обычно при составлении экономико-математической модели задачи транспортного типа приходится вводить целый ряд дополнительных ограничений, а затем пользоваться методом потенциалов. Ряд экономических задач легко сводим к транспортной задаче. Рассмотрим наиболее часто встречающиеся ситуации.

1. Отдельные поставки от определенных поставщиков неко­торым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки комму­никаций и т. д.). Это ограничение требует, чтобы в матрице пере­возок, содержащей оптимальный план, определенные клетки оставались свободными. Последнее достигается искусственным завышением затрат на перевозки С_ij в клетках, перевозки через ко­торые следует запретить. При этом производят завышение вели­чины С_ij до таких значений, которые будут заведомо больше всех, с которыми их придется сравнивать в процессе решения задачи.

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

3. Ряд транспортных маршрутов по которым необходимо доставить грузы, имеет ограничения по пропускной способности. Если, например, по маршруту A₁B₁ можно провести не более q единиц груза, то B_j столбец матрицы разбивается на два В_j^{`</sup> и B<sub>j</sub><sup>``</sup>. В первом спрос принимается равным разности между дейст­вительным спросом b<sub>j</sub> и ограничением q: b<sub>j</sub><sup>`} = b_j — q, во втором - равным ограничению q, т. е. b'`<sub>j</sub>= q. Затраты С<sub>ij</sub> в обоих столбцах одинаковы и равны данным, но в первом столбце B<sup>`</sup>_j, в клетке, соответствующей ограничению i, вместо истинного тарифа С_ij ставится искусственно завышенный тариф, т.е. ставится число на порядок большее остальных чисел (клетка блокирует­ся). Затем задача решается обычным способом.

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

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

6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателей С_ij. Выбор клетки, подлежа­щей заполнению при переходе oт одного допустимого плана к другому, должны производиться не по минимальной отрицатель­ной разнице [с_ij - (α_i + β_j)], а по максимальной положительной разнице. Оптимальным будет план, которому в последней таблице сопутствуют свободные клетки с неположитель­ными элементами: все разности [с_ij - (α_i + β_j)]≤0

7. Необходимо в одно время распределить груз различного ро­да по потребителям. Задачи данного типа называются мнoгопродуктовыми транспортными задачами. В этих задачах поставщики т родов грузов разбиваются на условных поставщиков, а пот­ребители n родов грузов разбиваются на n условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты A_iB_j долж­ны быть блокированы (закрыты), поскольку в данной постанов­ке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам должна соответствовать очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно опи­сывать одной моделью, Например, если поставки грузов различ­ного рода независимы, то задачу можно представить в виде комп­лекса транспортных задач по каждому роду груза. Однако если между грузами различного рода существует связь (например, одни из грузов можно заменить другими), то в общем случае исход­ную модель (задачу) не удается разбить на комплекс простых транспортных задач.

8. Доставка груза в кратчайший срок

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

Для решения подобных задач рассмотренный ранее метод по­тенциалов непригоден. Эти задачи решаются с помощью специ­ального алгоритма.

1. Составить матрицу условий так как это делают при решении обычной транспортной задачи.

2. Найти методом потенциалов план, у которого линейная форма достигает минимального значения.

3. Определить max t_ij (наибольшее из времён) запланированных перевозок (где х_ij > 0 ).

4. Заблокировать все всех клетки матрицы, где t_ij ≥ max t`_ij.

5. Отыскать для изменённой матрицы решение, при котором линейная форма достигает минимума. Если в полученном решении х_ij > 0 расположены только в незаблокированных клетках, то снова находим max t``_ij и повторяем шаги 4 и 5. Если же в полученном решении имеется хотя бы один x_ij > 0 расположенный в заблокированной клетке, то оптимальным будет предыдущее решение.

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