РЕШЕНИЕ ИСХОДНОЙ ЗАДАЧИ СИМПЛЕКСНЫМ МЕТОДОМ
Симплексный метод задач линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план. Полученная модель является задачей линейного программирования, функция F – целевая функция. Она является линейной функцией своих переменных (х1,х2), ограничения на эти переменные тоже являются переменными. Необходимо найти значения переменных х1 и х2 при которых данная функция F принимает максимальное значение, при соблюдении ограничений, накладываемых на эти переменные. Решение, удовлетворяющее системе ограничения и требования не отрицательности являются допустимыми, а решение удовлетворяющие одновременно и требованиям максимизации функции в целом является оптимальным. Приведем систему к каноническому виду. Для этого введем балансовые переменные- х3, х4, х5 и получим модель в следующем виде: 3x1 +2х2+х3 = 32 4x1 + 5х2 +х4= 48 x1 + 6х2 +х5= 40 хi≥0, i=1..5. F= 6x1 + 11х2 →max. Запишем данную задачу в исходную симплексную таблицу:
Первые три строки этой таблицы содержат в условной форме систему ограничений, а именно в столбце ai 0 - записываются свободные члены уравнений. В столбцах х1, х2, х3, х4, х5 – записываются коэффициенты при соответствующих переменных этой системы. Слева от столбца ai0 , в столбце (хi), записываются базисные переменные (которые ввели для баланса), содержащиеся в соответствующих уравнениях системы. Верхняя строка и крайний верхний столбец содержат коэффициенты при соответствующих переменных в целевой функции. Последняя строка называется оценочной, а элементы строки – оценками. Первый элемент а00 представляет собой значение целевой функции на начальном этапе. а00 = 0∙32+0∙48+0∙40=0 Остальные значения обозначаются а0k , получаются в результате скалярного умножения вектора столбца Сi на вектор столбец коэффициента при неизвестном xk c последующим вычитанием соответствующего элемента верхней строки, например: а01=(0∙3+0∙4+0∙1)-6 = -6 Для получения оптимального плана необходимо, чтобы все элементы оценочной строки симплексной таблицы были неотрицательными. Для этого: 1. выбираем в исходной таблице разрешающий столбец- p. Этот столбец соответствует наибольшей по абсолютной величине отрицательной оценке. В данной задаче это будет столбец х2 (т.к |-6| < |-11| ). 2. выбираем в исходной таблице разрешающую строку – q., используя условие , т.е. 32/2=16, 48/5=9,6 , 40/6=6,66(min) На перекрестке разрешающей строки и разрешающего столбца, получим разрешающий элемент - аqp. В данной задаче разрешающим элементом будет являться 6.
3. В новой симплексной таблице элементы разрешающей строки пересчитываем по формуле: На месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы оценочной строки пересчитываем по формуле прямоугольников:
Расчет по формуле прямоугольников представлен в таблице
В полученной таблице в оценочной строке имеется отрицательный элемент - . Столбец, содержащий этот элемент, будет являться разрешающим, поэтому для нахождения разрешающей строки выполним следующее решение: : =7 : = (min) : = 40 Следовательно, на пересечении разрешающего столбца и разрешающей строки найдем необходимый элемент: .
Составляем новую таблицу - на месте разрешающего элемента ставим 1, в разрешающем столбце все элементы заменяем на - 0. остальные элементы и элементы пересчитываем по формуле прямоугольников. Получим таблицу
Все элементы оценочной строки симплексной таблицы неотрицательны, следовательно исходный план является оптимальным.
Популярное: Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (326)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |