Методы оптимизации в экономике (стр. 2 )

Из рисунка видно, что точкой, в которой прямаяZ касается ОДР является точкой А. Находим ее координаты, решая систему уравнений:

Получим x1= 27, x2= 48.

Точка A (27;48).

Максимальный доход составляет Zmax= 427 + 648 = 396 руб.

Ответ. Для получения максимальной стоимости изделий 396 рублей необходимо изготовить изделий А 27 единиц, изделий В 48 единиц.

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

1.   Если оптимальное решение существует, то оно лежит на границе ОДР.

2.   Если решение единственное, то оно достигается в одной из вершин ОДР.

3.   Если решений множество, то они достигаются на одной из сторон выпуклого многоугольника ОДР.

4.   Решение, лежащее в одной из вершин ОДР, является опорным решением, а сама вершина - опорной точкой.

5.   Для того, чтобы найти опорное решение достаточно перебрать все вершины ОДР (опорные точки) и выбрать ту, где целевая функция достигает максимума.

1.3. Симплексный метод

Алгебраический метод решения (симплекс-метод) разработан американским математиком Д. Данцигом и опубликован в 1951 г. В его основе лежит использование элементарных преобразований матрицы ограничений канонической задачи линейного программирования (метод Жордана-Гаусса).

Переход от общей задачи линейного программирования (1), (2), (4) к задаче в канонической форме (1), (3), (4), осуществляется с помощью введения mнеотрицательных дополнительных переменных. Эти переменные добавляются к каждому из неравенств системы (2), обращая их в равенства, и входят в функцию цели с коэффициентами, равными нулю. В этом случае задача линейного программирования в канонической форме формулируется так: требуется найти совокупность неотрицательных чисел

, , (5),

которые удовлетворяют системе линейных уравнений:

(6)

и дают экстремум функции цели: max(min)(2.7)

Правомерность перехода от общей задачи к задаче в канонической форме основывается на теореме: неотрицательное решение системы неравенств (2.2) является решением системы уравнений (6). Справедливо и обратное утверждение.

Рассмотрим задачу линейного программирования на нахождение минимума целевой функции.

Справедливы теоремы.

Теорема 1. Если для некоторого фиксированного индекса j выполняется условие Zj - Cj> 0, то можно построить хотя бы один опорный план, для которого значение целевой функции Z будет меньше первоначального, т. е. Z < Z0.

Теорема 2. Если для некоторого опорного плана`x выполняется соотношение Zj - Cj£ 0, то план`x является оптимальным.

Сформулируем алгоритм симплексного метода.

По условию задачи составляется экономико-математическая модель задачи в общем виде:

Z(x1,...xn) = c1x1+...+cnxn max

xj 0,( j = 1,….n) .

Переходят от задачи на максимум к задаче на минимум Z. Для этого целевую функцию умножают на (-1).

-Z(x1,...xn) = - c1x1 -...-cnxn min.

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

xj 0, ( j = 1,….n+m) .

Запишем систему ограничений в векторной форме:

или .

Составляется первая симплексная таблица.

Таблица 1

Базис	C	b	-C1	-C2	…	-Cn	Cn+1=0	…	Cn+m=0
a1	a2	…	an	an+1	…	an+m
an+1	Cn+1=0	b1	a11	a12	…	a1n	1	…	0
an+2	Cn+2=0	b2	a21	a22	…	a2n	0	…	0
…	…	…	…	…	…	…	…	…	…
an+m	Cn+m=0	bm	am1	am2	…	amn	0	…	1
Zj-Cj	Z0	C1	C2	…	Cn	0	…	0

Столбец “Базис” – столбец векторов, входящих в базис.

Столбец “С” – столбец коэффициентов, стоящих в целевой функции при векторах базиса.

Строка “Zj-Cj” - называется индексной строкой.

Столбец “b” - столбец ограничений по ресурсам, входящих в базис.

Столбцы a1 … am, …, am+1… an - это коэффициенты, стоящие при неизвестных в системе ограничений.

Заполним индексную строку “Zj-Cj”. Для столбца “b” это значение равно сумме попарных произведений элементов столбца “C” на элементы столбца “b”, т. е.

.

Решение находится в столбце “b”:

`x=(b1, b2 ,…, bm, 0,…, 0); Z = Z0..

Две верхние строки таблицы содержат коэффициенты функции цели и n+m векторов системы ограничений.

4. Просматриваются числа Zj-Сj индексной строки.

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

5. Предположим, что базисное решение не оптимальное. Из всех положительных чисел индексной строки выбирается наибольшее по абсолютной величине, то есть . Индекс j, которому соответствует такое число индексной строки, укажет вектор, который следует ввести в базис. Пусть им будет . Столбец, соответствующий этому вектору, будет направляющим (ведущим).

6. Определяем направляющую (ведущую) строку. Определяется число . С этой целью компоненты базисного решения делятся на положительные компоненты ведущего вектора-столбца. Индекс i, которому соответствует , укажет вектор, который следует исключить из базиса. Пусть им будет вектор . Строка, соответствующая этому вектору, будет направляющей (ведущей). Элемент xij, стоящий на пересечении ведущего столбца и ведущей строки, называется разрешающим элементом.

7.  После выбора разрешающего элемента симплексная таблица преобразовывается по формулам прямоугольника:

, (8)

aij- разрешающий элемент матрицы, aij0.

После преобразования получим: все остальные элементы в столбце с разрешающим элементом преобразуются в нули. Тем самым, в соответствующей системе линейных уравнений неизвестное xj останется с коэффициентом, равным единице в i - м уравнении, а во всех остальных будет исключено.

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

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

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

1.3.1. Решение производственной задачи симплексным методом

Требуется максимизировать функцию доходов:

Z = 4x1 + 6x2 max

При наличии системы ограничений:

Сведем задачу на минимум к задаче на максимум. Для этого умножим функцию цели на (-1).

-Z=-4x1 - 6x2 min

Для приведения задачи к каноническому виду (с ограничениями - равенствами), пригодному к решению симплекс - методом, вводим дополнительные переменные x3, x4, x5 0.

Имеем:

-Z =-4x1-6x2 +0×х3+0×х4+0×х5 min.

Дополнительные переменныеx3, x4, x5 означают количество неиспользованного сырья (остаток) соответственно первого, второго и третьего вида.

Запишем задачу в векторной форме:

-Z = -4x1-6x2 +0×х3+0×х4+0×х5 min.

.

Коэффициенты при x3, x4, x5 образуют единичную матрицу. Принимаем вектора коэффициентов при x3, x4, x5 за базис.

Составим первую симплекс-таблицу (табл.2).

В столбецС запишем коэффициенты, стоявшие в целевой функции при соответствующих переменных (в нашем случае они равны нулю).

В столбец b поставим ограничения по ресурсам. Коэффициенты в столбцах а1, а2,…а5 – это коэффициенты, соответствующие переменным х1, х2,…х5 в системе ограничений, записанной в векторной форме.

Последняя строка называется индексной. Ее заполняют следующим образом. Находят сумму попарных произведений столбца b наС, затем вычитают соответствующий коэффициент при целевой функции.

Строка Zj-Cj: 0´784 + 0´552 + 0´567 = 0.

Столбец а1: 0´16 + 0´8 + 0´5 – (-4) = 4.

Столбец а2: 0´4 +0´7 + 0´6 – (-6) = 6.

Столбец а3: 0´1 +0´0 + 0´0 – 0 = 0 и т. д.

Таблица 2

Базис	C	b	с1=-4	с2=-6	с3=0	с4=0	с5=0
`a1	`a2	`a3	`a4	`a5
`a3	с3=0	784	16	4	1	0	0
`a4	с4=0	552	8	7	0	1	0
`a5	с5=0	567	5	9	0	0	1
Zj-Cj	0	4	6	0	0	0

Первое базисное решение находится в столбце b: x1 = 0; x2 = 0; x3 = 784; x4 = 552; x5 = 567. При этом Z= 0. В индексной строке имеются положительные числа 4, 6. Следовательно, план не оптимален.

Применяем алгоритм симплексного метода.

1.  Выбираем максимальный по абсолютной величине элемент, стоящий в индексной строке. Этот элемент равен 6. Ему соответствует столбец а2. Этот столбец будем называть направляющим. Выделим его в симплексной таблице.