3.4. Экономическое содержание двойственности

Основа планово-экономических задач: при ограниченных ресурсах достигнуть наилучшего экономического эффекта.

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

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

Рис. 3.2. Пример работы программы RAND4x6 (DOS-версия)

Виды и количество отходов обозначим через множество Q:

Q={q₁;q₂;…q_j;…q_n},

где q_j – количество q_j для j–го вида отходов.

Виды и количество вторичных изделий обозначим через X:

X={x₁; x₂;…x_i;…x_m},

где {x_i} – неизвестные нам количества, подлежащие планированию.

Стоимость единицы отхода также неизвестна, обозначим ее через y={y₁; y₂;…y_j;…y_n}.

Неизвестная прибыль от прямой продажи отходов может составить .

Выбрасывая отходы, мы получаем минимальную прибыль, равную нулю. Желательно увеличить эту прибыль за счет вторичного производства.

Пусть имеются инвестиционные проекты на X видов вторичных изделий или способов использования отходов, по которым известна матрица удельных расходов A=[a_ij] и отходов Q на единицу изделия x_iX.

Маркетинг показывает нам рыночную стоимость одного изделия x_iX. Пусть она равна b_iB:

B={b₁; b₂;…b_i;…b_m}.

С учетом введенных обозначений получаем таблицу типа транспортной.

Из последней на алгебраическом уровне абстрагирования формируется следующая двойственная пара задач:

1. суммы по столбцам определяют ОДР – X:

;

–

задача максимизации прибыли от вторичного использования отходов;

2. суммы по строкам определяют ОДР – Y:

;

–

задача минимизации расходов покупателя отходов.

Упражнение

Требуется:

1. Составить двойственную пару задач.

Решение:

1.1.

1.2.

ОДР – X

w20x₁+30x₂

1.3.

ОДР – Y

r15y₁+18y₂+16y₃+8y₄ .

Задание на самостоятельную проработку:

1) Решить задачу п.1.2 графически и алгебраически (путем уточнения координат точек решения). Решение этой задачи рекомендуется проделать самостоятельно.

2) Решить самостоятельно задачу п.1.3, используя табличный алгоритм замены переменных и симплекс-метод.

3) Сравнить результаты решения двойственной пары задач. Проверить выполнение общих свойств двойственности ЗЛП в данном конкретном случае.

4) Дать инвестиционную интерпретацию и составить конкретное описание задачи на знаково-лингвистическом уровне в случае:

(b₁; b₂) – удельная стоимость единичного изделия от реализации проектов (x₁; x₂);

(y₁; y₂; y₃; y₄) – удельная цена составляющих элементов проектов (x₁; x₂);

(q₁; q₂) – объемы инвестиций, предусмотренные на реализацию проектов (x₁; x₂) (активы);

[a_ij] – удельные расходы количеств элементов на реализацию проектов (x₁; x₂);

w – ожидаемая эффективность проекта;

r – эффективность от прямой реализации составляющих проекта;

w=r – условие определения стоимости элементов, определяемая от потребительской стоимости проектов (b₁; b₂) при их реализации в объемах (x₁; x₂).

4. Транспортная задача (ТЗ)

линейного программирования

4.1. Составление опорного плана ТЗ

по методу северо-западного угла (СЗУ)

Название этого метода связано с особой разметкой транспортной таблицы: стороны таблицы называют по сторонам света (верхняя – северная, нижняя – южная), а углы соответственно помечают как промежуточные направления (левый верхний – северо-западный угол или СЗУ и т.д.) (табл. 4.1).

Составление опорного плана начинают с СЗУ таблицы – заполняют клетку A₁ B₁ меньшим из чисел a₁ и b₁, т.е. x₁₁ = min {a₁, b₁}. От соотношения a₁ и b₁ зависит последовательность заполнения таблицы:

• Если a₁ > b₁ , то x₁₁ = b₁ – это значит, что заявка потребителя B_{1 ­}удовлетворена полностью. В этом случае говорят, что столбец B₁ «закрыт» и переходят к заполнению клетки A₁B₂ (т.е. передвигаются по строке вправо, к следующему потребителю). При этом x₁₂ = min {a₁ – b₁, b₂}.

• Если a₁ < b₁, то запасы поставщика A₁ исчерпаны (строка A₁ «закрыта»), а заявка потребителя B₁ удовлетворена не полностью. Поэтому, чтобы закончить обслуживание заявки B₁, переходим к клетке A₂ B₁ (т.е. к следующему поставщику) и записываем в нее значение x₂₁ = min {a₂, b₁ – a₁}.

• Если a₁= b₁, то закрываем строку A₁ и строку B₁, а затем переходим к клетке A₂ B₂.

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

Надо сказать, что название метода достаточно условно, поскольку заполнение таблицы можно начинать с любого угла.

В табл. 4.1-4.2 показано начало решения задачи – обслуживание потребителей B₁ и B₂. Результат решения задачи приведен в табл. 4.3.