Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Симплексный метод основан на последовательном переходе от одного опорного плана задачи линейного программирования к другому, при этом значение целевой функции изменяется. Рассмотрим алгоритм симплексного метода на примере задачи планирования товарооборота.
Коммерческое предприятие реализует несколько n–товарных групп, располагая m ограниченными материально-денежными ресурсами bi(). Известны расходы ресурсов каждого i-вида на реализацию продажи единицы товарооборота товаров по каждой группе, представленной в виде матрицы A=(ai,j),bi≥0, m<n и прибыль cj получаемая предприятием от реализации единицы товарооборота товаров j группы. Определить объем и структуру товарооборота xj(), при которых прибыль коммерческого предприятия была бы максимальной.
1. Математическую модель задачи запишем следующим образом:
Определить , который удовлетворяет ограничениям вида:
и обеспечивает максимальное значение целевой функции
Алгоритм симплексного метода включает следующие этапы.
2. Составление первого опорного плана
Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств. Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными:
где xn+1 – базисные переменные, хi – свободные переменные.
Решим эту систему относительно базисных переменных:
а функцию цели перепишем в таком виде:
Полагая, что основные переменные х1 = х2=х3=...=хn=0 получим первый опорный план =(0,0,..,0, b1, b2,..., bm); , заносим его в симплексную таблицу 3, которая состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной. Она заполняется коэффициентами функции цели, взятыми с противоположным знаком.
3. Проверка плана на оптимальность
Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны (≥0), то план табл. 3 =(x1, x2,..., xn) задачи табл. 2 является оптимальным. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный и его можно улучшить. Тогда переходим к следующему этапу алгоритма.
4. Определение ведущих столбца и строки
Из отрицательных коэффициентов индексной строки выбираем наибольший по абсолютной величине, что и определяет ведущий столбец, который показывает, какая переменная на следующей итерации перейдет из свободных в базисные.
Затем элементы столбца свободных членов симплексной таблицы делим на соответствующие только положительные элементы следующего столбца. Результаты заносим в отдельный столбец . Строка симплексной таблицы, соответствующая минимальному значению , является ведущей. Она определяет переменную xj, которая на следующей итерации выйдет из базиса и станет свободной.
Элемент симплексной таблицы, находящейся на пересечении ведущих столбца и строки, называют разрешающими и выделяет кружком.
5. Построение нового опорного плана
Переход к новому плану проводится пересчетом симплексной таблицы по методу Жордана-Гаусса. Сначала заменим переменные в базисе, т.е. вместо хi в базис войдет переменная хj, соответствующая направляющему столбцу.
Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления внесем в строку следующей симплексной таблицы, соответствующего введенной в базис переменной хj. В результате этого на месте завершающего элемента в следующей симплексной таблице будем иметь 1, а в остальных клетках j столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника: ,
где СТЭ - элемент старого плана,
РЭ - разрешающий элемент,
А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
6. Полученный новый опорный план опять проверяется на оптимальность в соответствии с этапом 3 алгоритма
При решении задачи линейного программирования на минимум целевой функции, признаком оптимальности плана является отрицательные значения всех коэффициентов индексной строки симплексной таблицы.
Если в направляющем столбце все коэффициенты аij≤0, то функция цели неограничена на множестве допустимых планов, т.е. и задачу решить нельзя.
Если в столбце симплексной таблицы содержатся два или несколько одинаковых наименьших значения, то новый опорный план будет вырожденным (одна или несколько базисных переменных станут равными нулю). Вырожденные планы могут привести к зацикливанию, т.е. многократному повторению процесса вычислений, не позволяющему завершить задачу. С целью исключения этого для выбора направляющей строки используют способ Креко, который заключается в следующем. Делим элементы строк, имеющие одинаковые наименьшее значение , на предполагаемые разрешающие элементы, а результаты заносим в дополнительные строки. За ведущую строку выбирается та, в которой раньше встречается меньшее число при чтении таблицы слева направо по столбцам.
Если в оптимальный план вошла дополнительная переменная хn+1, то при реализации такого плана имеются недоиспользованные ресурсы i-ro вида в количестве, полученном в столбце свободных членов симплексной таблицы.
Если в индексной строке симплексной таблицы оптимального плана находится нуль, принадлежащий свободной переменной, не вошедшей в базис, а в столбце, содержащем этот-нуль, имеется хотя бы один положительный элемент, то задача имеет множество оптимальных планов. Свободную переменную, соответствующую указанному столбцу, можно внести в базис, выполнив соответствующие этапы алгоритма. В результате будет получен второй оптимальный план с другим набором базисных переменных.
Дата публикования: 2015-03-29; Прочитано: 323 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!