Решение задач и выполнение научно-исследовательских разработок: Отправьте запрос сейчас: irina@bodrenko.org
Методы оптимальных решений
Лекция 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 с.