Презентация - Решение с использованием усеченной таблицы RUSMMF

Решение задач симплекс-методом Решение с использованием усеченной таблицы RUSMMF

Основные понятия Целевая функция Система ограничений - матрица системы ограничений, - столбец свободных членов Каноническая запись задачи - от ограничений типа неравенства переходим к ограничениям типа равенства, вводя балансовые переменные.

Симплексная таблица БП 1 СП БП 1 СП

Заполнение таблицы Заполнение столбца 1 БП 1 СП 0 БП 1 СП 0 Вносим в столбец 1 значения из столбца свободных членов, в f вносим 0

Заполнение f-строки Вносим значения коэффициентов функции f с противоположными знаками БП 1 СП 0 БП 1 СП 0

Заполнение матрицы коэффициентов Вносим значения коэффициентов системы ограничений БП 1 СП 0 БП 1 СП 0

Пересчет таблицы Разрешающий столбец . Выбираем минимальный отрицательный элемент если задача на максимум, и максимальный положительный элемент если задача на минимум БП 1 СП 0 БП 1 СП 0

Пересчет таблицы Симплексные отношения - отношение элемента столбца свободных членов к элементу разрешающего столбца БП 1 СП 0 -- БП 1 СП 0 --

Пересчет таблицы Разрешающая строка . Из симплексных отношений выбираем минимальное значение (положительное) БП 1 СП 0 -- БП 1 СП 0 --

Пересчет таблицы Разрешающий элемент - элемент на пересечении разрешающего столбца и разрешающей строки БП 1 СП 0 -- БП 1 СП 0 --

Правило прямоугольника (расчеты нового элемента, не в столбце и не в строке) В строке (которая ранее была разрешающей) новой таблицы элементы получаются путем деления на разрешающий элемент, кроме самого разрешающего элемента. Он заменяется на обратное число (1/разрешающий элемент). В столбце (который ранее был разрешающим) новой таблицы элементы получаются путем деления на элемент противоположный разрешающему, кроме самого разрешающего элемента.

Перейдем к решению примера Тип сырья Нормы расходов сырья на одно изделие Запасы сырья А Б В 1 4 2 1 180 2 3 1 3 210 3 1 2 5 244 Цена изделия 10 14 12 Задача 2. Построить модель ЗЛП. Решить задачу симплекс–методом.

Решение: Запишем математическую модель данной задачи: Сведем данную задачу к закрытому типу задач, введя дополнительные переменные

Запишем первую симплексную таблицу: БП 1 СП 180 4 2 1 90 210 3 1 3 210 244 1 2 5 122 0 -10 -14 -12 БП 1 СП 180 4 2 1 90 210 3 1 3 210 244 1 2 5 122 0 -10 -14 -12

Так как не все значения в f-строке положительные, то план не оптимальный. Выбираем наименьшее отрицательное значение в f-строке БП 1 СП 90 2 1/2 1/2 180 120 1 -1/2 5/2 48 64 -3 -1 4 16 1260 18 7 -5 БП 1 СП 90 2 1/2 1/2 180 120 1 -1/2 5/2 48 64 -3 -1 4 16 1260 18 7 -5

БП 1 СП 82 -1/8 80 -5/8 16 -3/4 -1/4 1/4 1340 57/4 23/4 5/4 БП 1 СП 82 -1/8 80 -5/8 16 -3/4 -1/4 1/4 1340 57/4 23/4 5/4 Так как все значения в f-строке положительные, то план оптимальный Пересчитываем таблицу

Спасибо за внимание!