Постановка задачи

Ваше производство имеет различные потребности в течение шести временных периодов. Исходные материалы, закупаемые по различной цене у двух поставщиков, должны быть запасены в количествах, достаточных для производства в различные периоды. Картину завершают затраты на хранение избытка материалов. Как вы должны решить задачу о количестве запасенных материалов, и каких поставщиков использовать, минимизируя общие затраты и обеспечив в тоже время запросы ваших потребителей?

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

Period 1 2 3 4 5 6

Demand 100 230 100 235 100 200

Поставщик 1 может обеспечить поставку 130 единиц, а поставщик 2 — 100 единиц, и затраты на хранение единицы запасов с одного периода до другого составляют 5 единиц.

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

Цель оптимизации

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

Модель

Целевая функция достаточно очевидна: сумма шести величин затрат в каждом из периодов и может быть записана как:

COST1 + COST2 + COST3 + COST4 + COST5 + COST6

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

Естественной записью этого ограничения для каждого периода будет:

COSTn = 102 * Source1Periodn + 103 * Source2Periodn + 5 * INVn

Так что ограничение для первого периода будет иметь вид:

COST1 = 102 S1P1+103 S2P1+5 EINV1

Однако, поскольку LINDO требует, чтобы переменные появлялись только в левой части ограничений, перенесем их влево с заменой знака, так что в LINDO ограничение примет вид:

COST1-102 S1P1-103 S2P1-5 EINV1 = 0

Другие ограничения на затраты соответствуют также этому формату.

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

EndingInventoryPeriod1 + Source1Period2 + Source2Period2 > 230

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

EndingInventoryPeriod1 + Source1Period2 + Source2Period2
- EndingInventoryPeriod2 > 230

Так что ограничение для этого периода запишется в виде:

EINV1 + S1P2 + S2P2 - EINV2 > 230

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

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

PurchaseSource nPeriodn < CapacitySource n

Ниже приведена результирующая модель:

MIN COST1 + COST2 + COST3 + COST4 + COST5 + COST6

SUBJECT TO

2) COST1 - 102 S1P1 - 103 S2P1 - 5 EINV1 = 0

3) COST2 - 102 S1P2 - 103 S2P2 - 5 EINV2 = 0

4) COST3 - 102 S1P3 - 103 S2P3 - 5 EINV3 = 0

5) COST4 - 102 S1P4 - 103 S2P4 - 5 EINV4 = 0

6) COST5 - 102 S1P5 - 103 S2P5 - 5 EINV5 = 0

7) COST6 - 102 S1P6 - 103 S2P6 - 5 EINV6 = 0

8) S1P1 + S2P1 - EINV1 >= 100

9) EINV1 + S1P2 + S2P2 - EINV2 >= 230

10) EINV2 + S1P3 + S2P3 - EINV3 >= 100

11) EINV3 + S1P4 + S2P4 - EINV4 >= 235

12) EINV4 + S1P5 + S2P5 - EINV5 >= 100

13) EINV5 + S1P6 + S2P6 - EINV6 >= 200

14) S1P1 <= 130

15) S2P1 <= 100

16) S1P2 <= 130

17) S2P2 <= 100

18) S1P3 <= 130

19) S2P3 <= 100

20) S1P4 <= 130

21) S2P4 <= 100

22) S1P5 <= 130

23) S2P5 <= 100

24) S1P6 <= 130

25) S2P6 <= 100

END

После нажатия кнопки Solve получим решение:

LP OPTIMUM FOUND AT STEP 22

OBJECTIVE FUNCTION VALUE

1) 98725.00

VARIABLE VALUE REDUCED COST

COST1 10200.000000.000000

COST2 23560.000000.000000

COST3 10735.000000.000000

COST4 23560.000000.000000

COST5 10200.000000.000000

COST6 20470.000000.000000

S1P1 100.000000.000000

S2P1.000000 1.000000

EINV1.000000 4.000000

S1P2 130.000000.000000

S2P2 100.000000.000000

EINV2.000000 6.000000

S1P3 105.000000.000000

S2P3.000000 1.000000

EINV3 5.000000.000000

S1P4 130.000000.000000

S2P4 100.000000.000000

EINV4.000000 10.000000

S1P5 100.000000.000000

S2P5.000000 1.000000

EINV5.000000 4.000000

S1P6 130.000000.000000

S2P6 70.000000.000000

EINV6.000000 108.000000

ROW SLACK OR SURPLUS DUAL PRICES

2).000000 -1.000000

3).000000 -1.000000

4).000000 -1.000000

5).000000 -1.000000

6).000000 -1.000000

7).000000 -1.000000

8) -.000000 -102.000000

9) -.000000 -103.000000

10) -.000000 -102.000000

11) -.000000 -107.000000

12) -.000000 -102.000000

13) -.000000 -103.000000

14) 30.000000.000000

15) 100.000000.000000

16).000000 1.000000

17).000000.000000

18) 25.000000.000000

19) 100.000000.000000

20).000000 5.000000

21).000000 4.000000

22) 30.000000.000000

23) 100.000000.000000

24).000000 1.000000

25) 30.000000.000000

26)

NO. ITERATIONS= 22

Общие затраты на приобретение запасов минимизированы до 98,725. Отметим, что из переменных EINV только EINV3 имеет ненулевое значение, указывая на то, что только в третьем периоде следует сделать дополнительный запас, переходящий на следующий период.

Простая сеть линейного программирования (ЛП)

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

Постановка задачи

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

Цель оптимизации

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

Модель

Целевая функция строится из условия минимизации (MIN) суммы затрат на перевозку по каждой «дуге». Термин «дуга» является обычным для путей, соединяющих точки сети. Эти точки в сети обычно называют «узлами». Мы обозначим узел первого склада (Warehouse1) например переменной WH1, а узел первого потребителя (customer1) именем C1. Количество перевозимого товара с первого склада к первому потребителю обозначим как «XWH1C1».

Ограничения имеют двоякий характер. Во-первых, общее количество товара, доставляемого к каждому из потребителей должно быть не меньше его потребностей. Так, например, для первого потребителя (Customer 1) величина (XWH1C1+ XWH2C1+ XWH3C1) должна быть больше или равна 15. Это отражено в строке с меткой C1.

Во-вторых, количество вывозимого товара с каждого из складов не может превышать его запасов. Так, общее количество товара, вывозимого с первого (Warehouse 1) склада, равное (XWH1C1+ XWH1C2+ XWH1C3+ XWH1C4) не может быть больше 30. Это отражено в строке с меткой WH1.

В итоге вся модель выглядит так:

MIN 6 XWH1C1 + 2 XWH1C2 + 6 XWH1C3 + 7 XWH1C4 + 4 XWH2C1

+ 9 XWH2C2 + 5 XWH2C3 + 3 XWH2C4 + 8 XWH3C1

+ 8 XWH3C2 + XWH3C3 + 5 XWH3C4

SUBJECT TO

C1) XWH1C1 + XWH2C1 + XWH3C1 >= 15

C2) XWH1C2 + XWH2C2 + XWH3C2 >= 17

C3) XWH1C3 + XWH2C3 + XWH3C3 >= 22

C4) XWH1C4 + XWH2C4 + XWH3C4 >= 12

WH1) XWH1C1 + XWH1C2 + XWH1C3 + XWH1C4 <= 30

WH2) XWH2C1 + XWH2C2 + XWH2C3 + XWH2C4 <= 25

WH3) XWH3C1 + XWH3C2 + XWH3C3 + XWH3C4 <= 21

END

После нажатия кнопки Solve, получим решение:

LP OPTIMUM FOUND AT STEP 6

OBJECTIVE FUNCTION VALUE

1) 161.0000

VARIABLE VALUE REDUCED COST

XWH1C1 2.000000.000000

XWH1C2 17.000000.000000

XWH1C3 1.000000.000000

XWH1C4.000000 2.000000

XWH2C1 13.000000.000000

XWH2C2.000000 9.000000

XWH2C3.000000 1.000000

XWH2C4 12.000000.000000

XWH3C1.000000 7.000000

XWH3C2.000000 11.000000

XWH3C3 21.000000.000000

XWH3C4.000000 5.000000

ROW SLACK OR SURPLUS DUAL PRICES

C1) -.000000 -6.000000

C2) -.000000 -2.000000

C3) -.000000 -6.000000

C4) -.000000 -5.000000

WH1) 10.000000.000000

WH2).000000 2.000000

WH3).000000 5.000000

NO. ITERATIONS= 6

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

Дата добавления: 2015-11-16