"Симплексный метод в экономических задачах" (стр. 2 )

откуда :

X1опт = 24, Х2опт = 14

Максимальная прибыль (максимум целевой функции (Р)) исчисляется, как:

Р = 45* X1опт + 80* Х2опт

Р = 45*24 + 80* 14 = 2200

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

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

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

Возникает практический вопрос: что произойдет с максимальной прибылью предприятия (целевой функцией) если изменится объем того или иного ресурса. Подобные вопросы являются основными для экономической теории планирования и управления производством. На практике важно не только найти оптимальные решения, но и знать конъюнктуру издержек, их прогноз и прибыльность. Ответ на эти вопросы можно получить решив другую, симметричную прямой - двойственную задачу. Графический метод решения двойственной прямой задаче позволяет оценить и спрогнозировать степень использования различных ресурсов. К тому же графический метод являегся наглядной графической иллюстрацией (как и прямой мегод - Рис.1) общих принципов решения оптимизационных задач симплекс-методом.

1.2. - Рассмотрим графический способ решения двойственной задачи.

Математическую модель двойственной задачи формулируют исходя из исходных данных обшей задачи и представляют в следующем виде:

Установить такие оценки для каждого из применяемых ресурсов (у1 и у2), которые при известных ограничениях по прибыльности единицы продукции :

5*у| + 10*у2≥45 

  20*у1 + 15*у2≥80        

и условии неотрицательности персменных:

  у| , у2  ≥ 0         

обеспечат минимальные совокупные затраты (минимум целевой функции Р):

400*у1+450*у2 = Р->шiп 

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

Система неравенств двойственной задачи содержит две переменные (у1, у2) и поэтому также, как и прямая задача, легко решается графическим путем.

На Рис.2 приводится построение геометрического изображения модели (2.1-2.4) в пространстве  двух измерений  в декартовой системе координат (у1, у2). По горизонтальной оси откладываются относительные оценки первою ресурса, по вертикальной - второго.

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

Условия ограничения  требуют, чюбы точки y1  и y2 (соответствующие относительным оценкам первою и второю ресурсов) находились в той части (области) неотрицательною квадранта, которая удовлетворяет этим условиям.

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

5*у| + 10*у2=45

20*у1 + 15*у2=80

соответствующих минимально-допустимым значениям соответствующих неравенств:

5*у| + 10*у2≥45

20*у1 + 15*у2≥80

Так, олну граничную прямую  находят по двум точкам (Е и Р), расположенным на осях координат:

при у1=0, у2=45/10=4.5,  Е (0:4.5)

при у2=0, у1=45/5 =9,  F (9:0)

Полученные точки Е и Р соединяют прямой и тем самым фиксируют нижнюю (минимизирующую) границу использования первого ресурса.

По такому же принципу находят вторую граничную прямую:

при у1=0, у2=80/15=5,3  G (0:5,3)

при у2=0, у1=80/20 =4,  H (9:0)

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

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

Определение оптимального плана (решения) задачи в этой области производят посредством минимизации целевой функции

400*у1+450*у2 = Р->шiп.

Для этой цели совершим процедуру, примененную ранее (см. Рис.1) для решения прямой задачи. То есть, вначале определим расположение прямой целевой функции, проходящей через начало координат по уравнению

Р=400*у1+450*у2= 0 

С экономических позиций это означает такое состояние предприятия, при котором оно не использует никакие ресурсы и не имеет ресурсных затрат. То есть, целевая функция находится вне области допустимых решений. Затем будем смещать целевую функцию (придав ей определенные числовые значения и совершив построение ее прямой) вверх (параллельно самой себе) до первого соприкосновения с областью допустимых решений. Минимальное значение целевая функция в этом случае получит на нижней границе (заштрихованной) области допустимых решений в точке К1 - Рис.2. Координаты этой точки К1 (вершины многоугольника) (у1опт, у2опт) соответствуют оптимальным оценкам обоих видов ресурсов. Дальнейшее перемещение целевой функции вверх нецелесообразно, так как приведет к ее нежелательному увеличению. Поскольку точка К1 находится на пересечении линейных ограничений, ее координаты  принадлежат обеим прямым и определяются (как и ранее для прямой задачи) решением системы из двух уравнений :

5*у I + 10*у2 =45

20*у,+ 15*у: =80

откуда :        у1 = 1. y2 = 4.

Минимальные затраты на ресурсы определяются. как:

400*y1+ 450*у2= Р

400*1+450*4 =2200

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

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

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

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

2. АЛГЕБРАИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ СИМПЛЕКСНОГО МЕТОДА

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

Обычная матрично-векторная форма:

целевая функция:

  ст * х = Р -> max         (2. 1)

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

        A * x = b         (2.2)

условия  неотрицательности:

  x ≥ 0         (2.3)

Система линейных  уравнений (2.2) представлена в виде матричного  уравнения – (A*x=b). Если матрица (A) квадратная (неособенная) существует единственное оптимальное решение:

       x = A-1 * b        (2.4)

Если  неизвестных больше, чем уравнений1 (n>m) - существует множество решений. Тогда обычную матрично-векторная форму,  для  однозначного решения задачи, можно  представить в  блочной форме. 

Блочная матрично-векторная форма:

целевая функция:

сNт * XN + сBт * XB = Р-> тах  (2.5)

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

B*XB +N*XN = bj         (2.6)

условия  неотрицательности:

XB ≥ 0  (2.7)

XN = 0  (2.8)

       где:

- исходная матрица (А) разбита на  лве  подматрицы -  квадратную (mxm) базисную (В),  с единственным решением,  и - небазисную  (N);

- вектор переменных (x) разбит на базисные (XB)  и  небазисные (XN):

- коэффициенты при целевой функции (2.5) (сT) разбиты на –  базисные (сTB) и небазисные (сTN).  в соответствии с разбиением (A). 

Из (2.6)  найдем  алгоритм решения задачи:

  XB = B-1* bj  - XN*N* В-1  (2.9)

  P  - после подстановки (Xв) в (2.5):

P = сBт *B-1 * bj  - (сBт * В-1* aNq -  cтN) * XN  (2.10)

где:

сBт * В-1 = р т – вектор оценок ресурсов базисной матрицы,

aNq  - единичный вектор-столбец коэффициентов основной переменной небазисной матрицы,

рТ * aNq – оценка небазисной переменной в формате базиса.

Ключевую роль при решении задачи симплекс-методом играет квадратная (m x m) матрица (В), которая имеет  единственное решение.  Она, по существу является вершиной многогранника допустимых решений, целенаправленный перебор которых (начиная с исходной, в начале координат, до вершины, с ортимальным значенияем  целевой функции) является  аалгебраическим решением задачи.

Так как вектор небазисных  переменных в базисе не представлен  (XN=0), что  обращает  в нуль  последний член  правой части уравнения (2.10), то  базисные переменные  (XB) и целевая функция (P) представляют  первым  членом  правой части уравнения (2.9 - 2.10).