В нижней строчке симплекс-таблицы необходимо отыскать отрицательные числа (не считая коэффициент Со). Если таких чисел нет, то данное базисное решение является оптимальным.
4. Пусть элемент Сj<0,тогда в j-ом столбце необходимо найти положительный элемент. Если все коэффициенты этого столбца отрицательные, то решения не существует. Если положительный коэффициент в j-ом столбце один, то выбранную строку с номером i надо поделить все коэффициенты на число aij.Результат деления записываем в новую симплекс-таблицу. Если же положительных коэффициентов несколько, необходимо составить отношение bi/aij и из полученных значений выбрать наименьшее, соответствующее i-ой строке. 6. В новой симплекс-таблице в столбце базисных неизвестных вместо xi пишется xj. Продолжается заполняться таблица. В столбце с номером j необходимо получить нули(включая строку с целевой функцией). Для этого надо умножить i-ую записанную строку на нужное число и сложить с остальными строками. В результате осуществился переход к новому базису, при этом значение целевой функции увеличилось. Алгоритм симплекс-метода. Пусть система приведена к каноническому виду. X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 X2+q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 X3+q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 ……………………………………………………… Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm В ней m базисных переменных, k свободных переменных. m+k=n - всего переменных. Fmin= C1X1+ C2X2+ C3X3+....+ CnXn Для дальнейших рассуждений вычислений будем пользоваться первой симплекс таблицей (таблица1). Таблица 1.Симплекс таблица
Первый столбец - коэффициенты в целевой функции при базисных переменных. Второй столбец - базисные переменные. Третий столбец - свободные члены (hi00). Самая верхняя строка - коэффициенты при целевой функции. Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений. Основное поле симплекс метода - система коэффициентов из уравнения. Последняя строка - служит для того, чтобы ответить на вопрос: «оптимален план или нет». Индексная строка позволяет нам судить об оптимальности плана: При отыскании Fmin в индексной строке должны быть отрицательные и нулевые оценки. При отыскании Fmax в индексной строке должны быть нулевые и положительные оценки. Переход ко второй итерации: Для этого отыскиваем ключевой (главный) столбец и ключевую (главную) строку. Ключевым столбцом является тот в котором находится наибольший положительный элемент индексной строки при отыскании Fmin или наименьший отрицательный элемент при отыскании Fmax. Ключевой строкой называется та, в которой содержится наименьшее положительное частное от деления элементов столбца H на соответствующие элементы ключевого столбца. На пересечении строки и столбца находится разрешающий элемент. На этом этапе осуществляется к переходу к последующим итерациям. Переход к итерациям: Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своим коэффициентом. Заполняется строка вновь введенного базиса путем деления соответствующих элементов выделенной строки предыдущей итерации на разрешающий элемент. Если в главной строке содержится нулевой элемент, то столбец, в котором находиться этот элемент переноситься в последующую итерацию без изменения. Если в главном столбце имеется нулевой элемент, то строка, в которой он находиться переноситься без изменения в последующую итерацию. Остальные элементы переносятся по формуле:
Решение задачи оптимизации. Построение аналитической модели. В цехе имеется токарный станок и станок-автомат. Цех выпускает детали 1,2 и 3 в комплекте: на каждую деталь 1 – по 2 детали 2 и 3. Часовая производительность станков по каждой из деталей приведена в таблице: Таблица 1. Часовая производительность станков Станки |
Детали | |||||||||||||||||||||||||||||||||||||||||||||||||||
1 | 2 | 3 | ||||||||||||||||||||||||||||||||||||||||||||||||||
1. Токарный | 5 | 5 | 10 | |||||||||||||||||||||||||||||||||||||||||||||||||
2. Автомат | 15 | 15 | 10 |
2019-12-29 | 215 | Обсуждений (0) |
5.00
из
|
Почему 1285321 студент выбрали МегаОбучалку...
Система поиска информации
Мобильная версия сайта
Удобная навигация
Нет шокирующей рекламы