Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»


При этом необходимо:


1)    найти начальную допустимую вершину (начальное допустимое решение задачи линейного программирования);


2)    знать, как перейти в вершину с лучшим значением целевой функции;


3)    знать критерий (способ проверки), позволяющий определять на каждом шаге, является ли достигнутая вершина оптимальной точкой;


4)    уметь выявлять отсутствие решения, т.е. неограниченность целевой функции в направлении отыскания экстремума (снизу — при отыскании min, сверху — при отыскании max).


Симплекс-метод — метод итеративный, поэтому его можно разбить на четыре шага.


Шаг 1. Отыскание начального допустимого базисного решения задачи линейного программирования. Если задача линейного программирования записана в стандартном виде канонической формы, т.е. в каждом уравнении есть базисная переменная, то НДБР формируют из соответствующих базисных переменных, приравнивая их к правым частям системы ограничений. При этом свободные переменные приравнивают к нулю.


Рассмотрим задачу линейного программирования n=5, m=3:


max(- x1 — 9x2 — 7x3 + x4 + 136x5), x1 + 2x4 = 20, x2 + x4 + x5 = 8, x3 + 9x4 + 8x5 = 4,


xi, x2, x3, x4, x5 > 0.


Очевидно, что в качестве НДБР можно взять следующее решение задачи: (20; 8; 4; 0; 0). Действительно, это решение является, во-первых, допустимым, так как при подстановке его в систему ограничений получим верные числовые равенства, во-вторых — базисным, так как лишь три его переменные ненулевые (так как m=3), оставшиеся две переменные нулевые.


Если же задача линейного программирования записана в канонической форме, то для отыскания начального допустимого базисного решения используют метод искусственного базиса. Суть этого метода заключается во введении в каждое уравнение системы (4) искусственной базисной переменной xn+1, xn+2, …, xn+m > 0 с единичной диагональной подматрицей. В результате переменных задачи будет n+m, а ограничения примут вид

Скачать в pdf «Экстремальные модели менеджмента и экономики»