- •Технологическая карта (план) занятия № 10
- •Содержание урока:
- •1. Организационный момент проверка посещаемости
- •Методы решения злп
- •1.2 Табличный симплекс - метод
- •1.3 Метод искусственного базиса
- •1.4 Модифицированный симплекс - метод
- •Описание Симплекс-метода
- •Порядок работы с симплекс таблицей
- •Пример 1 Задача об использовании сырья
- •Пример 2.
- •Пример 3
- •Пример 4 Задача об использовании ресурсов
- •Пример 5
- •Задачи на закрепление:
Пример 4 Задача об использовании ресурсов
Разберем процесс нахождения оптимального плана:
Для решения задачу необходимо привести к канонической форме:
(1)
Среди переменных задачи можно выделить базисные x3, x4 и x5, и небазисные x1, x2. Приравняв небазисные переменные x1, x2 к нулю, т. е. x1 = 0, x2 = 0, получим исходный базисный план (невырожденный): x3=36, x4 = 20, x5 = 40. Для этого плана значение целевой функции f = 0.
Исходя из смысла задачи об использовании ресурсов, ситуация, отвечающая исходному плану, означает бездеятельность предприятия. Предприятие ни один из двух видов продукции Р1 и Р2 не выпускает, так как их количество в исходном плане, обозначенное соответственно через x1 и х2, равно нулю. Доход от реализации продукции, отраженный в целевой функции f, также равен нулю. Данная ситуация не может устраивать предприятие и тем более не является оптимальной.
Приведем задачу (1) к виду:
(2)
Анализируя функцию f в (2), приходим к выводу, что увеличение значения f, означающее увеличение дохода, может произойти только в том случае, если значения х1 или х2 будут возрастать.
Увеличение значений х1 или х2 равносильно переводу их в число базисных.
В первую очередь увеличим значение х2, так как единица продукции Р2 приносит больший доход (значение х1 пока остается равным нулю). Значение х2 нельзя увеличивать бесконечно, а только до такой величины, которая будет удовлетворять условиям:
(3)
Определим значение x2(X1 = 0) из следующих соотношений, полученных на основе ограничений задачи (3.22):
Для выполнения условий (3) необходимо, чтобы . Поскольку данное значение х2 получилось из третьего ограничения, то выразив х2 из этого ограничения через переменные х1 и Х5, получим (переменная х2 переводится в число базисных вместо х5, которая становится небазисной):
(4)
Подставив выражение (4) в два оставшихся ограничения и целевую функцию, получим после первой итерации такой вид задачи:
(5)
Определим новый базисный план, полученный после первой итерации: х1=0, х5 = 0 (небазисные переменные); x3 = 6, x4=Ю, x2 = 5 (базисные переменные). Значение целевой функции f = 75.
На основании анализа f в (5) можно сделать вывод, что полученный план не является оптимальным, так как значение целевой функции может быть увеличено за счет увеличения значения x1 (увеличение значения х5 приведет к уменьшению значения f). Значение х1 также нельзя увеличивать бесконечно, а только до такой величины, которая будет удовлетворять условиям:
(6)
Определим значение x1(x5 = 0) из следующих соотношений, полученных на основе ограничений задачи (5):
Для выполнения условий (6) необходимо, чтобы . Поскольку данное значение х1 получилось из первого ограничения, то, выразив х1 из этого ограничения через переменные x3 и x5, получим (переменная x1 переводится в число базисных вместо х3, которая становится небазисной):
(7)
Подставив выражение (7) в два оставшихся ограничения и целевую функцию, получим после второй итерации следующий вид задачи:
(8)
Определим базисный план, полученный в результате, второй итерации: . x3=0 и x5=0(небазисные переменные), х1=2, x2=4, x4=4 (базисные переменные). Значение целевой функции f = 84.
Анализ f в (8) показывает, что полученный в результате второй итерации план является оптимальным, так как значение целевой функции не может быть увеличено за счёт увеличения значений x3 и x5.
На основании оптимального плана (х1=2, x2=4, x4=4) делаем вывод, что предприятие для получения максимального дохода в размере 84 руб. должно выпускать из имеющегося количества сырья 2 ед. продукции Р1 и 4 ед. продукции Р2.
Коэффициенты, стоящие в скобках при небазисных переменных в целевой функции, называются относительными оценками и обозначаются , где Ib — множество индексов базисных переменных. Относительными эти оценки называются потому, что их значение зависит от выбора базисного плана. Например, в
Условие оптимальности плана задачи линейного программирования (для задачи на max). Если для некоторого базисного плана оценки , то этот план является оптимальным.
Рассмотренное условие является достаточным условием оптимальности базисного плана задачи. Необходимость этого условия в общем случае не имеет места и может нарушаться только для вырожденного базисного плана. Оптимальному вырожденному базисному плану могут соответствовать отрицательные оценки .