<<
>>

2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

З а д а ч а 2.1. Компания с ограниченной ответственностью осуществляет производство прохладительных напитков на двух заводах - А и В. Поставкой бутылок на каждый из заводов занимаются две фирмы P и Q. На ноябрь заводу требуется 5000 бутылок, а заводу В - 3500 бутылок. Фирма Р может поставить максимум 7500 бутылок, а фирма Q - 4000 бутылок.

2.1 П Стоимость перевозки бутылок, показатели спроса и предложения Поставщик Стоимость перевозки одной бутылки на завод, пенсов Максимальный А В объем поставки Р 4 4 7500 Q 3 2 4000 СПРОС НА БУТЫЛ 5000 3500 КИ Как следует организовать доставку бутылок на заводы, чтобы общая стоимость перевозки была минимальна?

Решение

Пусть фирма Р поставляет х бутылок для завода А и у бутылок для завода В. Фирма Q поставляет а бутылок заводу а и ь бутылок заводу В. Целевая функция с учетом приведенных в таблице затрат на перевозку будет иметь вид:

С = 4х + 4y + 3a + 2b.

Выразим ограничения через переменные:

* Данная задача не удовлетворяет предпосылкам транспортной задачи, но может быть преобразована в транспортную.

х + y < 7500, a + b < 4000, a + х = 5000, y + b = 3500.

Решая задачу с помощью прикладной программы для ЭВМ, получаем следующий результат.

х = 4500.0000, a = 500.0000, b = 3500.0000. Значение целевой функции (оптимальное) 26500.0000. Анализ ограничений и теневые цены:

Огр: х + y < 7500

4500.0000 <= 7500.0000 ==> 0.00000

4000.0000 <= 4000.0000 ==> 0.000000

5000.0000 = 5000.0000 ==> -4.000000

Огр: a + b < 4000 Огр: a + х = 5000 Огр: y + b = 3500

3500.0000 = 3500.0000 ==> -3.000000.

Данная задача после некоторого преобразования может быть решена графически.

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

За дача 2.2. Некоторый продукт производится на двух заводах и распределяется между двумя пользователями. Их потребности на ближайшие два месяца приведены в таблице:

2.2П Потребности на ближайшие два месяца Пользователь Потребность август сентябрь 1 420 550 2 350 480 Стоимость транспортировки продукта с заводов потребителям приведена в таблице:

2.3П Стоимость транспортировки продукта с заводов потребителям Завод Пользователь 1 2 1 10 13 2 12 6 Стоимость производства единицы продукта и объем производства по плану за два месяца приведены в таблицах.

2.4П Объем производства по плану за два месяца Завод Объем производства август сентябрь 1 500 600

300

2

500

2.5П Стоимость производства единицы продукта за два месяца Завод Объем производства август сентябрь 1 3,0 3,6 2 3,2 2,9

При этом возможно производить продукт в течение месяца, хранить его лишь в течение месяца, а затем отправлять пользователю. Стоимость хранения составляет 0,5 на заводе 1 и 0,6 на заводе 2.

Решение

Сформулируем задачу как задачу линейного программирования. Введем необходимые переменные.

z1p1a

z1p2a

z2p1a

z2p2a

z1p1s

z1p2s

z2p1s

z2p2s

c1a c2a

1

количество продукта, поставляемое заводом пользователю 1 в августе;

количество продукта, поставляемое заводом 1 пользователю 2 в августе;

количество продукта, поставляемое заводом 2 пользователю 1 в августе;

количество продукта, поставляемое заводом 2 пользователю 2 в августе;

количество продукта, поставляемое заводом 1 пользователю 1 в сентябре;

количество продукта, поставляемое заводом 1 пользователю 2 в сентябре;

количество продукта, поставляемое заводом 2 пользователю 1 в сентябре;

количество продукта, поставляемое заводом 2 пользователю 2 в сентябре;

количество продукта, поступившего на склад завода

в августе;

количество продукта, поступившего на склад завода

в августе;

z1a - количество продукта, произведенного заводом 1 в августе;

z1s - количество продукта, произведенного заводом 1 в сентябре;

z2a - количество продукта, произведенного заводом 2 в августе;

z2s - количество продукта, произведенного заводом 2 в сентябре.

Целевая функция будет иметь вид:

С = z1p1a Ф 10 + z2p1a Ф 12 + z1p1s Ф 10 + z2p1s Ф 12 + + z1p2a Ф 13 + z2p2a Ф 6 + z1p2s Ф 13 + z2p2s Ф 5 + z1a Ф 3 + + z2a Ф 3.2 + z1s Ф 3.6 + z2s Ф 2.9 + c1a Ф 0.5 + c2a Ф 0.6. Ее значение необходимо минимизировать. Введем следующие ограничения.

z1p1a+z2p1a=420 z1p1s+z2p1s=550 z1p2a + z2p2a = 350

z1p2s+z2p2s=480 z1a<500 z1s<600 z2a< 300 z2s < 500 c1a = z1a - z1p1a - z1p2a c2a = z2a - z2p1a - z2p2a z1s = z1p1s - z1p2s - c1a z2s = z2p1s + z2p2s - c2a С помощью прикладной программы для ЭВМ получаем следующее решение:

Отчет о решении задачи линейной оптимизации

Замечание Переменная Значение z1p1a 420.0000 z1p2a 50.000000 z2p1a 0.00000 z2p2a 300.0000 z1p1s 550.0000 z1p2s 0.00000 z2p1s 0.00000 z2p2s 480.0000 c1a 30.000000 c2a 0.00000 z1a 500.0000 z1s 520.0000 z2a 300.0000 z2s 480.0000 Значение целевой функции (оптимальное) 20289.0000 Анализ ограничений и теневые цены:

420.0000 = 420.0000 ==> -13.100000

550.0000 = 550.0000 ==> -13.600000

350.0000 = 350.0000 ==> -16.100000

480.0000 = 480.0000 ==> -7.900000

500.0000 <= 500.0000 ==> 0.1000000

520.0000 <= 600.0000 ==> 0.00000

300.0000 <= 300.0000 ==> 6.900000

480.0000 <= 500.0000 ==> 0.00000

Огр: z1p1a + z2p1a = 420 Огр:z1p1s+z2p1s=550 Огр: z1p2a + z2p2a = 350 Огр:z1p2s+z2p2s=480 Огр: z1a < 500 Огр: z1s < 600 Огр: z2a < 300 Огр: z2s < 500

Огр:c1a = z1a - z1p1a - z1p2a

30.000000 = 30.000000 ==> 3.100000

Огр: c2a = z2a - z2p1a - z2p2a

0.00000 = 0.00000 ==> 10.100000

Огр: z1s = z1p1s + z1p2s - c1a

520.0000 = 520.0000 ==> -3.600000

Огр: z2s = z2p1s + z2p2s - c2a

480.0000 = 480.0000 ==> -2.900000 Итоговая таблица оптимального плана производства и транспортировки выглядит следующим образом.

2.6П Оптимальный плана производства и транспортировки Август Сентябрь Пользователь Пользователь Склад Пользователь 1 2 1 2 1 420 50 30 30 + 520 0 2 0 300 0 0 480 Итого 420 350 - 550 480

<< | >>
Источник: Мешкова Л. Л., Белоус И. И., Фролов Н. М.. Логистика в сфере материальных услуг (На примере снабженческо-заготовительных и транспортных услуг). 2-е изд. испр. и перераб. Тамбов: Изд-во Тамб. гос. техн. ун-та,2002. 188 с.. 2002

Еще по теме 2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ:

  1. 1.3.3. Использование методов анализа сигналов для решения задачи поиска «цели»
  2. 2 ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  3. 2.1 РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  4. 2.2 АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
  5. 2.3 Модификации транспортной задачи
  6. 2П ТРАНСПОРТНАЯ ЗАДАЧА И ЗАДАЧА О НАЗНАЧЕНИЯХ: АЛГОРИТМЫ РЕШЕНИЯ
  7. 2.1П РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ИСПОЛЬЗОВАНИЕМ МЕТОДОВ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
  8. 2.2П АЛГОРИТМЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ
  9. 1.Метод линейного программирования.
  10. 7.6. Методы нахождения опорного решения задачи линейного программирования