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