Дробно-линейное программирование
Если в задаче с линейными ограничениями задана дробно-линейная целевая функция, то такая задача может быть преобразована к традиционному виду путем несложных преобразований. Преобразованная модель может быть разрешена симплексным методом, а найденное решение трансформировано в решение исходной задачи дробно-линейного программирования. Все этапы алгоритма проиллюстрируем на конкретном примере. 1. Систему ограничений приводят к каноническому виду:
2. Знаменатель целевой функции обозначают через § появится дополнительное ограничение § функция цели приобретет вид 3. Все ограничения умножают на
4. Вводят обозначения:
Упорядочивают систему относительно новых переменных, перенося из правой части элементы, связанные с
5. Задача приобрела каноническую форму, ее решение может быть выполнено симплексным методом. Учитывая, что индексы векторов должны соответствовать индексам переменных (
Таблица 1 Начальное симплекс-решение
Данной таблице соответствуют такие значения переменных:
Это решение не оптимально. В таблице 1 получено три одинаковых симплексных отношения, - все они равны нулю. При выборе ключевой строки руководствуются правилом: берут ту, которая соответствует большему элементу ключевого столбца. В данном случае выбирают первую строку, и генеральный элемент равен 6. Таблица 2 Вторая симплексная таблица
Второе решение выглядит так:
Оно не оптимально. Переход к третьей таблице выполняется по обычным правилам с учетом комментария к выбору ключевой строки, сделанного после таблицы 1. Таблица 3 Третье симплексное решение
Третье решение:
Условие оптимальности все еще не выполняется, переходят к следующей таблице. Анализ показывает, что значения большинства переменных будут равны нулю до тех пор, пока ключевой строкой будет оставаться строка с нулевым элементом в Таблица 4 Четвертое симплексное решение
Решение, соответствующее таблице 4, имеет вид:
Оно не является оптимальным, строят следующее симплекс-преобразование.
Таблица 5 Пятое симплексное решение
В таблице 5 получено решение, удовлетворяющее условию оптимальности:
6. Определяют значения исходных переменных: Таким образом, решение задачи дробно-линейного программирования будет следующим:
7. Дают, если возможно, геометрическую интерпретацию задачи:
§ находят область допустимых значений; § отмечают точки, соответствующие симплекс-таблицам.
Областью решений является треугольник
Замечание. Дробно-линейную задачу с двумя переменными можно решать графическим методом, основываясь на таких правилах:
1. По системе заданных ограничений строят область допустимых решений. 2. Выбирают произвольное значение 3. Обозначим § если § если 4. Определив оптимальные точки, находят их координаты – это и будут оптимальные значения переменных, после чего вычисляют величину функции цели.
Пример. Найти решение дробно-линейной задачи.
1. Строим область допустимых решений – она определяется тремя неравенствами и представляем собой треугольник
2. Строим прямую а) б)
а) б)
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|