Некоторые применения теории двойственности при решении задач линейного программирования

Бюллетень науки и практики / Bulletin of Science and Practice

УДК 37                                             

В настоящее время умение применять теоретические знания при решении практических задач становится решающим фактором для изучения дисциплины. В частности, исходя из многолетнего опыта преподавания практической математики в экономическом ВУЗе, авторам представляется необходимым продемонстрировать решение некоторых экономических задач при помощи математического аппарата [1].

Если мы не сможем улучшить математическое образование, учитывая потребности современного мира и студентов, мы находимся в опасности превращения математики во все более «мертвый язык» и отчуждения групп студентов, математический потенциал которых останется неразвитым [2].

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

Методам линейного программирования посвящено много фундаментальных работ. Математик Дж. Данциг ввел понятие линейного программирования и предложил в 1949 г. алгоритм, получивший название симплексный метод. С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной. Первоначальная задача называется исходной. Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Исходная и двойственная задачи тесно связаны между собой и образуют единую пару двойственных задач.

С

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

Двойственные задачи и их экономический анализ. Рассмотрим задачу об b (i = 1, m) использовании ресурсов. Предприятие имеет m видов ресурсов в количестве i единиц, из которых производится n видов продукции. Для производства единицы j –й продукции расходуется aij единиц i – го ресурса, а ее стоимость составляет Сj единиц.

Составить план выпуска продукции, обеспечивающий максимальный выпуск в стоимостном выражении.

X ( ^j = 1, ⁿ )

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

Найти вектор X = ( x1, x2,■■■, xn), координаты которого удовлетворяют ограничениям a11 x1 + a12x2 + ••• + a1 nxn ^ b1

a₂X + a₂₂x₂ + ... + a_2nx„ <  b₂

. a m 1 x 1 + a m 2 x 2 + ... + a mn x n ^ ^bm

X j - 0 ( j = 1, n )

и доставляют максимальное значение линейной функции Z = C ¹ x ¹ + C ^{2 x 2} + "• + Cx

Оценим ресурсы, необходимые для изготовления продукции. За единицу стоимости y i ( i = 1, m ) ресурсов примем единицу стоимости выпускаемой продукции. Обозначим через

Бюллетень науки и практики / Bulletin of Science and Practice Т. 8. №5. 2022 стоимость единицы i –го ресурса. Тогда двойственную задачу линейного программирования можно сформулировать следующим образом.

Найти вектор Y = ⁽ y¹, y 2 ,.", y m ) , координаты которого удовлетворяют ограничениям 'a ll У 1 + a 21 У 2 + - + a m 1 У т >  с 1

<

a 12 У 1 + a 22 У 2 + - + a m 2 У т >  с 2

. a 1 п У 1 + a 2 п У 2 + - + ^атп У т >  с п

У, >  0 ( i = 1, т )

и доставляют минимальное значение линейной функции

^S = ^Ь 1 У 1 + ^Ь 2 У 2 + - + ^Ь т У т

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

X ( j = 1, п )

Исходная задача. Сколько и какой продукции j         необходимо произвести, с (j = 1,П)

чтобы при заданных стоимостях j        единицы продукции и размерах имеющихся b (i = 1, m)

ⁱ       ресурсов максимизировать выпуск продукции в стоимостном выражении.

Двойственная задача. Какова должна быть цена единицы каждого из ресурсов, чтобы

С ( j = m) при заданных количествах ресурсов и величины стоимости единицы продукции ^j минимизировать общую стоимость затрат.

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

Симметричные и несимметричные двойственные задачи и их математические модели.

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

L(x) = Cx + C2x2 +... + Cnxn ^ max при ограничениях в форме равенств a11 X1 + a12 x 2 + ... + a1 nxn = b1

a 21 ^X 1 ⁺ a 22 ^X 2 ⁺ ... ⁺ a 2 n x n = ^b 2

. a m 1 ^X 1 ⁺ a m 2 ^X 2 ⁺ ... ⁺ a mn x n = ^bm

X j >  0 ( j = 1, n )

Составим математическую модель двойственной задачи, для чего воспользуемся теми же правилами, что и для составления симметричной задачи, но с учетом следующих особенностей:

• -    ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства < , если максимум, то >

;

• -    переменные y — произвольные по знаку, т.е. могут принимать как положительные, так и отрицательные значения.

Математическая модель двойственной задачи будет такой

Бюллетень науки и практики / Bulletin of Science and Practice Т. 8. №5. 2022

S (У ) = Ь1У1 + b2У2 + ... + bmУm ^ min при ограничениях

'a ll У 1 ⁺ a 21 У 2 ⁺ ... ⁺ a m 1 У т >  ^C1

a 12 У 1 ⁺ a 22 У 2 ⁺ ... ⁺ a m 2 У т >  с 2

I a 1 п У 1 ⁺ a 2 п У 2 ⁺ ... ^{+ а}тп У т >  с п

У, >  0 ( i = 1, m )

Симметричные двойственные задачи . Рассмотрим случай неканонической модели исходной задачи, в которой все ограничения — неравенства, а переменные x, ( j = 1, _п ) неотрицательные. Такая задача имеет вид

L(x) = Cx + C2x2 +... + Cnxn ^ max при ограничениях a11 x1 + a12x2 + ... + a1 nxn < b1

a 21 ^X 1 ⁺ a 22 x 2 ⁺ ... ⁺ a 2 n x n ^ ^b 2

. a m 1 ^X 1 ⁺ a m 2 x 2 ⁺ ... ⁺ a mn x n ^ ^bm

X j >  0 ( j = 1, n )

Составим математическую модель двойственной задачи следующим образом:

• -    каждому неравенству системы ограничений исходной задачи приведем в соответствие переменную;

• -    составим целевую функцию, коэффициентами которой будут свободные члены системы ограничений исходной задачи;

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

Таким образом, математическая модель двойственной задачи будет иметь вид S ( У ) = Ь1 У1 + b2 У 2 + ... + bmУm ^ min при ограничениях

• ^a 11 У 1 ⁺ a 21 У 2 ⁺ ... ⁺ a m 1 У m >  ^C 1

• ^a 12 У 1 ⁺ a 22 У 2 ⁺ ... ⁺ a m 2 У m >  с 2

..........................................

I ^a 1 п У 1 ⁺ a 2 пУ2 ⁺ ... ^{+ a}mn У m >  с п

• У, >  0 ( i = 1, m )

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

Бюллетень науки и практики / Bulletin of Science and Practice Т. 8. №5. 2022 Несимметричные задачи Исходная задача Lmin = CX AX = B X > 0 Исходная задача Lm х = CX AX = B X > 0 Двойственная задача Smax = YB YA - C Двойственная задача Smin = YB YA > C Симметричные задачи Исходная задача                           Двойственная задача Lmin = CX                                          Smax = Y AX > B                                     YA - C X > 0                                        Y > 0 Исходная задача                           Двойственная задача L   = CX                                          Smin = YB AX - B                                     YA > C X > 0                                        Y > 0

Пример. Построить двойственную задачу к следующей задаче, заданной в общей форме:

Исходная задача

L ( x ) = X j + 2 x ₂ + 3 x₃ —— min

Двойственная задача

S ( у ) = 2 y_x + 3 y ₂ + 6 y ₃ + 3 y ₄ ^ max

2 x ₄ + 2 x₂

X j — x₂

X j + x₂ 2 X j + x.

—

—

, — х ₃ >  2 4 х ₃ - — 3 2 х ₃ >  6

■₂ — 2 х ₃ >  3

X j > 0 ( j = 1,3 )

2 y ₁ — y ₂ + y ₃ + 2 y ₄ - 1

² У 1 ⁺ У 2 ⁺ У 3 ⁺ У 4 ^{- 2}

—

y 1 + ⁴ y 2 ^{— 2} y 3 ^{— 2} y 4 - ³

y^ 0 (• = 1,4 )

Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений х и у прямой и двойственной задач выполняется равенство

L (X ) = S ( У )

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

Теорема. Для оптимальности допустимых решений х = ( х_{ , х ₂,

-, ^х п ) и У = ( У 1 ,У 2 ,-, У т )

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

m xj'L(ayyl—Ci )=0

i = 1

Анализ результатов экономических задач. Рассмотрим задачу об оптимальном использовании ресурсов с математической моделью:

L(x) = Cx + C2x2 +... + Cnxn ^ max при ограничениях в форме неравенств axx + a,x, +... + alnx„ < b a^ + a22x2 +... + a2nxn < b2

. a m 1 ^X 1 ⁺ a m 2 x 2 ⁺ ... ⁺ a mn x n <  ^bm

xj - 0 (j = 1, n )

Двойственная задача ограничениях

будет иметь вид s ( y ) = by + by + ... + b_my_m ^ min при

'a ll У 1 ⁺ a 21 У 2 ⁺ ... ⁺ a m 1 У т ^{- C} 1

• _< ^a 12 У 1 ⁺ a 22 У 2 ⁺ ... ⁺ a m 2 У т ^- с 2

I a 1 п У 1 ⁺ a 2 п У 2 ⁺ ... ^{+ a}mn У m ^{- C}n

• У, - 0 ( i = 1, m )

Если ^{y i} мало, то значительному увеличению i-го ресурса будет соответствовать небольшое увеличение оптимального дохода, т.е. ценность ресурса невелика.

Если ^{У i} = ⁰, то при увеличении i-го ресурса оптимальный доход остается неизменным, значит, ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребность в нем, не представляет ценности для производства и его оценку можно принять за нуль.

Если ^{y i} велико, то незначительному увеличению i-го ресурса будет соответствовать существенное увеличение оптимального дохода, т.е. ценность ресурса высока, а его уменьшение приведёт к существенному сокращению выпуска продукции.

Двойственный симплексный метод

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

• -    составляется каноническая форма ЗЛП с возможными отрицательными свободными членами;

• -    задача в канонической форме переписывается в симплексную таблицу;

• -    определяется вектор, выводимый из системы базисных векторов с наименьшим отрицательным свободным членом;

• -    определяется вектор, вводимый в системы базисных векторов, вычислением минимума отношений отрицательных элементов последней строки симплексной таблицы к соответствующим отрицательным элементам строки выводимой из системы базисных векторов с наименьшим отрицательным свободным членом;

• -    элемент, находящийся на пересечении вводимого и выводимого векторов является разрешающим элементом;

• -    составление новой симплексной таблицы осуществляется, как и в обычном симплексном методе;

Процесс продолжается до тех пор, пока все элементы вектора свободных членов будут неотрицательными и условие оптимальности решения выполняется.

Пример. Z=12x1+16x2 ^ min x1 + 2x2 ≥ 40

x1 + x2 ≥ 30

x1, x2 ≥ 0

Составим двойственную к этой задаче и решим симплексным методом. Для этого заменим требование минимизации на максимизацию. Правые стороны системы ограничений запишем коэффициентами в новую целевую функцию. Коэффициенты исходной целевой функции запишем в правую сторону неравенств новых ограничений. Знаки неравенств поменяем на обратные. Матрицу коэффициентов системы ограничений транспонируем.

S=40y1+30y2 ^ max, S-40y1-30y2=0

A = (1  2) . Транспонируем матрицу коэффициентов системы ограничений: AT =

(    ). Составим новую систему ограничений:

y 1 + y 2 ≤ 12    y 1 + y 2 + u 1 = 12

{2y 1 + y 2 ≤ 16,  {2y 1 +y 2 +u 2 = 16

y 1 ,y 2 ≥ 0           u₁, u₂ ≥ 0

Теперь решим симплексным методом:

B	S	y 1	y 2	u 1 =x 1	u 2 =x 2	b i
u 1	0	1	1	1	0	12
u 2	0	2	1	0	1	16
	1	-40	-30	0	0	0
u 1	0	0	1/2	1	-1/2	4
y 1	0	1	1/2	0	1/2	8
	1	0	-10	0	20	320
y 2	0	0	1	2	-1	8
y 1	0	1	0	-1	1	4
	1	0	0	20	10	400

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