Теория двойственности в анализе оптимальных решений экономических задач.

Методы оптимальных решений

Контрольные вопросы по предмету

0


Подпишитесь на бесплатную рассылку видео-курсов:

Текст видеолекции

Методы оптимальных решений

Лекция 2

Тема лекции 2: «Теория двойственности в анализе оптимальных решений экономических задач»

Разделы лекции:

1. Математический аппарат для решения задач линейного программирования.
2. Построение двойственной задачи. Теоремы двойственности.
3. Экономическая интерпретация двойствен¬ной задачи.

РАЗДЕЛ 1.  МАТЕМАТИЧЕСКИЙ АППАРАТ ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

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

ЛИНЕЙНЫЕ СИСТЕМЫ ОБЩЕГО ВИДА.
Наши рассмотрения мы начнем с несколько условного примера.
ПРИМЕР 1.

У завода есть четыре потребителя, которым еженедельно отгружается готовая продукция. Груз доставляется каждому потребителю на автомашине упакованным в ящики, маркированные в зависимости от вида продукции. Однажды, когда автомашины были уже отправлены, но еще находились в пути, обнаружилось, что один из четырех видов груза был отправлен по ошибке и его следует возвратить (причем в полной сохранности и без нарушения целостности остальных грузов). Одновременно выяснилось также, что по недосмотру служащего не осталось никаких сведений о том, как именно маркирована та партия ящиков, в которых находился этот подлежащий возврату груз.
А что же известно?
Известно количество маркированных ящиков каждого вида и общий вес груза в каждой автомашине, эти данные приведены в таблице 1. А также известно то, что ящики с возвращаемым грузом должны быть тяжелее остальных.
Таблица 1.
Номер автомашины    Груз (количество ящиков)
    1-й вид    2-й вид    3-й вид    4-й вид    Общий вес, ц.
1    1    4    9    8    51
2    2    9    8    3    45
3    2    6    8    6    48
4    3    5    7    8    51

Возникает вопрос: а нельзя ли дать рекомендации по изъятию этого груза без распаковки и дополнительного взвешивания? Оказывается, можно. Приведем расчеты, при помощи которых совсем нетрудно выйти из сложившейся чрезвычайной ситуации. 
Обозначим через хk вес ящика с k-м видом груза. Тогда общий вес груза на автомашине 1, используя данные из таблицы 1, можно подсчитать так:  x1+4x2+9x3+8x4, что равно 51. Проведем аналогичные подсчеты для трех других автомашин и запишем результаты:
 x1+4x2+9x3+8x4=51,

2x1+9x2+8x3+3x4=45,

2x1+6x2+8x3+6x4=48,

3x1+5x2+7x3+8x4=51.

Таким образом, мы получили набор (систему) линейных уравнений, в которые входят четыре неизвестные пока величины х1, х2, х3 и х4, подлежащие определению. Покажем, как их можно найти методом исключения неизвестной.
1-Й ШАГ.

 Заметим, что если ко второму уравнению прибавить первое, умноженное на (– 2) , то в результате получится соотношение: x2 – 10x3 – 13x4= –57,  в котором неизвестной х1 явно нет. Поступая аналогичным образом с третьим (первое уравнение нужно умножить на (– 2) и сложить с третьим уравнением) и с четвертым (первое уравнение нужно умножить на (–3)  и сложить с четвертым уравнением) уравнениями и сохраняя неизменным первое, приходим к следующей системе соотношений: 
x1+4x2+9x3+8x4=51,

x2–10x3–13x4= –57,

–2x2–10x3–10x4= –54,

–7x2–20x3–16x4= –102.

В дальнейших преобразованиях первое уравнение, активно работавшее на 1-м шаге, участия не принимает.
2-Й ШАГ.

На этом шаге рабочим является преобразованное второе уравнение:  x2–10x3–13x4= –57.
Умножим его на 2 и сложим с третьим уравнением: –30x3–36x4= –168. Полученное соотношение не содержит ни неизвестной x1, ни неизвестной x2.
После сложения четвертого уравнения со вторым, предварительно умноженным на 7, мы приходим к похожему результату: –90x3–107x4= –501.

В итоге получаем систему уравнений (*) следующего вида:
x1+4x2+9x3+8x4=51,

x2–10x3–13x4= –57,

–30x3–36x4= –168,

–90x3–107x4= –501.

3-Й ШАГ.

На этом шаге рабочим является преобразованное третье уравнение: –30x3–36x4= –168.

Прибавляя его к четвертому (предварительно умножив на (–3)), окончательно получаем: x4=3.

ЗАВЕРШАЮЩИЙ ЭТАП.

В результате проделанных преобразований нам удалось найти значение одной из неизвестных, а именно х4=3. Значения остальных неизвестных находятся совсем просто. Сначала из третьего уравнения системы (*) находим значение неизвестной х3 , предварительно подставив туда уже найденное значение неизвестной х4=3. Мы имеем: –30x3–36•3= –168. Отсюда, –30x3= –168+108, то есть x3=2.

Подставляя затем найденные значения неизвестных х3=2 и x4=3 во второе уравнение системы (*), получаем: x2–10•2–13•3= –57, отсюда, x2= –57+20+39=2.

Наконец, из первого уравнения, подставляя найденные значения: х2=2, х3=2 и x4=3, находим значение неизвестной x1: x1+4•2+9•2+8•3=51, то есть x1=51–8–18–24=1.
 
Запишем полученный ответ: x1=1, х2=2, х3=2 , x4=3.

Отсюда вытекает, что вес ящика с четвертым видом груза x4=3, больше веса ящиков с другими видами груза. Значит,  нужно вернуть на завод ящики с 4-м видом груза, то есть 8+3+6+8=25 ящиков.

ЧТО ТАКОЕ МАТРИЦА?
Довольно часто либо при начальном описании задачи, либо при более жестком ее формулировании конкретный набор числовых данных удобно записывается в виде прямоугольной таблицы. Подобные прямоугольные таблицы естественно возникают при рассмотрении графов и сетей, при описании задач линейного программирования, при рассмотрении систем линейных уравнений и еще во многих других случаях, где они оказываются весьма кстати. Эти обстоятельства были замечены в середине XIX века, и появились матрицы. Сейчас вполне можно сказать, что матрица является одним из основных математических понятий, обладающим массой интересных и полезных свойств. Мы познакомимся лишь с некоторыми из них. Но сначала немного определений.

ОПРЕДЕЛЕНИЕ. Матрицей А размера m x n называется набор m•n  чисел aij   (i = 1,2, . . . , m; j=1,2, . . . , n) — элементов матрицы, записанных в виде прямоугольной таблицы: 
Набор
ai1 ai2 … ain
 
 называется i-й строкой матрицы А, а набор

a1j a2j … amj
 
 называется j-м столбцом этой матрицы.
В случае когда m=n, матрица А называется квадратной, а число n — ее порядком. Пользуясь понятием матрицы, опишем для примера все три шага преобразований, которые были проведены в примере 1.
Начнем с исходной системы уравнений и аккуратно выпишем все коэффициенты. Имеем 
Здесь строки матрицы соответствуют уравнениям системы, а столбцы — неизвестным. Последний столбец отделен от остальных вертикальной чертой — этим подчеркивается его особое место в матрице (члены, расположенные в уравнениях по правую часть от знака равенства, не содержат неизвестных величин (свободны от неизвестных)).
Посмотрим теперь, как будут выглядеть матрицы, соответствующие системам, получавшимся в конце каждого шага.

После 1-го шага  получим соответствующую матрицу: 
После 2-го шага  получим соответствующую матрицу:
 
После 3-го шага  получим соответствующую матрицу:  

ЗАМЕЧАНИЕ. Обратите внимание на то, как расположены нули в выписанных матрицах.
Довольно ясно, что и число линейных уравнений, и число связанных ими неизвестных могут быть любыми.
ОПРЕДЕЛЕНИЕ ЛИНЕЙНОЙ СИСТЕМЫ.

Совокупность соотношений
a11x1+a12x2+…+ a1nxn=b1,

a21x1+a22x2+…+a2nxn=b2,


am1x1+am2x2+…+ amnxn=bm,  

(**)
где aij, bi (i=1, …, m; j=1, …, n) – заданные числа, а числа хj, j=1, …, n,  рассматриваются как величины, подлежащие определению (неизвестные), называется системой m линейных уравнений с n неизвестными (линейной системой).
Заметим, что линейная система (**) полностью описывается расширенной матрицей системы:

a11    a12    …    a1n    b1
a21    a22    …    a2n    b2
…    …    …    …    …
am1    am2    …    amn    bm
 
ЧТО ТАКОЕ РЕШЕНИЕ ЛИНЕЙНОЙ СИСТЕМЫ?

Решением линейной системы (**) называется любой упорядоченный набор чисел λ1, λ2, … , λn,  который при подстановке в каждое уравнение системы (**) вместо набора неизвестных х1, х2, ..., хn,  обращает это уравнение в верное равенство.
СКОЛЬКО РЕШЕНИЙ МОЖЕТ ИМЕТЬ ЛИНЕЙНАЯ СИСТЕМА?

Интересно отметить, что и в общем случае (как и для системы двух уравнений с двумя неизвестными) при исследовании системы могут встретиться только три варианта:
(1) система имеет единственное решение,
(2) система имеет бесчисленное множество решений,
(3) система не имеет решений (такая система называется несовместной).
ИССЛЕДОВАНИЕ ЛИНЕЙНЫХ СИСТЕМ.
Метод последовательного исключения неизвестной, примененный в ходе решения примера 1, универсален. Пользуясь этим методом, можно исследовать любую систему линейных уравнений и, если она имеет решение, найти его.
ПРИМЕР 2 (ИССЛЕДОВАНИЕ ЛИНЕЙНОЙ СИСТЕМЫ).

Дана система линейных уравнений  
Требуется найти значения параметра c, при которых система:
1) несовместна,
2) совместна.
В случае, когда система совместна, отыскать ее решение.
1-Й ШАГ. При помощи первого уравнения исключаем неизвестную x1 из второго и третьего уравнений (умножая первое уравнение на (– 2) и складывая со вторым уравнением, исключаем неизвестную x1 из второго уравнения;  умножая первое уравнение на (– 7) и складывая с третьим уравнением, исключаем неизвестную x1 из третьего уравнения). В результате получаем следующую систему уравнений:
  

2-Й ШАГ. Сохраняя первое уравнение системы неизменным, при помощи второго уравнения исключаем неизвестную x2 из третьего уравнения. Для этого умножаем второе уравнение на  (– 2) и складываем с третьим уравнением. В результате получаем:

  

ВЫВОД. Заданная система
1) несовместна, если с+1≠0,
2) совместна, если с+1=0.
При с= –1 получаем:
  
Таким образом, третье уравнение этой системы выполнятся тождественно: 0=0.  В итоге, на три неизвестные величины х1, х2 и х3 имеем только два условия.
Полагая х3=t, из второго уравнения находим, что x2+7t= –4.  Отсюда,  x2= –4 – 7t. 

Подставим теперь полученные выражения х3=t,  x2= –4 – 7t, в первое уравнение. Имеем:
x1+4(–4 – 7t) –3t=2.  Отсюда, x1=18+31t.  
ОТВЕТ:
1) при с≠–1 система несовместна,
2) при с= –1 система совместна, и ее решение можно записать в виде:

x1=18+31t, x2= –4 – 7t, х3=t.  
(здесь t –  любое действительное число).
ЗАМЕЧАНИЕ. Линейная система, рассмотренная в примере 2, при  с= –1 имеет бесчисленное множество решений.

Например, при t=0, получим решение: x1=18, x2= –4, х3=0.   Аналогично, подставив вместо  t любое действительное число, получим решение системы. Ясно, что при  с= –1 данная система будет иметь бесчисленное множество решений.

ОПЕРАЦИИ НАД МАТРИЦАМИ.
Матрицы предоставляют весьма удобный способ записи количественной информации и потому часто используются в самых разных ситуациях. Приведем лишь два примера.
ПРИМЕР 3 (РАСПИСАНИЕ).

 В колледже m студенческих групп: G1, …, Gm, и n преподавателей: L1, …, Ln . Известно, что в i-й группе Gi k-й преподаватель Lk должен провести аik часов занятий. Таблица (матрица) занятости студентов и преподавателей (таблица 2) может быть записана в следующем виде: Таблица 2.
    L1    …    Ln
G1    a11    …    a1n
…    …    …    …
Gm    am1    …    amn


(в i-й строке указано количество часов занятий, которые i-я группа проведет с каждым из преподавателей L1, …, Ln, а в k-м столбце – количество часов, которые k-й преподаватель Lk проведет с каждой из групп G1, …, Gm).
ПРИМЕР 4.
Мороженщица, торгующая в кинотеатре, перед утренним сеансом продала 36 порций пломбира: 8 порций в стаканчиках, 10 порций в брикетах, 7 порций в трубочках и 11 порций в рожках; перед дневным сеансом — 62 порции: соответственно 16, 15, 13 и 18. Наибольший спрос пришелся на вечер — 101 порция: 25, 21, 31 и 24 соответственно. Это можно записать компактно в виде таблицы (таблица 3).

Таблица 3.
    Утренний сеанс    Дневной сеанс    Вечерний сеанс
Пломбир в стаканчиках    8    16    25
Пломбир в брикетах     10    15    21
Пломбир в трубочках     7    13    31
Пломбир в рожках    11    18    24


Нередко матрицы выступают не только в роли хранителей информации. Интересно, что с ними можно проводить различные операции, подобные тем, которые мы привычно совершаем с числами: матрицы можно складывать, вычитать, умножать и пр. Однако действовать здесь приходится осторожно, с оглядкой, так как не всякие матрицы можно сложить, а с перемножением дело обстоит еще сложнее.
СЛОЖЕНИЕ МАТРИЦ.
Пусть А=||aij|| и В=||bij|| – матрицы одинаковых размеров (т. е. состоящие из одинакового числа строк и одинакового числа столбцов):

 

Матрица C=||cij||
 
называется суммой матриц А и В, если ее элементы вычисляются по правилу: cij=aij+bij, i=1, …, m; j=1, …, n.

Иными словами, складываются элементы матриц А и В, стоящие в одинаковых позициях (в i-й строке и в j-м столбце), и полученная сумма записывается в новой матрице С в ту же позицию (i,j).
Это можно записать и так:  
Обозначение: C=А+В.
Вычитание матриц определяется аналогично.
ЗАМЕЧАНИЕ. Операция сложения определена лишь для матриц, имеющих одинаковые размеры. Если матрицы имеют разное число строк или разное число столбцов, то складывать их нельзя.
ПРОДОЛЖЕНИЕ ПРИМЕРА 3 (РАСПИСАНИЕ). По заданной матрице занятости (таблица 2) требуется составить расписание занятий таким образом, чтобы общая продолжительность h всех проведенных занятий была минимальной, считая, что проблем с аудиторным фондом нет. Попробуем сначала оценить общую продолжительность занятий снизу.
Преподаватель Lk, k = 1,..., n, должен провести всего (tk=a1k+…+amk) часов занятий, так что число h не может быть меньше, чем максимальное из чисел t1, …, tn. То есть h≥t=max tk.

Общее число часов занятий в группе Gi, i=1, …, m, равно (vi=ai1+…+ain). Вследствие чего число h не может быть меньше, чем максимальное из чисел v1, …, vm. То есть h≥v=max vi.

Тем самым, общая продолжительность занятий h не меньше наибольшего из чисел t и v. Иными словами, должно выполняться условие:  h≥S=max{t, v}. НА САМОМ ДЕЛЕ ДЛЯ ВЫПОЛНЕНИЯ УЧЕБНОГО ПЛАНА ТРЕБУЕТСЯ РОВНО S ЧАСОВ.

Покажем, как можно составить такое расписание занятий в случае, когда m=5, n=3, а матрица загруженности имеет вид
    L1    L2    L3
G1    2    1    3
G2    0    1    0
G3    2    3    1
G4    1    0    2
G5    0     2    0

Складывая элементы матрицы по строкам и по столбцам, легко убедиться в том, что t=7 и v=6, причем в наибольшей степени загружен преподаватель L2, а G1 и G3 – наиболее загруженные группы. В данном случае h=S=7. Тем самым, минимальная суммарная продолжительность занятий равна семи часам, причем 2-й преподаватель должен быть загружен каждый час. Покажем, как именно можно составить соответствующее оптимальное расписание.
Матрица (запись) 
0    0    1
0    0    0
0    1    0
1    0    0
0    0    0


означает, что 1-й час занятий преподаватель L1 проводит с группой G4 (и, следовательно, не может провести этот час ни с какой другой группой, да и группа G4 не может провести этот час ни с каким другим преподавателем). Преподаватель L2 проводит 1-й час занятий  с группой G3, а преподаватель L3 –  с группой G1. 
По истечении 1-го часа занятий получаем новую матрицу загруженности на оставшиеся шесть часов:
2-0    1-0    3-1
0-0    1-0    0-0
2-0    3-1    1-0
1-1    0-0    2-0
0-0    2-0    0-0


То есть

2    1    2
0    1    0
2    2    1
0    0    2
0    2    0

Выберем матрицу нагрузки на 2-й час занятий в виде:

0    1    0
0    0    0
1    0    0
0    0    1
0    0    0

Тогда по истечении 2-го часа получим:
2-0    1-1    2-0
0-0    1-0    0-0
2-1    2-0    1-0
0-0    0-0    2-1
0-0    2-0    0-0

То есть получим новую матрицу загруженности на следующие 5 часов:

2    0    2
0    1    0
1    2    1
0    0    1
0    2    0


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

Полученное соотношение означает, что все занятия можно провести за 7 часов, а каждую группу и каждого преподавателя снабдить фактическим расписанием. Так, на 5-м часу преподаватель Ll проводит занятия с группой G1, преподаватель L2 – с группой G5 и преподаватель L3 – с группой G3. В то время как студенты групп G2 и G4 могут позаниматься в библиотеке или отдохнуть.
УМНОЖЕНИЕ МАТРИЦЫ НА ЧИСЛО.
Матрица D=||dij||  называется произведением матрицы А=||aij|| на число α, если ее элементы dij вычисляются по правилу: dij=α•aij, i=1, …, m; j=1, …, n. Иными словами, умножив элемент матрицы А из i-й строки и j-го столбца на число α, нужно записать полученный результат в i-ю строку и j-й столбец новой матрицы. Сказанное можно записать и так: 
Обозначение: α•А.
В частности, при умножении матрицы А на число α=0 получается матрица, все элементы которой равны нулю (нулевая матрица того же размера, что и матрица А):
ТРАНСПОНИРОВАНИЕ МАТРИЦЫ.
ПРИМЕР 4 (ПРОДОЛЖЕНИЕ). Результат торговли мороженым можно записать двояко: либо так, как это было сделано в примере 4:
    Утренний сеанс    Дневной сеанс    Вечерний сеанс
Пломбир в стаканчиках    8    16    25
Пломбир в брикетах     10    15    21
Пломбир в трубочках     7    13    31
Пломбир в рожках    11    18    24

либо так:
    Пломбир в стаканчиках    Пломбир в брикетах     Пломбир в трубочках    Пломбир в рожках
Утренний сеанс     8    10    7    11
Дневной сеанс    16    15    13    18
Вечерний сеанс    25    21    31    24

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

Пусть A=||aij|| –   заданная матрица.

 
Построим матрицу В по следующему правилу: взяв в матрице А произвольный элемент aik , (i= l,...,m; k= 1,..., n), запишем его в новой матрице в k-ю строку и i-й столбец, т. е. положим: bki=aik.   В результате получим матрицу

 
про которую говорят, что она получена из матрицы А путем транспонирования, а сама операция над матрицей А, которая, не изменяя самих ее элементов, определяет для них новый порядок расположения, называется транспонированием матрицы А.
Обозначение: АT.
УМНОЖЕНИЕ МАТРИЦЫ НА СТОЛБЕЦ.
Пусть A=||aij||

 
– матрица размера m x n  и X – столбец высоты n. 
Произведение матрицы А на столбец X определяется так: 
Или в несколько сокращенном виде:
 

Заметим, что матрицу можно умножать не на любой столбец, а лишь на такой, число элементов которого равно числу столбцов матрицы. Символически это можно описать так: 
Обозначение: АX.
ЗАМЕЧАНИЕ. Результирующий столбец АX содержит ровно m элементов. При m=n оба столбца (и X, и АX) имеют одинаковую высоту.

ПРИМЕР 4 (ПРОДОЛЖЕНИЕ, ПОДСЧЕТ ВЫРУЧКИ). Вновь вернемся к мороженщице и подсчитаем ее выручку, зная цену каждого сорта проданного ею мороженого.

    Пломбир в стаканчиках    Пломбир в брикетах     Пломбир в трубочках    Пломбир в рожках
Утренний сеанс     8    10    7    11
Дневной сеанс    16    15    13    18
Вечерний сеанс    25    21    31    24

При цене 30 руб. за одну порцию пломбира в стаканчиках, 15 руб. за одну порцию пломбира в брикетах, 20 руб. за одну порцию пломбира в трубочках и 25 руб. за одну порцию пломбира в рожках утренняя выручка оказывается равной:

8•30 +10•15+7•20+11•25=805 руб.;

дневная:
16•30 +15•15+13•20+18•25=1415 руб.

и вечерняя:
25•30 +21•15+31•20+24•25=2285 руб.

Те же самые результаты мы получим, умножив матрицу продаж мороженого

8    10    7    11
16    15    13    18
25    21    31    24

на ценовой столбец:

30
15
20
25
 Получим столбец выручки:
805
1415
2285


УМНОЖЕНИЕ СТРОКИ НА МАТРИЦУ.
Пусть p =(p1 p2 …  pm)  – строка из m элементов и матрица A =||aij|| размера m x n. 
Произведение строки P на матрицу А определяется формулой 
или символически 
Обозначение: рА.
ПРИМЕР 5. Цены на билеты в кинотеатр зависят от того, когда начинается сеанс — утром, днем или вечером. Цена билета на утренний сеанс равна 100 руб., на дневной — 150 руб., а на вечерний — 200 руб.
Пусть матрица A=

50    60    45    60
50    90    80    70
105    100    95    110

описывает число посетителей кинотеатра в первые четыре дня (столбцы) показа нового кинофильма; строки отражают посещения утром, днем и вечером соответственно. Тогда выручку по дням можно рассчитать так.
Строку цен p=
100    150    200

умножить на матрицу A. Мы получим строку выручки по дням:

pA=

100•50+150•50+
+200•105=33500
    100•60+150•90++200•100=39500
    100•45+150•80+
+200•95=35500    100•60+150•70+
+200•110=38500

НЕОТРИЦАТЕЛЬНЫЕ И ПОЛОЖИТЕЛЬНЫЕ МАТРИЦЫ.
Матрица A=||aij|| называется неотрицательной, если aij≥0, i=1, …, m; j=1, …, n.

Матрица A=||aij|| называется  положительной, если выполняются строгие неравенства aij>0, i=1, …, m; j=1, …, n.

ПРИМЕР 6. Матрица занятости в примере о составлении расписания неотрицательна:

2    1    3
0    1    0
2    3    1
1    0    2
0     2    0

Матрица реализации порций мороженого положительна:
8    10    7    11
16    15    13    18
25    21    31    24

Обозначения: A≥0, A>0.

Пусть А=||aij||  и В=||bij|| – матрицы одинаковых размеров.
Будем писать A>B,  если aij>bij, i=1, …, m; j=1, …, n.

Будем писать A≥B,  если aij≥bij, i=1, …, m; j=1, …, n.

РАЗДЕЛ 2. ПОСТРОЕНИЕ ДВОЙСТВЕННОЙ ЗАДАЧИ.

Как отмечено выше, среди широкого класса задач опти¬мального программирования имеются важные подклассы за¬дач, для которых разработаны эффективные методы реше¬ния. Наиболее изученным подклассом задач являются зада¬чи линейного программирования. К математическим задачам линейного программирова¬ния приводят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде ин¬терпретируются как задачи об оптимальном использова¬нии ограниченных ресурсов (задача о раскрое, смесях, дие¬те и т.д.). Некоторые примеры таких задач и их решение графическим методом мы рассмотрели на лекции 1 «Основы линейного программирования».

КАНОНИЧЕСКАЯ ФОРМА ЗАПИСИ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.

В лекции 1 «Основы линейного программирования» показано, что любую задачу линейного программирования можно записать следующим образом. В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целе¬вой функции f(X), где X=(x1, x2, …, xn):

f(X)=c1x1+c2x2+ … + cnxn  →max(min) (1)

при ограничениях (условиях):

a11•x1+a12•x2+…+a1n•xn{≤ , =, ≥}b1,  

a21•x1+a22•x2+…+a2n•xn{≤ , =, ≥}b2,  



am1•x1+am2•x2+…+amn•xn{≤ , =, ≥}bm,    (2)

xj≥ 0, j=1, …, n , (3)

где aij, bi, cj (i=l,…, m; j=1, …,n) – заданные постоянные величины.

Так записывается общая задача линейного программиро¬вания в развернутой форме.  Знак {≤, =, ≥} означает, что в конкретной ЗЛП возможно ограничение типа равенства «=» или неравенства «≤», «≥».

Систему ограничений (2) называют функциональны¬ми ограничениями ЗЛП, а ограничения (3) называют прямыми ограничениями ЗПЛ.

ЧТО ТАКОЕ ПЛАН ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

Вектор X = (x1, x2, ..., xn), удовлетворяющий системе ог¬раничений (2), (3), называется допустимым решением, или планом ЗЛП, т.е. ограничения (2), (3) определяют область допустимых решений, или планов задачи линей¬ного программирования (область определения ЗЛП).

ЧТО ТАКОЕ ОПТИМАЛЬНЫЙ ПЛАН ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ?

План (допустимое решение) X* = (x*1, x*2, ..., x*n), который доставляет экстремум (максимум или минимум) целевой функции f(X) (1), называется опти¬мальным планом (оптимальным допустимым решением) ЗЛП.

Канонической формой записи задачи линейного програм¬мирования (КЗЛП) называют задачу следующего вида (запись с исполь¬зованием знаков суммирования):

Найти максимум целевой функции
 n
f(X) =  ∑ cjxj  → max (4)
          j=1
при ограничениях:

n
∑ a1jxj = b1,
j=1

n
∑a2jxj = b2,
j=1

n
∑ amjxj = bm,
j=1

(5)

и

xj≥ 0, bi≥ 0, i=1, …,m, j=1, …, n. (6)

Векторная форма записи КЗЛП имеет вид:

 Найти максимум целевой функции

f(X)=CХ→ max

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

А1x1+А2х2 + ... +Аnxn=В, X≥0,

где С=(c1,c2, …, cn), X=(x1, x2, …, xn) – арифметические векторы, СХ – скалярное произведение векторов С и Х; Аj, j=1, …, n; и В — вектор-столбцы:

 

Матричная форма записи КЗЛП следующая.

Найти максимум целевой функции

f(X)=CX→max

при условиях

АХ=В, X≥0.

Здесь C=(c1 c2 ... cn) — вектор-строка; А =||aij|| – матри¬ца размера (m x n), столбцами которой являются вектор-столбцы  Aj, j=1, …, n; X – вектор-столбец, B – вектор-столбец: 

 
 

При этом запись X≥0 понимают как вектор (или век¬тор-столбец в зависимости от контекста), у которого все ком¬поненты (элементы) неотрицательны.

Иногда используется следующая стандартная форма записи ЗЛП.

Найти экстремум (максимум или минимум) целевой функции

f(X)=CX→max (min)

при условиях

АХ≤ {≥} В, X≥0.

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (2) k-й дополнительной переменной хn+k≥0, которая берется со знаком «–»  в случае ограничения типа «≥» и со знаком «+» в случае ограниче¬ния типа «≤». Если на некоторую переменную хp не накладывается ус¬ловие неотрицательности, то делают замену переменных хp=х'p – х"p, где х'p≥ 0, х"p≥0 . В преобразованной задаче все переменные неотрицательные. Переход к задаче на макси¬мум достигается изменением в случае необходимости знака у целевой функции. На лекции 1 «Основы линейного программирования» мы подробно рассмотрели этот вопрос с введением свободных переменных (избыточные и остаточные переменные).

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

ЧТО ТАКОЕ ДВОЙСТВЕННЫЕ ОЦЕНКИ?
 
Переменные двойственной задачи yi, i=1, …, m, называют ОБЪЕКТИВНО ОБУСЛОВЛЕННЫМИ ОЦЕНКАМИ, ИЛИ ДВОЙСТВЕННЫМИ ОЦЕН¬КАМИ.

Пусть дана следующая задача линейного программирования (ЗЛП) (1’),(2’),(3’):
 

Модель двойственной задачи имеет вид (1”),(2”),(3”):

 

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

ПО КАКИМ ПРАВИЛАМ СОСТАВЛЯЕТСЯ ДВОЙСТВЕННАЯ ЗАДАЧА ПО ОТНОШЕНИЮ К ИСХОДНОЙ ЗЛП?

Двойственная задача по отношению к исходной ЗЛП состав¬ляется согласно следующим правилам:

1) целевая функция исходной задачи ЗЛП формули¬руется на максимум, а целевая функция двойственной задачи – на минимум, при этом в задаче на максимум все неравенства в функциональных ограниче¬ниях имеют вид «≤», а в задаче на минимум – вид «≥»;

2) матрица A=||aij||,  составленная из коэффициентов при неизвестных в сис¬теме функциональных ограничений (2’) исходной задачи, и аналогичная матрица AT=||aji|| в двойственной задаче получаются друг из друга транс¬понированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений (2’) исходной задачи, а число функциональных ограничений (2”) в системе  двойственной задачи – числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе функциональных ограничений (2’) исходной задачи, а правыми частями в функциональных ограничениях  (2”) двойственной задачи – коэффициенты при неизвестных в целевой функции (1’) исходной задачи;

5) каждому функциональному ограничению одной задачи соответствует пере¬менная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записанному в виде неравенства «≤», соответствует переменная, связанная условием неотрицательности. Если функцио¬нальное ограничение исходной задачи является равенст¬вом, то соответствующая переменная двойственной зада¬чи может принимать как положительные, так и отрица¬тельные значения.

Математические модели пары двойственных задач могут быть симметричными и несимметричными.

КАКИЕ ДВОЙСТВЕННЫЕ ЗАДАЧИ ЯВЛЯЮТСЯ НЕСИММЕТРИЧНЫМИ?

В несимметрич¬ных двойственных задачах система функциональных ограничений исходной ЗЛП задается в виде равенств, а в двойственной – в виде неравенств.  Причем в двойственной несимметричной задаче  переменные могут быть и отрицательными.

КАКИЕ ДВОЙСТВЕННЫЕ ЗАДАЧИ ЯВЛЯЮТСЯ СИММЕТРИЧНЫМИ?

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

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

Итак, согласно теории линейного программирования ка¬ждой ЗЛП вида (1’)-(3’) соответствует двойственная ей ЗЛП: (1”)-(3”). Основные утверждения о взаимодвойственных задачах содержатся в двух следующих теоремах.

ПЕРВАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ.

Для взаимодвойствен¬ных ЗЛП имеет место один из следующих взаимоисключающих случаев.

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оп¬тимальных решениях совпадают: max f(X)= min g(Y).

2. В прямой задаче допустимое множество не пусто, а це¬левая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допусти¬мое множество.

3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множест¬во оказывается пустым.

ВТОРАЯ ТЕОРЕМА ДВОЙСТВЕННОСТИ (ТЕОРЕМА О ДОПОЛНЯЮЩЕЙ НЕЖЕСТКОСТИ).

Пусть X = (х1,х2, ..., xn) – допустимое реше¬ние прямой задачи (1’)-(3’), a Y = (y1, y2, …, ym) – допустимое решение двойственной задачи (1”)-(3”). Для того чтобы они были оптимальными решениями соответствую¬щих взаимодвойственных задач (1’)-(3’) и (1”)-(3”), не¬обходимо и достаточно, чтобы выполнялись следующие соот¬ношения:
 

Решая ЗЛП симплексным методом, мы одновременно ре¬шаем двойственную ЗЛП. Значения переменных двойствен¬ной задачи уi, i=1, …, m,  в оптимальном плане называют, как выше уже отмечено, объективно обусловленными, или двойствен¬ными оценками.

РАЗДЕЛ 3. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ДВОЙСТВЕН¬НОЙ ЗАДАЧИ.

Рассмотрим экономическую интерпретацию двойствен¬ной задачи на следующем примере.

ПРИМЕР 7. (ЗАДАЧА ОПТИМАЛЬНОГО ИСПОЛЬЗОВАНИЯ РЕСУР¬СОВ).

Пусть для выпуска четырех видов продукции P1, P2, Р3, Р4 на предприятии «Белоснежка и семь гномов» используют три вида сырья S1, S2 и S3. Объемы выделенного сырья, нормы расхода сырья и прибыль на единицу продукции при изготовлении каждого вида продукции приведены в таблице 4. Требуется опреде¬лить план выпуска продукции, обеспечивающий наиболь¬шую прибыль.

Таблица 4.
Вид сырья    Запасы сырья    Вид продукции
        P1    P2    P3    P4
S1    35    4    2    2    3
S2    30    1    1    2    3
S3    40    3    1    2    1
Прибыль    14    10    14    11

Составим экономико-математическую модель задачи оп¬тимального использования ресурсов на максимум прибыли. В качестве неизвестных примем объем выпуска продукции j-го вида xj (j=1,2,3,4). Имеем следующую модель задачи.
Максимизировать целевую функцию f(X)=14x1+10x2+14x3+11x4 => max,

При следующих ограничениях:

4x1+2x2+2x3+3x4≤35,

x1+x2+2x3+3x4≤30,

3x1+x2+2x3+x4≤40,

xj≥0, j=1,2,3,4.

Теперь сформулируем двойственную задачу. Пусть некая организация «Бременские музыканты» решила закупить все ресурсы рассматриваемо¬го предприятия «Белоснежка и семь гномов». При этом необходимо установить опти¬мальную цену на приобретаемые ресурсы y1, y2, y3, исходя из следующих объективных условий:

1) покупающая организация «Бременские музыканты» старается минимизировать об¬щую стоимость ресурсов;

2) за каждый вид ресурсов надо уплатить не менее той суммы, которую хозяйство «Белоснежка и семь гномов» может выручить при перера¬ботке сырья в готовую продукцию.

Согласно первому условию общая стоимость сырья выра¬зится величиной

g(Y)=35у1+30у2+40у3 → min.

Согласно второму требованию вводятся следующие ограничения.

(1) На единицу пер¬вого вида продукции расходуются четыре единицы первого ресурса ценой y1, одна единица второго ресурса ценой у2 и три единицы третьего ресурса ценой у3.  Тогда стоимость всех ре¬сурсов, расходуемых на производство единицы первого вида продукции, равна: 4y1+y2+3y3, и должна составлять не ме¬нее 14 у.е., то есть 4y1+y2+3y3≥14.

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

(2) Для второго вида продукции: 2y1+y2+y3≥10.


(3) Для третьего вида продукции: 2y1+2y2+2y3≥14.


(4) Для четвертого вида продукции: 3y1+3y2+y3≥11.


Таким образом, имеем следующую систему функциональных ограничений двойственной ЗЛП:

4y1+y2+3y3≥14,

2y1+y2+y3≥10,

2y1+2y2+2y3≥14,

3y1+3y2+y3≥11.

По экономическому смыслу цены неотрицательные: y1≥0, y2≥0, y3≥0.

Получили симметричную пару взаимодвойственных задач. В результате решения данной задачи симплексным методом получен оптимальный план X* =(0; 5; 12,5; 0); Y*=(3; 4; 0).

В ЧЕМ СОСТОИТ ЭКОНОМИЧЕСКИЙ СМЫСЛ ПЕРВОЙ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ?

Экономический смысл первой теоремы двойственности следующий. План производства X и набор оценок ресурсов Y оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при из¬вестных заранее ценах продукции c1, с2, …, cn, равна затра¬там на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов у1, y2, …, ym. Для всех же других планов X и Y обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов: f(X)≤g(Y) , т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Зна¬чит, величина g(Y)–f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов. Из первой теоремы двойственности следует, что при оп¬тимальных производственной программе и векторе оценок ресурсов производственные потери равны нулю. Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию «Белоснежка и семь гномов» безразлично, производить ли продукцию по оптимальному плану X* и по¬лучить максимальную прибыль либо продать ресурсы организации «Бременские музыканты» по оп¬тимальным ценам Y* и возместить от продажи равные ей минимальные затраты на ресурсы.

КАКИЕ ТРЕБОВАНИЯ СЛЕДУЮТ ИЗ ВТОРОЙ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ НА  ОПТИМАЛЬНЫЙ ПЛАН ПРОИЗВОДСТВА И ОПТИМАЛЬНЫЙ ВЕКТОР ОЦЕНОК РЕСУРСОВ?

Из второй теоремы двойственности в данном случае сле¬дуют такие требования на оптимальную производственную программу X=(x1,x2, …, xn) и оптимальный вектор оценок ресурсов Y=(y1,y2, …, ym).

Требования (I). Если yi>0, то

n
∑ aij•xj=bi;
j=1

a если   

n
∑ aij•xj<bi,
j=1

то yi=0.

Требования (I)  можно интерпретировать так: если оценка yi единицы ресурса i-го вида положительна, то при опти¬мальной производственной программе этот ресурс использу¬ется полностью; если же ресурс используется не полностью, то его оценка равна нулю.

Требования (II). Если xj>0, то
m
∑ aij•yi=cj;
i=1

а если
m
∑ aij•yi>cj,
i=1

то xj=0.

Из требований (II) следует, что если j-й вид продукции xj вошел в оптимальный план, то он в оптимальных оценках не убыточен; если же j-й вид продукции убыточен, то он не войдет в оптимальный план, не будет выпускаться.

Кроме нахождения оптимального решения должно быть обеспечено получение дополнительной информации о воз¬можных изменениях решения при изменении параметров системы. Эту часть исследования обычно называют анализом модели на чувствительность. Он необходим, например, в тех случаях, когда некоторые характеристики исследуемой системы не поддаются точной оценке. В лекции 1 «Основы линейного программирования» на конкретном примере (производство красок для наружных и внутренних работ  компанией «Яркие краски») мы провели анализ чувствительности модели при изменении параметров ЗЛП. 

Экономико-математический анализ решений осуществ¬ляется в двух основных направлениях: в виде вариантных расчетов по моделям с сопоставлением различных вариантов плана и в виде анализа каждого из полученных решений с помощью двойственных оценок. Вариантные расчеты могут осуществляться при неизменной структуре самой модели (постоянном составе неизвестных, способов производства, ог¬раничений задачи и одинаковом критерии оптимизации), но с изменением численной величины конкретных показа¬телей модели. Вариантные расчеты могут проводиться также при варьировании элементов самой модели: изменении кри¬терия оптимизации, добавлении новых ограничений на ре¬сурсы или на способы производства их использования, рас¬ширения множества вариантов и т.д.

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

СПИСОК  РЕКОМЕНДУЕМОЙ  ЛИТЕРАТУРЫ.

[1] Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций. СПб.: Союз, 1999. — 320 с.

[2] Таха Х.А. Введение в исследование операций. — 6-е изд. Пер. с англ. — М.: Издательский дом «Вильямс», 2001. — 912 с: ил.

[3] Шелобаев С. И. Математические методы и модели в экономике,  финансах, бизнесе: Учебное пособие для вузов. — М.: ЮНИТИ - ДАНА, 2001. - 367 с.
[4] Шикин Е. В., Чхартишвили А. Г. Математические методы и модели в управлении: Учебное пособие. — 3-е изд. — М.: Дело, 2004. — 440 с. — (Серия «Классический университетский учебник»).

[5] Экономико-математические методы и прикладные модели: Учебное пособие для вузов/ В.В. Федосеев, А.Н. Гармаш,  Д.М. Дайитбегов и др.; Под ред. В.В. Федосеева. — М.:  ЮНИТИ, 1999. - 391 с.