Читайте также:
|
1.Математическую модель задачи привести к каноническому (стандартному) виду.
2. Построить начальную симплекс-таблицу исходя из стандартного вида.
3. Найти разрешающий столбец. В строке коэффициентов ЦФ найти значение с самим маленьким отрицательным числом. Этот столбец и будет разрешающим.
4. Вычислить разрешающую строку и ведущий элемент (Почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей.Ведущий элемент будет на пересечении разрешающего столбца и разрешающей строки.).
5.Построить новую симплекс-таблицу-второй шаг.
При построении новой таблицы убрать из базиса строку с переменной разрешающей строки в предыдущей таблице. Ввести в базис строку с названием разрешающего столбца предыдущей таблицы.
* Построение ведущей строки в новой таблице. Почленно поделить всю разрешающую строку на разрешающий элемент.
* Построение других строк в новой таблице. Почленно умножить ведущую строку на соответствующие этим строкам элементы разрешающего столбца из предыдущей таблицы и прибавить к соответствующим строкам в старой таблице.
6. Проверяем таблицу второго шага на оптимальность. Если в строке целевой функции нет отрицательных элементов, тогда таблица имеет оптимальный план, записать ответ. Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу, строят новую симплекс-таблицу в соответствии п.5 и затем проверяют ее на оптимальность. Построение таблиц заканчивается с нахождением оптимального плана.
Прямая задача на минимум решается следующим образом:
* Написать математическую модель двойственной задачи в стандартном виде
* Решить двойственную модель симплекс - методом
* Записать ответ.
Связь между задачами двойственной пары в том, что, решая симплексным методом одну из них, автоматически получаем решение другой.
Для этого достаточно воспользоваться соответствием переменных прямой и двойственной задач в последней симплекс-таблице.
| Х1 | x2 | … | xn | S1 | S2 | … | Sm |
| S1 | S2 | … | Sm | y1 | y2 | … | ym |
27. Анализ решения задачи по симплекс – таблице, отвечающей критерию оптимальности.
Схема решения задачи симплексным методом (Это может быть и не то)
1) указывается способ вычисления первоначального допустимого решения задачи.
2) при помощи признака оптимальности проверяется не является ли это решение оптимальным.
3) по выбранному начальному решению строятся другие решения, более близкие к оптимальному.
Алгоритм перехода к симплекс-таблице № 2:
1) Неизвестные x 2 и x 4 меняют местами.
2) Разрешающий элемент a 24 заменяют обратной величиной.
3) Остальные элементы разрешающей строки делим на разрешающий элемент.
4) Элементы разрешающего столбца, кроме разрешающего
элемента, делят на разрешающий элемент и
меняют знаки.
5) Все остальные элементы симплекс–таблицы № 2 получают по правилу прямоугольника: Из произведения элементов диагонали, содержащей искомый элемент, вычитают произведение элементов противоположной диагонали и делят всё на элемент, противоположный искомому.
Дата добавления: 2015-02-16; просмотров: 153 | Поможем написать вашу работу | Нарушение авторских прав |