V. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕННЫХ НЕИЗВЕСТНЫХ

Обычно свободные члены ограничений типа трактуются как запасы ресурсов, коэффициенты перед неизвестными – как нормы затрат ресурсов на производство единицы продукции данного вида, балансовые неизвестные - как остатки ресурсов; при этом сами неравенства показывают, что общие затраты каждого ресурса не могут превышать его запаса. Функция цели z₁, максимум которой разыскивается, обычно трактуется как прибыль от реализации произведенной продукции. На основании теоремы: «Если одна задача имеет оптимальное решение, то двойственная к ней задача также имеет оптимальное решение, причем z_1max=f_2min», прибыль в оптимальном плане можно выразить через запасы ресурсов: .

Отсюда следует, что неизвестная v_i (двойственная к остатку ресурса y_i) равна первой производной от максимальной прибыли по запасу i -го ресурса и поэтому имеет такую интерпретацию: она показывает, на сколько увеличится прибыль в оптимальном плане, если увеличить запас ресурса b_i на единицу (более строго, прибыль при увеличении ресурса b_i на увеличивается на , где вариация ресурса не должна превышать некоторого допустимого предела).

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

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

Если какой-либо ресурс имеется в избытке, остаток этого ресурса отличен от нуля y_k> 0, следовательно, его двойственная неизвестная равна нулю v_k=0 и дальнейшее увеличение запаса этого ресурса не будет приводить к изменению прибыли (теневая цена данного ресурса равна нулю).

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

VI. ТРАНСПОРТНАЯ ЗАДАЧА, МЕТОДЫ ОПРЕДЕЛЕНИЯ НАЧАЛЬНЫХ ОПОРНЫХ ПЛАНОВ

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

Среди специальных задач, на практике чаще от других встречается транспортная задача, разные ее модификации и обобщения. Классическая транспортная задача – задача о наиболее экономном плане перевозки однородного продукта или взаимозаменяемых продуктов из пункта производства в пункты потребления. Рассмотрим транспортную задачу по критерию стоимости.

Пусть на m станциях отправления A₁, A₂, …, A_m сосредоточено a₁, a₂, …, a_m единиц некоторого однородного груза. Этот груз нужно перевезти в n пунктов назначения B₁, B₂, …, B_n, причем в каждый из них необходимо завезти, соответственно, b₁, b₂, …, b_n единиц этого груза. Стоимость перевозки единицы груза из пункта A_i в пункт B_j равняется c_ij, считается заданной.

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

(17)

Такую задачу называют транспортной задачей с правильным балансом. (Некоторые авторы называют транспортную задачу, в которой выполняются условия (17), закрытой или открытой – в случае невыполнения условия.) Если условие (17) нарушается, ее называют транспортной задачей с неправильным балансом. Математическая модель транспортной задачи была рассмотрена ранее.

Поскольку транспортная задача – задача линейного программирования, ее можно решить симплекс-методом. Однако из-за простоты построения системы ограничений симплекс-метод здесь намного упрощается. Рассмотрим на примере такие методы нахождения начальных опорных планов: диагональный и метод наименьшей стоимости.

Диагональный метод. Пусть транспортная задача задается матрицей перевозок (таблица 8, нижние числа).

 

Таблица 8.

Пункты поставки	Пункты потребления	Запасы
B1	B2	B3	B4	B5
A1
A2
A3
Потребности

 

Суть диагонального метода состоит в том, что ячейки, начиная с A₁B₁, последовательно заполняются значениями необходимых перевозок. Запасы A₁ – 60 ед., потребности B₁ – 22, поэтому можно завести из A₁ в B₁ 22 ед., потребности B₁ удовлетворяются. Запас A₁ уменьшился до 38 ед. Запас A₁ – 38 ед., потребности B₂ – 45 ед., завезши в пункт B₂ – 38 ед., вычерпано запасы A₁ и одновременно уменьшено потребности B₂ до 7 ед., которые удовлетворяются запасом A₂, и т.д.

Определение. Заполненные ячейки называются базисными, незаполненные – свободными.

Базисные ячейки соответствуют базисным неизвестным, свободные – сводным.

Диагональным методом найдем опорный план с базисными значениями, записанными в таблице 8. Легко подсчитать, что количество базисных ячеек равняется m+n-1, т.е. 3+5-1=7.

Примечание. Количество базисных ячеек всегда определяют как r=m+n-1. Если это условие не выполняется, то необходимо количество ячеек, которых не достает, заполнить нулями. Получим вырожденное опорное решение.

Метод наименьшей стоимости отличается от диагонального только последовательностью заполнения ячеек. Начинают заполнять те ячейки таблицы, где стоимость перевозки (записаны в каждой ячейке слева) на данном этапе минимальны (таблица 9).

Таблица 9.

Пункты поставок	Пункты потребления	Запасы
B1	B2	B3	B4	B5
A1
A2
		- 13	+
A3
		+ 7	18-
Потребности

 

Наименьшая стоимость 1 в ячейке A₁B₂, поэтому заполняем ее. Следующая минимальная стоимость 2 в ячейках A₂B₁, потом A₁B₃, A₃B₃. Ячейку A₂B₄ не заполняем, поскольку запас A₂ исчерпано. Выбираем ячейку A₃B₄ с минимальной стоимостью 4, со стоимостью 3 все ячейки заполнены. Таким образом, опорный план, найденный методом наименьшей стоимости в таблице 9, имеет вид: .

Чтобы выяснить, какой метод нахождения начальных опорных планов является наиболее эффективным, вычислим общую стоимость перевозок, найденных с помощью таблиц 8; 9:

диагональный метод

единицы;

метод наименьшей стоимости

единица.

Таким образом, наиболее близким к оптимальному плану начальный опорный план, который определен методом наименьшей стоимости. Поэтому его рекомендуется использовать на практике. Диагональный метод, как правило, используется при решении задач на ЭВМ.

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

Чтобы опорный план был оптимальным, необходимо и достаточно, чтобы выполнялись условия:

для базисных ячеек

, (18)

для свободных ячеек

(19)

где .

Рассмотрим этот метод на примере таблица 9. Поставим в соответствие пунктам A_i потенциалы - , B_j - и построим систему уравнений.

Для базисных ячеек система потенциалов имеет вид:

Возьмем =0. Тогда =1, =4, =0, =4, =2, =0, =2.

Для свободных ячеек проверяем условия:

Для ячейки A₂B₄ рассмотрим цикл перерасчета и сделаем перерасчет на величину min(13, 18)=13 – наименьшую, которая стоит в отрицательных вершинах. Получаем распределение (таблица 10).

Снова находим потенциалы , (таблица 10). Для ячеек A₃B₁ не выполняется второе условие , а именно: 0 + 4 > 3. Оптимальный опорный план (см. таблица 10) необходимо улучшить с помощью цикла перерасчета для ячейки A₃B₁ (предлагаю закончить решение задачи самостоятельно).

 

 

Таблица 10.

Пункты поставки	Запасы	Потребности bij для пункта назначения
B1	B2	B3	B4	B5
Стоимость cij перевозки
A1							=0
A2							=-2
A3							=0
		=4	=1	=2	=4	=4

 

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

Изучая этот метод, необходимо рассмотреть способы перехода к наступающему опорному плану, так чтобы значения целевой функции минимизировалось. Для перехода к новому плану используем следующие определения.

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

1. Вершина одного и того же отрезка цикла называют соседними.
2. Цикл, в соответствие соседним вершинам которого поставлены противоположные знаки «+» и «-», называют определенным.
3. Определенный цикл, одна вершина которого лежит в свободной ячейке, а все другие – в базисных, называется циклом перерасчета. Например, для ячеек A₃B₁ цикл перерасчета согласно таблицы 10 имеет вид

-

+

-

+

+

-

Договоримся, что свободные ячейки соответствуют знаку «+».

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

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

Теорема 1. Сдвиг по определенному циклу в матрице перевозок преобразует одно решение системы ограничений транспортной задачи на другое решение этой задачи.

Теорема 2. Для любой свободной ячейки существует лишь один цикл перерасчета.

Примечания:

1. Значения базисных ячеек, которые не брали участие в цикле перерасчета, в новой таблице остаются без изменений.

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

 

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

В каждой итерации этого метода необходимо выполнить два действия: 1) найти опорный план; 2) проверить его оптимальность.

На оптимальность опорный план всегда проверяют методом потенциалов, а находят его сдвигом по циклу перерасчета (кроме начального плана, который можно найти диагональным или методом стоимости).

На практике существуют транспортные задачи, в которых общая сумма запасов не равняется общей сумме потребностей; их называют транспортными задачами с неправильным балансом (открытыми).

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