Читайте также: |
|
В примере 1 была составлена задача о диете (1.4)-(1.6) и она приведена к канонической форме (1.7)-(1.9). При этом ни одно из уравнений фазовых ограничений (1.8) не имеет предпочтительной формы, поэтому необходимо составить и решить М -задачу.
М -задача запишется так:
(1.39) | |
(1.40) | |
(1.41) |
Выразим ЦФ через свободные переменные . Для вычисления сложим все уравнения фазовых ограничений: или
.
Откуда следует
,
поэтому ЦФ (1.39) запишется в виде:
(1.42) |
Приведя подобные коэффициенты при свободных переменных , получим ЦФ
(1.43) |
Решим задачу ЛП (1.40), (1.41), (1.43) с помощью симплекс-метода, взяв в качестве базисных переменных искусственные переменные .
Решение, оформленное с помощью MS Excel, приведено ниже на рис.1.10-1.12. Существенным отличием от симплекс-таблиц, приведенных ранее, является выделение двух строк для записи ЦФ. Коэффициенты в ЦФ имеют вид . Первая строка содержит множители, стоящие перед постоянной М, т.е. , вторая строка . Обе строки будем преобразовывать по тем же правилам, что и остальные строки.
Поскольку сколь угодно большое положительное число, очевидно, что знак коэффициента полностью определяется знаком . Это определяет ход решения М -задачи:
1) сначала избавляемся от отрицательных коэффициентов в первой строке ЦФ (в таблицах эта строка помечена буквой «М»);
2) далее избавляемся от отрицательных коэффициентов во второй строке ЦФ (в таблицах эта строка помечена буквой «1»), при условии, что в этом столбце строки «М» содержится ноль.
Результат решения задачи после третьей итерации приведен на рис.1.12 в диапазоне ячеек A33:J39. Целевая функция имеет вид
(1.44) |
Очевидно, что дальнейшее увеличение ЦФ может быть достигнуто за счет ввода в базис, поскольку при достаточно больших М коэффициенты при отрицательны.
Результат решения задачи после четвертой итерации приведен на рис.1.12 в диапазоне ячеек A41:J47. Целевая функция имеет вид
(1.45) |
Очевидно, что все коэффициенты при свободных переменных отрицательны, при достаточно больших М. Оговорка относительно М существенна, поскольку коэффициент при будет отрицательным, когда М, например, больше 1. Таким образом, решение М -задачи получено, а значение ЦФ функции равно -150.
Поскольку в оптимальном плане М -задачи все искусственные переменные , то, в соответствие с теоремой, план
является оптимальным планом исходной задачи (1.4)-(1.6).
Таким образом, оптимальным решением задачи о диете является план, который предусматривает покупку кормов только второго вида в количестве 75 единиц, стоимость диеты равна 150 у.е. При этом перекорм по питательному веществу B равен 75 единиц, а по питательному веществу C равен 17.5 единиц, по питательному веществу A перекорма нет.
Рис.1.10. Решение М -задачи (начало)
Рис.1.11. Решение М -задачи (продолжение).
Рис.1.12. Решение М -задачи (окончание).
Задание
Каждый вариант содержит одну задачу.
Дата добавления: 2015-09-03; просмотров: 96 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Решение | | | Задача о диете. |