КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Опишите процесс решения задачи линейного программирования симплекс-методом
Линейное программирование первоначально развивалось как направление, разрабатывающее новые подходы к решению задач минимизации выпуклых функций, т. е. в рамках выпуклого программирования. Выпуклое программирование посвящено нахождению экстремума выпуклой целевой функции на выпуклом множестве, обычно задаваемом в виде системы выпуклых неравенств. Пусть мы имеем задачу линейного программирования: Целевая функция вида: и ограничения , Переобозначим свободные коэффициенты ограничений aj0=bj. Приведем матрицу ограничений к каноническому виду: Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения: x1, x2 , ... , xr - базисные переменные; xr+1, xr+2 , ... , xn - свободные переменные. ; . (2.41) По последней системе ограничений и целевой функции построим симплекс-таблицу. Таблица 2.3 Симплекс-таблица Все дальнейшие преобразования связаны с изменением содержания этой таблицы. Нижняя строка элементов аок, называется индексной. Элементы индексной строки вычисляются следующим образом: означает номер соответствующей строки. Поскольку на первом шаге заполнения таблицы все элементы сn+I равны нулю, то элементам индексной строки присваиваются значения соответствующих элементов целевой функции данного столбца, взятые с обратным знаком, т.е. а0k= -Ск. Последняя строка таблицы служит для определения направляющего столбца. Элемент а00 равен значению целевой функции, которое вычисляется по формуле , к - номер базисной переменной (индексация идет по строкам таблицы). В столбце Вх записываются базисные переменные, на первом шаге в качестве базисных выбирают фиктивные переменные {хп+к }, . В дальнейшем фиктивные переменные необходимо вывести из базиса. В столбец С записываются коэффициенты при хп+к, на первом шаге значения этих коэффициентов равны нулю. Для перехода от базиса фиктивных переменных к базису реальных переменных применяют следующие правила: * в качестве направляющего столбца выбирают столбец Аj , для которого выполняется условие a0j = min{aol), при а0l < 0, т.е. выбирается минимальный элемент, при условии, что этот элемент отрицательный; * выбирают направляющую строку, для чего каждый элемент столбца свободных членов делится на соответствующий элемент направляющего столбца, элемент столбца свободных членов находится в одной строке с элементом направляющего столбца -. Из всех возможных соотношений выбирается минимальное при условии, что arj > 0, 1 ≤ r ≤ т. Применяя сформулированные правила, определяем направляющий элемент. Далее выполняется шаг симплексных преобразований. Переменная, которая соответствует направляющему столбцу, вводится в базис, а переменная, соответствующая направляющей строке, выводится из базиса. При этом для переменной, вводимой в базис, изменяется соответствующее значение коэффициента целевой функции. Вместо коэффициента сn+i соответствующего старой базисной переменной, в таблице записывается значение коэффициента целевой функции при переменной, вводимой в базис. Если направляющий элемент аij, то переход от данной таблицы к следующей осуществляется с использованием следующих правил. 1. Для всех элементов направляющей строки где к - номер шага (к = 1, 2,...); i - номер направляющей строки; j - номер направляющего столбца; , т.е. все элементы направляющей строки делим на направляющий элемент, в итоге направляющий элемент стал равным единице; . 2. В направляющем столбце необходимо получить , для всех , r≠i, при , т.е. в направляющем столбце должны быть все нули кроме направляющего элемента, который равен единице. Для всех остальных элементов, включая индексную строку, производим вычисления Симплексные преобразования повторяют до тех пор, пока не реализуется один из двух возможных исходов: а) все a0l ≥0 - это условие оптимальности базиса последней таблицы; б) найдется такой элемент a0l< 0, при котором все элементы столбца аrj ≤ 0, - это признак неограниченности целевой функции на множестве допустимых решений.
|