Исследование математических операций 2 (стр. 15 из 28)

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

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

6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателя c_ij . Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице

, а по максимальной положительной разнице

. Оптимальным будет план, которому в последней таблице сопутствуют свободные клетки с неположительными элементами: все разности

.

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

Рассмотрим примеры задач транспортного типа.

Пример 1. Одно фермерское хозяйство (A₁) имеет продовольственное зерно двух видов: 3 тыс. тонн – III класса и 4 тыс. тонн - IV класса. Второе фермерское хозяйство (A₂) также имеет зерно двух видов: 5 тыс. тонн – III класса и 2 тыс. тонн - IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (B₁) необходимо поставить 2 тыс. тонн пшеницы III класса, 3 тыс. тонн пшеницы IV класса и остальные 2 тыс. тонн пшеницы любого класса.

Аналогично второй элеватор (B₂) должен получить 8,25 тыс. тонн, из них пшеницы - 1 тыс. тонн III класса и 1,5 тыс. тонн IV класса.

Стоимость перевозки в д.е. 1 тонны зерна составляет: из пункта A₁ в пункты B₁ и B₂ - 1 и 1,5 соответственно; из пункта A₂ в пункты B₁ и B₂ - 2 и 1 д.е. соответственно.

Составить оптимальный план перевозок.

Решение

Каждого поставщика условно разбиваем на две части согласно двум видам зерна (

и

;

и ), аналогично потребителей разбиваем на три части (пшеница III класса, IV класса и любой класс): , и

, а также

, и . Потребности превышают запасы, поэтому вводим фиктивного поставщика A₃. Часть клеток в таблице запираем большими числами М; например, в клетке (1; 2) стоит большое число. Это значит, что поставщик не может удовлетворить потребителя

пшеницей IV класса за счет имеющейся пшеницы III класса.

С учетом сделанных замечаний составим первую таблицу (табл. 3.6).

Таблица 3.6

Исходные данные

Перевозки от фиктивного поставщика не производятся, поэтому

. Величина М намного больше c_ij . Применяя метод потенциалов, в итоге получим таблицу с оптимальным решением (табл. 3.7).

Таблица 3.7

Оптимальное решение

Анализ решения. Первый поставщик поставит на первый элеватор (B₁) пшеницу III класса ( x₁₂ = 2); пшеницу IV класса (x₂₂ = 3), а также пшеницу любого класса (III или IV) (x₁₃ = 1 ; x₂₃ = 1).

Второй поставщик (A₂) поставит на второй элеватор (B₂) пшеницу III класса (x₃₁ = 1), пшеницу IV класса (x₄₅ = 1,5) и частично любую пшеницу (x₃₆ = 4; x₄₆ = 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x₅₆ = 1,25). Минимальные затраты на перевозку составили: Z_min = 14 д.е.

Пример 2. Модель производства с запасами.

Фирма переводит свой головной завод на производство определенного вида изделий, которые будут выпускаться в течение четыре месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет:

 запасов изделий, произведенных в прошлом месяце, сохраняющихся для реализации в будущем;

 производства изделий в течение текущего месяца;

 избытка производства изделий в более поздние месяцы в счет невыполненных заказов.

Затраты на одно изделие в каждом месяце составляют 4 д.е. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 д.е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 2 д.е. в месяц.

Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно.

Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

Решение

Задачу можно сформулировать как транспортную. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом:

Транспортная система	Производственная система
1. Исходный пункт i	1. Период производства i
2. Пункт назначения j	2. Период потребления j
3. Предложение в пункте i	3. Объем производства за период i
4. Спрос в пункте j	4. Реализация за период j
5. Стоимость перевозки из i в j	5. Стоимость производства и хранения за период i и j

Перед нами структура транспортной модели. Для рассматриваемой задачи стоимость "перевозки" изделий из периода i в период j выражается как:

Из определения c_ij следует, что затраты в период i при реализации продукции в тот же период i (i = j) оцениваются только стоимостью производства. Если в период i производится продукция, которая будет потребляться позже (i < j), то имеют место дополнительные издержки, связанные с хранением. Аналогично производство в i –й период в счет невыполненных заказов (i > j) влечет за собой дополнительные расходы в виде штрафа. Например,

c₁₁ = 4 д.е.

c₂₄ = 4 + (0,5 + 0,5) = 5 д.е.

c₄₁ = 4 + (2 + 2 + 2) = 10 д.е.

Исходная транспортная таблица выглядит следующим образом (табл. 3.8).

Таблица 3.8

Оптимальное решение