Экономический смысл двойственности.

 

3.3. Экономический смысл двойственной задачи

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

,

,

,

где b _i – лимит i -го ресурса на предприятии,

a _ij – расход i -го ресурса на единицу j -го вида продукции,

c _j – прибыль от реализации одной единицы j -го вида продукции,

n – количество изделий которые может выпустить предприятие,

m – количество ресурсов,

x _j – количество продукции j -го вида в плане.

Заметим, что задача формирования плана является ЗЛП в симметричной форме, поэтому двойственная к ней задача имеет вид

,

,

.

Для того, чтобы понять экономический смысл двойственности введем наименование всех параметров исходной задачи.

,

,

,

,

и так как в двойственной задачи наименование левой и правой частей должны совпадать

откуда .

Таким образом, переменная получает наименование цены единицы ресурса. Однако надо помнить, что двойственная переменная есть цена ресурса только в рамках рассматриваемой задачи, поэтому лауреатом Нобелевской премии Канторовичем Л. В. Двойственные переменные были названы объективно обусловленными оценками. Кроме того так как на оптимальном решении

,

,

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

 

Транспортная задача. Постановка, модель, несбалансированные транспортные задачи, задачи с запретами.

 

§4. Транспортная задача

4.1. Математическая модель транспортной задачи

Построение транспортной задачи и ее вербальная модель были представлены в первой главе.

Напомним математическую модель транспортной задачи:

, (1)

, (2)

, (3)

. (4)

Ограничение (1) и (2) означают, что от каждого поставщика должна быть вывезена вся продукция, а каждый потребитель должен быть удовлетворен.

Кроме того предполагается выполнение условия баланса

.

Как видно из математической модели транспортная задача представляет собой ЗЛП в канонической форме, имеющую () ограничений и () переменных. То есть транспортная задача даже при небольшом количестве поставщиков и потребителей оказывается достаточно громоздкой и ее решение с помощью обычного симплекс-метода хотя и возможно, но требует значительных информационных и временных ресурсов. Однако, с учетом специфики системы ограничений, формулы симплекс-метода значительно упрощаются. Модифицированный с учетом структуры матрицы симплекс-метод называется методом потенциалов и будет рассматриваться позже.

 

 

Способ задания

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

Заметим, что условие неотрицательности переменных в таблице не отражается, так как является выполненным для всех ЗЛП. Что же касается транспортной задачи, то - столбцы ее матрицы ограничений имеют «длину» () и состоят из двух блоков. Первый блок «длины» m имеет единицу на месте i и нули на остальных местах, а второй блок «длины» n имеет единице на месте j и нули на остальных:

.

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

 

Рис. 1.

Допустимое решение , также заносится в матрицу размером (). При этом i -я строка соответствует i -му ограничению (1), а j -й столбец – j -му ограничению (2) откуда следует, что сумма элементов i -й строки матрицы X равна , сумма всех элементов j -го столбца – равна .

Рис. 2.