Грицюк С.Н., Мирзоева Е.В., Лысенко В.В. Математические методы и модели в экономике

Подождите немного. Документ загружается.

10

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

2. Составляем расширенную матрицу системы ,

в которую включаем матрицу A, столбец свободных

членов и строку с функцией F:

3. Найдем :

Меняем F на Z, так как будет другая задача, а сле-

довательно, и другая целевая функция.

4. Сформулируем двойственную задачу:

при ограничениях:

Связь между оптимальными решениями двойствен-

ных задач устанавливается с помощью теорем двойс-

твенности.

11

Математические методы и модели в экономике

Теорема (достаточный признак оптимальности)

Если X

= (x

, x

, ..., x

) и Y

= (y

, y

, ..., y

)

допустимые решения взаимодвойственных задач,

для которых выполняется равенство F(X

) = Z(Y

то X

— оптимальное решение исходной задачи I, а

— оптимальное решение двойственной задачи II.

Первая (основная) теорема двойственности

Если одна из взаимодвойственных задач имеет оп-

тимальное решение, то его имеет и другая задача,

причем

Если линейная функция одной из задач не ограни-

чена, то условия другой задачи противоречивы.

Экономический смысл первой теоремы

двойственности

План производства X

= (x

, x

, ..., x

) и набор

цен (оценок) ресурсов Y

= (y

, y

, ..., y

) оказыва-

ются оптимальными тогда, когда прибыль (выручка)

от продукции, найденная при известных заранее це-

нах c

, c

, ..., c

, равна затратам на ресурсы по це-

нам y

, y

, ..., y

(определяемых только из решения

задачи).

То есть предприятию безразлично, производить

ли продукцию по оптимальному плану X

= (x

, x

..., x

) и получить максимальную прибыль F

max

либо

продавать ресурсы по оптимальным ценам Y

= (y

, ..., y

) и возместить от продажи равные ей (при-

были) минимальные затраты на ресурсы Z

min

Тесная связь между двумя взаимно двойственны-

ми задачами проявляется не только в равенстве опти-

мальных значений их линейных функций, о чем ут-

верждалось в первой (основной) теореме.

Рассмотрим две взаимно двойственные задачи I и II:I и II: и II:II::

I II

12

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

при ограничениях: при ограничениях:

Если каждую из них решать симплексным методом,

то необходимо привести их к каноническому виду, для

чего в систему ограничений (I) вводят m неотрица-

тельных переменных x

n+1

, x

n+2

, ..., x

n+m

, а в систему

ограничений (II) n неотрицательных переменных y

n+1

n+2

, ..., y

n+m

, где i(j) — номер неравенства, в кото-

рое ввели данную переменную. Система ограничений

каждой из задач примет вид:

Между первоначальными переменными одной из

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

ми другой задачи устанавливаются следующие соот-

ветствия.

Таблица 4.55

Переменные исходной задачи (I)I))

Первоначальные

(по условию)

Дополнительные

… x

m+1

m+2

… x

m+j

… x

m+n

 

…



…

  

…



…



m+1

m+2

… y

m+j

… y

m+n

… y

Дополнительные Первоначальные (по условию)

Переменные двойственной задачи (II)II)

1

Математические методы и модели в экономике

Теорема

Положительным (ненулевым) компонентом опти-

мального решения одной из взаимодвойственных за-

дач соответствуют ненулевые компоненты оптималь-

ного решения другой задачи, то есть для любых i = 1,

2, …,m и j = 1, 2, …,n,

если x

> 0, то y

m+j

= 0;

n+1

> 0, то y

= 0;

аналогично:

если y

> 0, то x

n+i

= 0;

m+j

> 0, то x

= 0.

Таким образом, эта теорема позволяет определить

решение одной из пары двойственных задач по реше-

нию другой.

Пример

Рассмотрим задачу об использовании ресурсов, ре-

шенную симплексным методом.

Выпишем последнюю таблицу симплексного мето-

да для исходной задачи (см. таблицу 4.6).

Таблица 4.6

Основные Дополнительные

базис b

6 1 0 –1/5 3/5 0 0

1 0 0 –2/5 1/5 1 0

1

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

4 0 1 2/5 –1/5 0 0

3 0 0 3/5 –9/5 0 1

F 24 0 0 4/5 3/5 0 0

Z y

Дополнительные Основные

Значит:

Компоненты оптимального решения двойственной

задачи называются объективно обусловленными

оценками.

Объективно обусловленные оценки ресурсов опреде-

ляют степень дефицитности ресурсов: по оптимально-

му плану производства дефицитные (то есть полностью

используемые) ресурсы получают ненулевые оценки,

а недефицитные — нулевые оценки. К тому же, объ-

ективно обусловленные оценки ресурсов показывают,

на сколько денежных единиц изменится максимальная

прибыль от реализации продукции при изменении за-

паса соответствующего ресурса на одну единицу.

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

выражают превышение затрат над ценой.

4.2. Транспортные задачи линейного

программирования

4.2.1. �остановка и типы

транспортных задач

Простейшими транспортными задачами являются

задачи о перевозках некоторого однородного груза

из пунктов отправления (от поставщиков) в пункты

назначения (к потребителям при обеспечении мини-

мальных затрат на перевозки).

1

Математические методы и модели в экономике

Рассмотрим такую задачу.

Имеется m поставщиков A

и n потребителей B

Количество груза, находящегося у потребителя A

будем обозначать через . Количество груза,

необходимое потребителю B

— через . Дана

матрица тарифов (издержек или транспортных

расходов).

где с

— стоимость перевозки единицы груза от i-го

поставщика к j-му потребителю.

Планом транспортной задачи называется матрица

где x

обозначает количество груза, которое надо

доставить от i-го поставщика к j-му потребителю.

Общие суммарные затраты, связанные с реали-

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

функцией:

Математическая модель задачи выглядит так:

при ограничениях:

(4.19)

(4.20)

1

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Система ограничений (4.21) содержит m + n урав-

нений с m · n переменными.

Если суммарный объем груза поставщиков равен

суммарному спросу потребителей, то есть

то это транспортная задача с закрытой моделью.

А если или , то это транс-

портная задача с открытой моделью.

Равенство (4.22) является необходимым и доста-

точным условием совместности ограничений задачи.

Для транспортной задачи важное значение имеет

теорема о ранге матрицы.

Теорема

Ранг матрицы транспортной задачи на единицу

меньше числа уравнений, то есть

С учетом этой теоремы в каждой матрице перевозок

опорный план должен содержать не более m + n – 1

занятых клеток, а остальные — свободные.

4.2.2. Методы построения начального

опорного решения

1. Метод северо-западного угла

Существует ряд методов построения начального

опорного решения, наиболее простым из которых яв-

(4.21)

(4.22)

(4.23)

1

Математические методы и модели в экономике

ляется метод северо-западного угла. В данном методе

запасы очередного поставщика используются для обес-

печения запросов очередных потребителей до тех пор,

пока не будут исчерпаны полностью, после чего исполь-

зуются запасы следующего по номеру поставщика.

Заполнение таблицы транспортной задачи начина-

ется с левого верхнего угла и состоит из ряда одно-

типных шагов. На каждом шаге, исходя из запасов

очередного поставщика и запросов очередного потре-

бителя, заполняется только одна клетка и, соответс-

твенно, исключается из рассмотрения один поставщик

или потребитель.

2. Метод минимального элемента

(минимальной стоимости)

Метод минимальной стоимости прост, он позволяет

построить опорное решение, достаточно близкое к оп-

тимальному, так как использует матрицу стоимостей

транспортной задачи С = (с

), i = 1, 2, …, m, j = 1, 2,i = 1, 2, …, m, j = 1, 2, = 1, 2, …, m, j = 1, 2,m, j = 1, 2,, j = 1, 2,j = 1, 2, = 1, 2,

…, n.n.. Как и метод северо-западного угла, он состоит

из ряда однотипных шагов, на каждом из которых за-

полняется только одна клетка таблицы, соответству-

ющая минимальной стоимости , и исключает-

ся из рассмотрения только одна строка (поставщик)

или один столбец (потребитель). Очередную клетку,

соответствующую , заполняют по тем же пра-

вилам, что и в методе северо-западного угла. Постав-

щик исключается из рассмотрения, если его запасы

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

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

полностью. На каждом шаге исключается либо один

поставщик, либо один потребитель. При этом если

поставщик еще не исключен, но его запасы равны

нулю, то на том шаге, когда от данного поставщика

требуется поставить груз, в соответствующую клетку

таблицы заносится базисный нуль и лишь затем пос-

тавщик исключается из рассмотрения. Аналогично с

потребителем.

1

С. Н. Грицюк, Е. В. Мирзоева, В. В. Лысенко

Пример

Имеется три поставщика А

, А

и А

, а также че-

тыре потребителя В

, В

и В

Количество груза,

находящегося у потребителей, равно соответственно:

= 60 т, a

= 40 т и a

= 35 т. Количество груза, не-

обходимого потребителю B

, равно соответственно:

= 40 т, b

= 25 т, bb

= 20 т и bb

= 50 т. Дана матрица

тарифов (издержек или транспортных расходов):

Решение

Так как , то данная задача — закры-

того типа. Составим первоначальный опорный план

двумя различными способами.

1. Способ северо-западного углаСпособ северо-западного угла

Таблица 4.�

–

60, 20, 0

–

40, 35, 15

–

35, 0

40,0

25, 5, 0

20, 0

50, 35, 0

1

Математические методы и модели в экономике

2. Способ минимального элемента

Таблица 4.�

–

60, 40, 0

–

10 40, 15, 5

–

35, 0

40, 35, 0

25, 0

20, 0 50, 10, 0

Таким образом, опорный план, найденный способом

минимального элемента, ближе к оптимальному, чем

план, найденный способом северо-западного угла.

4.2.3. Метод потенциалов

Для решения транспортной задачи методом потен-

циалов необходимо:

1) получить опорный план перевозок по одному из

известных способов;

2) вычислить потенциалывычислить потенциалы α

и β

— соответственно

поставщиков и потребителей;

3) вычислить сумму потенциалов (косвенные тари-вычислить сумму потенциалов (косвенные тари-

фы) для свободных клеток:

4) проверить разность, (то есть вычислить оценкипроверить разность, (то есть вычислить оценки

свободных клеток):

Если все , то полученный план оптимальный.

Если хотя бы одна оценка , то строится цикл