Транспортная задача. 
Технология решения задач линейной оптимизации

Рассмотрим еще один пример, где используется средство поиска решений. Предположим, что фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в Денвере, Бостоне, Новом Орлеане и Далласе с производственными возможностями 200, 150, 225 и 175 единиц продукции ежедневно, соответственно. Центры распределения товаров фирмы располагаются в Лос-Анджелесе, Далласе, Сент-Луисе, Вашингтоне и Атланте с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно, соответственно. Хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в $ 0,75 в день, а штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $ 2,5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в таблице «Транспортные расходы» :

Таблица «Транспортные расходы» .

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

Поскольку данная модель сбалансирована (суммарный объем произведенной продукции равен суммарному объему потребностей в ней), то в этой модели не надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель нужно было бы ввести:

o В случае перепроизводства — фиктивный пункт распределения, стоимость перевозок единицы продукции в который полагается равной стоимости складирования, а объемы перевозок — объемам складирования излишков продукции на фабриках В случае дефицита — фиктивную фабрику, стоимость перевозок единицы продукции с которой полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок — объемам недопоставок продукции в пункты распределения.

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

Неизвестными в данной задаче являются объемы перевозок. Пусть.

— объем перевозок с i-ой фабрики в j-ый центр распределения.

Функция цели — это суммарные транспортные расходы, т. е. где — стоимость перевозки единицы продукции с i-и фабрики j-й центр распределения. Неизвестные в данной задаче должны удовлетворять следующим ограничениям:

• o Объемы перевозок не могут быть отрицательными
• o Так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены

В результате имеем следующую модель:

Минимизировать:

при ограничениях.

где — объем производства на i-й фабрике, bj — спрос в j-м центре распределения.

Для решения этой задачи с помощью средства поиска решений введем данные, как показано на рис. 5.

В ячейки А1: Е4 введены стоимости перевозок. Ячейки А6: Е9 отведены под значения неизвестных (объемы перевозок). В ячейки G6: G9 введены объемы производства на фабриках, а в ячейки А11: Е11 введена потребность в продукции в пунктах распределения. В ячейку F10 введена целевая функция =СУММПРОИЗВ (А1:Е4;А6:Е9).

Рис. 1. Исходные данные транспортной задачи

В ячейки А10: E10 введены формулы.

=СУММ (Аб:А9).

=СУММ (В6:В9).

=СУММ (С6:С9).

=СУММ (D6:D9).

=СУММ (Е6:Е9) определяющие объем продукции, ввозимой в центры распределения.

В ячейки F6: F9 ведены формулы.

=СУММ (А6:Е6).

=СУММ (А7:E7).

=СУММ (А8:Е8).

=СУММ (А9:Е9) вычисляющие объем продукции, вывозимой с фабрик.

Теперь выберем команду Сервис, Поиск решения (Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver), как показано на рис. 6.

Не забудьте в диалоговом окне Параметры поиска решения (Solver Options) установить флажок Линейная модель (Assume Linear Model). После нажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы (рис. 3).

Рис. 2. Диалоговое окно Поиск решения для транспортной задачи

Рис. 3. Оптимальное решение транспортной задачи

Задания для самостоятельного решения.

1) Решить транспортную задачу со следующими условиями:

2) Для строительства трех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый из заводов может изготовлять 100, 150 и 50 усл. ед. кирпича. Ежедневные потребности в кирпиче на каждом из строящихся объектах соответственно равны 75, 80, 60 и 85 усл. ед. Известны также тарифы перевозок 1 усл. ед. кирпича с каждого с заводов к каждому из строящихся объектов:

Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной.

3) На трех железнодорожных станциях скопилось 120, 110 и 130 незагруженных вагонов. Эти вагоны необходимо перегнать на железнодорожные станции В1, В2, В3, В4 и В5. На каждой из этих станций потребность в вагонах соответственно равна 80, 60, 70, 100 и 50. Тарифы перевозок задаются матрицей.

Составить такой план перегонок вагонов, при котором общая стоимость была минимальной.

4) Компания «Royal Wedgetoun Pottery» получила заказы на три вида выпускаемой ею продукции (бокалы, чашки и вазы), которые необходимо удовлетворить в течение следующей недели. Размеры заказов следующие:

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

Кроме того, известно, что производственные мощности станков В и С на следующую неделю составят 3000 единиц, а станка, А — 2000 единиц.

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

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

5) Компания «Orange Computer» производит только один вид продукции — матричные печатающие устройства, которые в настоящее время являются дефицитом. Четыре основных покупателя — это крупные специализированные компьютерные универмаги, расположенные в Аббатстауне, Бесвиче, Карлике и Денстоуне, уже подали заявки, общий размер которых превышает общие производственные мощности трех заводов компании в Рексфорде, Сидоне и Тристроне. Компания должна принять решение о том, как распределить производственные мощности, чтобы получить максимальную прибыль. После того, как каждый принтер тщательно упакован в мягкую упаковку, предохраняющую его от каких-либо повреждений, его помещают в отдельную коробку. В нижеследующей таблице приведены значения стоимости транспортировки одной единицы от каждого завода-производителя в каждый специализированный универмаг (ф. ст.):

Поскольку все четыре специализированных универмага расположены в различных частях страны и, следовательно, стоимость транспортировки продукции между заводами-производителями и универмагами различна, а также ввиду некоторых различий и в издержках производства каждого из четырех заводов, существующая структура цен предусматривает возможность установления различных цен для каждого из четырех универмагов. В настоящее время установлены следующие цены за единицу продукции: 230 ф. ст. в Аббатстауне, 235 ф. ст. в Бесвиче, 225 ф. ст. в Карлике и 240 ф. ст. в Денстоуне. Издержки производства на единицу продукции составляют 150 ф. ст. на заводах в Рексфорде и Тристроне и 155 ф. ст. на заводе в Сидоне.

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

Значения спроса в Аббатстауне, Бесвиче, Карлике и Денстоуне равны 850, 640, 380 и 230 единицам соответственно. Производственные мощности позволяют производить на заводе в Рексфорде 625, в Сидоне — 825, а в Тристроне — 450 принтеров. Используя алгоритм решения транспортной задачи, определить оптимальное распределение перевозок. Определить соответствующую оптимальному решению прибыль.