Реферат по математическим основам теории систем на тему Линейное программирование Группа: пс-263
жүктеу/скачать 5.42 Mb.
|
- Бұл бет үшін навигация:
- 4.2.1. Представление пространства решений стандартной задачи ЛП.
| 4.2. Симплекс-метод
Общую идею симплекс-метода проиллюстрируем на примере модели для задачи фирмы Reddy Mikks. На исходная точка алгоритма – начало координат (т. A) – начальное решение. От исходной точки осуществляется переход к некоторой смежной угловой точке (т. B или т. F). Её выбор зависит от коэффициентов целевой функции. Т.к. коэффициент при xE больше коэффициента при xI, а целевая функция подлежит максимизации, требуемое направление перехода соответствует увеличению xE (т. B). Далее указанный процесс повторяется для выяснения, существует ли другая экстремальная точка, соответствующая лучшему допустимому решению. Правила выбора экстремальной точки: Каждая последующая угловая точка должна быть смежной с предыдущей. Обратный переход к предшествующей экстремальной точке не может производиться. Чтобы описать рассмотренные процедуры формальными способами, необходимо определить пространство решений и угловые точки алгебраически. Требуемые соотношения устанавливаются по таблице:
4.2.1. Представление пространства решений стандартной задачи ЛП. Модель: максимизировать целевую функцию при ограничениях На – пространство решений. Каждую точку можно определить с помощью Для идентификации нужной точки воспользуемся тем, что при ограничения модели эквивалентны равенствам, которые представляются соответствующими рёбрами пространства решений. Анализируя , заметим, что можно упорядочить, исходя из того, какое значение (нулевое или ненулевое) имеет данная переменная в экстремальной точке.
Из таблицы выделим закономерности: Стандартная модель содержит четыре уравнения и шесть неизвестных, поэтому в каждой из экстремальных точек (6–4) переменные должны иметь нулевые значения. Смежные экстремальные точки отличаются только одной переменной в каждой группе (нулевых и ненулевых переменных). Если линейная модель стандартной формы содержит уравнений и неизвестных, то все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы уравнений, в которых m-n переменных равны нулю. Однозначные решения такой системы – базисные решения. Если они удовлетворяют требованию неотрицательности правых частей, то это – допустимое базисное решение. Переменные, равные нулю – небазисные, остальные – базисные. Каждую следующую экстремальную точку можно определить определить путём замены одной из текущих небазисных переменных текущей базисной переменной. В нашем примере при переходе из т. A в т. B необходимо увеличивать небазисную переменную от исходного нулевого значения до значения, соответствующего т. B. В т. B s2 обращается в нуль (становится небазисной). Т.о., происходит взаимообмен xE и s2 между небазисными и базисными переменными. Включаемая переменная – небазисная в данный момент переменная, которая будет включена в множество базисных переменных на следующей итерации. Исключаемая переменная – базисная в данный момент переменная, которая на следующей итерации подлежит исключению из множества базисных переменных. жүктеу/скачать 5.42 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||