Методы оптимальных решений
Лекция 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 с.