Первый подход к поиску базиса.
В случае если в ограничениях задачи левая часть < либо правой, используется первый подход к поиску базиса. Исходная система ограничений- неравенств преобразуется в систему равенств путём добавления свободных переменных, коэффициенты при которых равны единице. В каждое из ограничений системы добавляют свою свободную переменную. Для наглядности расположим их по диагонали. С экономической точки зрения свободные переменные представляют собой неиспользованные ресурсы, следовательно, их «цена» в целевой функции = 0, т. е. они не учитываются в целевой функции. Коэффициенты при свободных переменных образуют единичную матрицу, определитель которой = 1. Это означает, что система не вырожденная и векторы-столбцы, компонентами которых являются коэффициенты соответствующих свободных переменных, линейно не зависимы и образуют базис. Симплекс-метод основан на разложении векторов по базису. Условия задачи можно записать в виде векторов. = P1 =P2…… = Pn = P0 -вектор решений.
Пример задачи оптимизации и её решение Симплекс-методом. Необходимо загрузить судно в порту 3-мя родами груза а, б, в. Грузоподъёмность судна = 2000т (Qp); грузовместимость(W) = 3080м3; удельный погрузочный объём каждого груза: Wа =2, 1м3/т Wб = 1, 5м3/т Wв = 1, 7м3/т Max возможное время погрузки (Тnmax) = 36ч = 2160 мин Удельное время погрузки каждого рода груза: tа = 0, 8мин/т tб = 0, 9мин/т tв = 1, 3мин/т Имеется в порту в наличии груза: а = 900т б = 1300т в = неограниченное количество За перевозку 1т груза взимается провозная плата: Са = 8 у. е. Сб = 7, 5 у. е. Св = 7 у. е. Необходимо составить оптимальный план загрузки судна на max дохода Обозначим: х1 – количество груза а, загруженного в оптимальном плане. х2 – количество груза б, загруженного в оптимальном плане. х3 – количество груза в, загруженного в оптимальном плане. Целевая функция - доход Z = 8x1 + 7, 5x2 + 7x3 → max
Ограничения. Перейдём от системы неравенств к системе равенств, добавляя свободные переменные.
х4 – неиспользуемая грузоподъёмность х5 – неиспользуемая грузовместимость х6 – неиспользуемое до max время погрузки. х7 – недопогруженное количество груза а. х8 – недопогруженное количество груза б.
Представим условия (т. е. ограничения) в виде векторов. Р1 = Р2 = Р3 = Р4 =
Р5 = Р6 = Р7 = Р8 = Р0 =
Вектора Р1, Р2, Р3, образованные из коэффициентов при реальных переменных, называются структурными. Вектора Р4, Р5, Р6, Р7, Р8 называются линейно не зависимыми (свободными) векторами, Ро – вектор решений. Данная задача решается относительно m линейно независимых базисных векторов. В данном случае, это свободные векторы (образующиеся из коэффициентов при свободных переменных) Р4 - Р8.
Алгоритм решения предусматривает построение симплекс-таблиц.
Z j – симплекс-оценка Zj = Z j – Cj – признак оптимальности в симплекс-методе. Если задача решается на max и значение последней строки ≥ 0 по всем столбцам, то план является оптимальным. Если задача решается на min и значение последней строки 0, то план так же является оптимальным. Если при решении задач на max. хотя бы у одного вектора значение Zj – Cj < 0, то план не оптимален и требует улучшения. В общем виде первоначальная симплекс-таблица выглядит следующим образом:
Симплекс-метод . Алгоритм перехода от одного допустимого плана к другому. Данный алгоритм позволяет превратить неоптимальный план в оптимальный. Алгоритм имеет следующие этапы: I. Определятся вектор, который вводится в базис. Это вектор, который имеет max. нарушение признака оптимальности. Столбец, который соответствует вводимому в базис вектору, называется ключевым, его индекс обозначается буквой k . В нашем примере k = 1 II. Определяется вектор, который выводится из базиса. Это тот вектор, у которого имеет место следующее соотношение. для xik > 0 xi – элементы вектора решений (столбца Р0) xik – элементы ключевого столбца. Строка, которая соответствует минимуму, т. е. выводимому из базиса вектору, называется ключевой строкой, её индекс обозначается буквой r. Элемент таблицы, который находится на пересечении k-ого столбца и r-той строки, называется генеральным элементом и обозначается xrk. III. Определяется новые значения элементов вектора решений. Р’0 = P0 - ΘPk х’i = xi - Θxik Для ключевой строки значение Р0 = Θ, т.е. х’r = q IV. Определяется новое значение ключевой строки x’r j = V. Определяются новые значения всех остальных элементов симплекс-таблицы x’ij = xij - Где – элемент данного вектора в ключевой строке. – соответствующий элемент в ключевом столбце. – генеральный элемент.
Популярное: Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (227)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |