Оптимизация транспортировки линейным программированием с ограничениями по процедуре

Я пытаюсь решить типичную транспортную задачу с помощью оптимизации (минимизации транспортных расходов) в GLPK или R.

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

Пример:

production (id, province, tons)
            1  A      300
            2  A      800
            3  B      800
            4  B     1200

    export (id, sourcing_province, tons)
            5  A      400
            5  B      600
            6        2000

    routes (id_orig, id_dest, cost) 
               1  5  5.1
               1  6  3.2
               2  5  6.7
               2  6  7.2
               3  5  2.8
               3  6  4.1
               4  5  6.9
               4  6  5.3

Однако есть дополнительные ограничения, усложняющие проблему: я знаю, что экспортер (5) на самом деле получает определенное фиксированное количество из каждой провинции. В частности, в приведенном выше примере экспортер (5) должен получить 400 тн из провинции А и 600 тн из провинции Б. У экспортера (6) нет ограничений, он может закупать товары из любой провинции. Я не нахожу способа выразить эти ограничения.

Не могли бы вы мне помочь?


r glpk restriction linear-programming
person user12975    schedule 14.02.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Вы можете рассмотреть свою проблему с точки зрения краев. Если 1, 2, 3, 4 — производители, а 5,6 — экспортеры, пусть e15 — это поток от производителя 1 к экспортеру 5, e25 — от производителя 2 к экспортеру 5 и так далее.

С этим обозначением проблема становится:

/* Objective function */
min: 5.1 e15 + 3.2 e16 + 6.7 e25 + 7.2 e26 + 2.8 e35 + 4.1 e36 + 6.9 e45 + 5.3 e46;

/* production limits */
e15 + e16 <= 300;
e25 + e26 <= 800;
e35 + e36 <= 800;
e45 + e46 <= 1200;

/* demand */
e15 + e25 + e35 + e45 >= 1000;
e16 + e26 + e36 + e46 >= 2000;

/* exporter 5 restrictions   */
e15 + e25 >= 400;
e35 + e45 >= 600;

Последние два неравенства являются фиксированными количественными ограничениями.

Вы можете использовать LpSolve для решения этой проблемы. Для этого также существует пакет R lpsolveAPI. Приведенная выше формулировка проблемы уже находится в формате LP.

person Karsten W.    schedule 14.02.2014
comment
Что делать, если количество ограничений слишком велико, чтобы прописывать их вручную? Я привел только пример, но реальный случай включает в себя тысячи производителей, сотни экспортеров и несколько сотен ограничений. Могу ли я назвать все эти ограничения простым способом, используя матрицу ограничений? - person user12975; 14.02.2014
comment
Конечно! Ограничениями для lpsolve являются время вычислений и память вашего компьютера. См. пакет lpsolveAPI для программной настройки таблицы. - person Karsten W.; 14.02.2014