4. Компания планирует оптимизировать распределение станочного парка, состоящего из станков четырех типов, для выполнения станочных работ пяти видов. Пусть имеется 25, 30, 20 и 30 станков каждого типа. Приведем количество работ каждого вида: 20, 20, 30, 10 и 25 соответственно. Отметим, что станки четвертого типа не используются для выполнения работ четвертого вида. В табл. 5.14 представлена стоимость (в долл.) выполнения каждого вида работ на станках определенного типа. Сформулируйте транспортную задачу, решите ее с помощью программы TORA и интерпретируйте полученный результат.

Таблица 5.14

5. Спрос на некий скоропортящийся продукт в следующие 4 месяца составляет 400, 300, 420 и 380 тонн соответственно. Предложение этого товара в те же месяцы составляет 500, 600, 200 и 300 тонн. Отпускная цена на этот товар колеблется от месяца к месяцу и равна соответственно 100, 140, 120 и 150 долл. за тонну. Поскольку товар скоропортящийся, он должен быть реализован в течение трех месяцев (включая текущий). Стоимость хранения в течение месяца тонны товара равна 3 долл. Природа товара такова, что невозможна задержка с выполнением заказа. Опишите данную ситуацию как транспортную модель и найдите ее оптимальное решение для 4-х месяцев с помощью программы TORA.

6. Спрос на специализированные малые двигатели в следующие пять кварталов составляет 200, 150, 300, 250 и 400 единиц. Мощность производства двигателей в тот же период времени оценивается в 180, 230, 430, 300 и 300 единиц. Невыполнение заказов не допускается, при необходимости можно организовать сверхурочные работы для выпуска дополнительной продукции. Стоимость единицы продукции в каждый из следующих пяти кварталов составляет 100, 96, 116, 102 и 106 долл. соответственно. Стоимость дополнительно произведенной продукции увеличивается на 50% по сравнению со стандартной стоимостью в соответствующий период. Если двигатели, произведенные в одном квартале, реализуются в последующих, за хранение одного двигателя в течение квартала необходимо заплатить 4 долл. Сформулируйте транспортную задачу. С помощью программы TORA определите оптимальный план производства двигателей.

7. Периодически проводится профилактика самолетных двигателей с заменой важной детали А. В следующие 6 месяцев будут выполнены регламентные работы (с разбивкой по месяцам) на 200,180, 300,198, 230 и 290 двигателях. Все регламентные работы, запланированные на месяц, проводятся в течение первых двух дней месяца, когда отработанная деталь заменяется А на новую или отремонтированную. Снятую деталь можно отремонтировать в местной мастерской, и она будет готова к началу следующего месяца, или отправить в центральные мастерские, откуда она вернется через 3 месяца (считая месяц, в котором выполнены

профилактические работы). Стоимость ремонта одной детали А в местной мастерской составляет 120 долл., а в центральной - только 35 долл. Если отремонтированная деталь будет использована в последующие месяцы, стоимость ее хранения составит 1,50 долл. в месяц. Новые детали можно купить по цене 200 долл. В первом месяце с возрастанием цены на 5% каждые 2 месяца. Представьте описанную ситуацию в виде транспортной модели и с помощью программы TORA найдите ее оптимальное решение.

8. Управление национальными парками получило четыре заявки от подрядчиков на лесозаготовки в трех сосновых лесных массивах Арканзаса. Эти массивы имеют площадь 10 000, 20 000 и 30 000 акров. Каждый подрядчик может получить для разработки не более половины всех отводимых для лесозаготовки площадей. Предлагаемые подрядчиками цены за разрешение на лесозаготовки (долл.) показаны в табл. 5.15.

Таблица 5.15

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

b) С помощью программы TORA определите площади, выделяемые каждому подрядчику для лесозаготовок.

5.3. РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

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

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

Алгоритм решения транспортной задачи будет проиллюстрирован на следующем примере.

Пример 5.3.1

Транспортная компания занимается перевозкой зерна специальными зерновозами от трех элеваторов к четырем мельницам. В табл. 5.16 показаны возможности отгрузки зерна (предложения) элеваторами (в зерновозах) и потребности (спрос) мельниц (также в зерновозах), а также стоимость перевозки зерна одним зерновозом от элеваторов к мельницам. Стоимость перевозок с, приведена в сотнях долларов.

В данной задаче требуется определить структуру перевозок между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо вычислить объемы перевозок хц между ;-м элеватором иу-й мельницей.

Таблица 5.16

Мельницы

1 2 3 4 Предложение

Спрос 5 15 15 15

Последовательность этапов алгоритма решения транспортной задачи в точности повторяет аналогичную последовательность этапов симплексного алгоритма.

Шаг 1. Определяем начальное базисное допустимое решение, затем переходим к выполнению второго этапа.

Шаг 2. На основании условия оптимальности симплекс-метода среди всех небазисных переменных определяем вводимую в базис. Если все небазисные переменные удовлетворяют условию оптимальности, вычисления заканчиваются; в противном случае переходим к третьему этапу.

ШагЗ. С помощью условия допустимости симплекс-метода среди текущих базисных переменных определяем исключаемую. Затем находим новое базисное решение. Возвращаемся ко второму этапу.

Рассмотрим каждый описанный этап в отдельности. 5.3.1. Определение начального решения

Общая транспортная модель с т пунктами отправления и п пунктами назначения имеет т + п ограничений в виде равенств, по одному на каждый пункт отправления и назначения. Поскольку транспортная модель всегда сбалансирована