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

 

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

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

,

,

,

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

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

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

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

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

xj – количество продукции 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.