A=[a1, a2, …an],
которую называют матрицей условий задачи.
В векторной форме выражение (4.6) записывается в виде скалярного произведения векторов с и х, а левая часть системы уравнений (4.7) записывается в виде произведения матрицы А на вектор х. Теперь в очень краткой форме можно записать основную задачу линейного программирования:
найти максимум функции FЦ=сх
при условии Ах≤b, х≥0; (4.9)
или
найти минимум функции FЦ= - сх
при условии - Ах≥-b, х≥0. (4.9')
Чтобы перейти к стандартной процедуре решения основной задачи линейного программирования симплексным методом, необходимо, чтобы среди векторов aj было m единичных. Так, в системе уравнений (4.7) векторы а1-аm – единичные, т. е. у каждого из этих векторов имеется только одна компонента aij (i=1,2,…m), не равная нулю, и она равна единице. Если количество единичных векторов aj меньше m, то в соответствующие уравнения ограничений необходимо ввести дополнительные переменные хj, с помощью которых уравнения ограничений (4.9) будут записаны в канонической форме (4.7). В общем виде это производится методом искусственного базиса [9]. Однако в большинстве случаев недостающие переменные хj можно просто прибавить в соответствующие уравнения ограничений, где их до того не хватало (см. пример 4.1.). Это возможно, если ограничения в условиях задачи представлены в виде неравенств.
Процедура симплексного метода основана на следующих положениях.
Совокупность точек х в n-мерном евклидовом пространстве Еn, ограниченная условиями (4.9), образует область допустимых решений рассматриваемой задачи. Каждую точку х=(х1,х2,…хn) из указанной области в экономических расчетах принято именовать планом (допустимым). Точка, в которой достигается либо максимум, либо минимум заданной целевой функции, называется оптимальной точкой, или оптимальным планом. В пространстве Еn область допустимых решений образуется в результате пересечения полупространств х≥0 (при n=2 – полуплоскостей) и Ах≤b или - Ах≥-b, заданных условиями (4.9), и существует в виде многогранника решений. Оптимальная точка (оптимальный план) является одной из вершин многогранника решений. Любые m линейно независимых векторов aj (j=1,2,…n, m≤n), удовлетворяющих системе уравнений (4.7), порождают точку х=(b1,b2,…bm,0,…0), являющуюся вершиной многогранника решений. Такую точку принято называть угловой точкой или опорным планом. Оптимальная точка является одной из угловых точек. В этом нетрудно убедиться на примере нахождения максимального значения функции двух переменных (n=2)
(4.10)
при условиях
(4.11)
Каждое из неравенств (4.11) геометрически определяет полуплоскость в соответствии с граничными прямыми
Если система неравенств (4.11) совместна, то получим многоугольник (вырожденный многогранник, так как n=2) решений вроде приведенного на рис.4.2.
Рис. 4.2. Многоугольник решений
Область допустимых решений на рис.4.2 отмечена штриховкой ее границ. На графике рис.4.2 изображены также линии Fц=const, соответствующие уравнению (4.10) при с1>0 и с2>0. Если перемещать линию Fц в направлении вектора с=(с1, с2), то значение Fц будет возрастать и достигнет максимального значения Fцm в угловой точке А. Следовательно, точка А является оптимальной, а ее координаты определяют оптимальный план решения данной задачи.
Процедура симплексного метода заключается в том, что переходят от одной угловой точки (опорного плана) к другой угловой точке (к другому опорному плану) таким образом, что значение целевой функции обязательно увеличивается (при поиске максимума целевой функции) или обязательно уменьшается (при поиске минимума). При этом указываются признаки достижения максимума или, соответственно, минимума целевой функции.
Первые m единичных векторов аj системы уравнений (4.7)составляют базис поиска оптимального плана. Поскольку оптимальная точка является одной из угловых точек, то искать ее следует путем замены одного из векторов базиса на один из векторов аj (j≥m+1), до того не входивших в состав базиса. После ввода в базис вектора аj значение целевой функции можно рассчитать по формуле
(4.12)
где Fцо – предыдущее значение целевой функции;
л – коэффициент пропорциональности, значение которого определяется в зависимости от того, какой вектор выводится из базиса.
Параметр Дj определяет величину и знак приращения, которое получает целевая функция после ввода в базис нового вектора аj. Если Дj>0, то целевая функция убывает (Fцj <Fцо), а при Дj<0 целевая функция увеличивается. Знак Дj является критерием полезности ввода нового вектора в базис. При поиске максимума имеет смысл вводить в базис только такой вектор, которому соответствует Дj<0, а при поиске минимума поиск оптимального режима (оптимального плана) продолжают лишь тогда, когда находится вектор, ввод которого в базис приводит к Дj>0 и соответственно– к уменьшению Fц. Значение Дj рассчитывается по формуле
(4.13)
где сi-первые 
коэффициентов целевой функции (4.6);
аij – коэффициенты при хj (j=1,2,…n) системы уравнений (4.7).
При j≤m, т. е. для m единичных векторов, входивших перед этим расчетом в состав базиса, согласно (4.13) получим Дj=0.
Рассмотрим более подробно поиск оптимального режима, когда последний соответствует максимуму целевой функции. Сначала перечислим признаки оптимальности режима (опорного плана).
1) Опорный план x*=(x1*,x2*,…xm*,0,0,…0) решения задачи (4.6)–(4.8) является оптимальным, если Дj ≥ 0 для любого j (j=1,2,…n).
2) Если Дk < 0 для некоторого j=k и среди чисел аik нет положительных, то целевая функция (4.6) не ограничена.
3) Если Дk < 0, но среди чисел aik есть положительные ( не все aik ≤ 0), то существует опорный план xґ такой, что Fц(xґ) > Fц(x).
Далее составляем таблицу 4.1а. В табл. 4.1а первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют.
Таблица 4.1а
i | Базис | сб | b | с1 | с2 | … | cr | … | cm | cm+1 | … | ck | … | cn |
а1 | а2 | … | ar | … | am | am+1 | … | ak | … | an | ||||
1 | а1 | c1 | b1 | 1 | 0 | … | 0 | … | 0 | a1m+1 | … | a1k | … | a1n |
2 | a2 | c2 | b2 | 0 | 1 | … | 0 | … | 0 | a2m+1 | … | a2k | … | a2n |
… | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
r | ar | cr | br | 0 | 0 | … | 1 | … | 0 | arm+1 | … | ark | … | arn |
… | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
m | am | cm | bm | 0 | 0 | … | 0 | … | 1 | amm+1 | … | аmk | … | amn |
m+1 Fц0 0 0 … 0 … 0 Дm+1 … Дk … Дn Исходные данные таблицы 4.1а соответствуют опорному плану х=(b1,b2,…bm,0,…0).
Таблица 4.1б
i | Базис | сб | b | с1 | с2 | … | cr | … | cm | cm+1 | … | ск | … | cn |
а1 | а2 | … | ar | … | am | am+1 | … | aк | … | an | ||||
1 | а1 | c1 | b′1 | 1 | 0 | … | a′1r | … | 0 | a′1m+1 | … | 0 | … | a′1n |
2 | a2 | c2 | b′2 | 0 | 1 | … | a′2r | … | 0 | a′2m+1 | … | 0 | … | a′2n |
… | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
r | ак | ск | b′r | 0 | 0 | … | a′r r | … | 0 | a′r m+1 | … | 1 | … | a′r n |
… | … | … | … | … | … | … | … | … | … | … | … | … | … | … |
m | am | cm | b′m | 0 | 0 | … | a′m r | … | 1 | a′mm+1 | … | 0 | … | a′m n |
m+1 F′ц0 0 0 … Д′r … 0 Д′m+1 … 0 … Д′n
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
