Задачи дробно-линейного программирования

Если в задаче нелинейного программирования ограничения линейные, а целевая функция дробно-линейная, то ее называют задачей дробно-линейного программирования. Общий вид задачи дробно-линейного программирования: максимизировать (или минимизировать) функцию

при условиях

Симплексный метод Во многих задачах с экономическим содержанием требуется, чтобы знаменатель целевой функции удовлетворял условию

При этом условии задачу дробно-линейного программирования можно решить симплексным методом. Введем новые переменные. Обозначим

Тогда задача (3.4) — (3.6) примет вид

при ограничениях

В результате получена задача линейного программирования. После ее решения симплексным методом, используя соотношения (3.7), можно найти оптимальное решение исходной задачи (3.4), (3.5). Пример 1. Найти максимальное значение функции

при ограничениях

Решение:

Так как по условию все переменные неотрицательные, то выполнено условие (3.6):

Введем вспомогательную переменную

и, соответственно, дополнительное ограничение

Задача принимает вид:

при условиях:

Умножим второе, третье и четвертое ограничения на , введем новые переменные:

Получена задача линейного программирования: найти максимум функции

при ограничениях

Решив эту задачу симплексным методом, получим

Используя формулу (8.7), возвратимся к исходным переменным:

Итак,

Графический метод Задачи дробно-линейного программирования с двумя переменными можно решать графически. Рассмотрим следующую задачу

Будем считать, что

Для решения этой задачи найдем многоугольник решений, определяемый ограничениями (3.9). Из выражения (3.8) найдем :

где — прямая, проходящая через начало координат.

При фиксированном значении угловой коэффициент прямой тоже фиксирован. При изменении значений прямая будет поворачиваться вокруг начала координат.

Установим, как будет вести себя угловой коэффициент при монотонном возрастании . Найдем производную от по .

Знаменатель производной всегда положителен, а числитель от не зависит. Следовательно, производная имеет постоянный знак и при увеличении угловой коэффициент будет только возрастать или только убывать, при этом прямая будет поворачиваться вокруг точки . Если угловой коэффициент прямой положителен, то прямая вращается против движения часовой стрелки, при отрицательном значении — по часовой стрелке. Установив направление вращения, находим вершину или вершины многогранника, в которых функция принимает экстремальное значение, либо делаем вывод о неограниченности функции. При этом возможны следующие случаи.

1. Многогранник решений ограничен, максимум и минимум достигаются в его угловых точках.

2. Многогранник решений не ограничен, однако существуют угловые точки, в которых целевая функция принимает максимальное и минимальное значения.

3. Многогранник решений не ограничен, один из экстремумов имеется. Например, минимум достигается в одной из вершин многогранника решений, т.е. имеет место так называемый асимптотический максимум.

4. Многогранник решений не ограничен. Максимум и минимум являются асимптотическими.

Алгоритм графического метода

1. Построить многогранник решений.

2. Определить угловой коэффициент и установить направление поворота линий уровня целевой функции.

3. Найти точку экстремума целевой функции или установить неразрешимость задачи.

Пример задачи №23

Предприятие использует три типа оборудования для производства изделий видов и . Время обработки одного изделия на каждом из типов оборудования и затраты на его обработку представлены в таблице.

Первый тип оборудования целесообразно использовать не менее 10 ч, оборудование 2 типа — не более 41 ч, 3 типа — не более 6 ч.

Составить оптимальный план производства изделий при минимальной себестоимости.

Решение:

Составим математическую модель задачи. Пусть и — количество обрабатываемых деталей видов и соответственно. Общие затраты на их обработку составят руб., а себестоимость одного изделия будет равна

Запишем математическую модель задачи:

при ограничениях

Областью допустимых решений является треугольник . Найдем из выражения целевой функции.

Угловой коэффициент . Найдем производную от по .

т.е. при увеличении угловой коэффициент будет только возрастать, а линия уровня поворачиваться против часовой стрелки. Минимум достигается в точке . Найдем ее координаты из системы

при выпуске 6 изделий вида и 4 изделий вида .

Градиентный метод

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

Пусть дана целевая функция

Градиент функции в некоторой точке

есть вектор

Вектор (3.12) направлен по нормали к поверхности уровня и показывает направление максимальной скорости роста функции.

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

Вычислим из уравнения (3.13) , определим точку . Решение заканчивают, если в новой точке , так как дальнейшее перемещение вдоль градиента становится невозможным. Если , то точку принимают за начальную, и процесс решения продолжают до тех пор, пока не будет получен нулевой градиент. Результат решения во многом зависит от выбора начальной точки, с которой начинается приближение к оптимальному решению.

Решение задач математического программирования с ограничениями в форме уравнений и неравенств предполагает дополнительные условия на выбор множителя , при котором новая точка не выйдет за пределы области допустимых решений.

Пусть дана задача выпуклого программирования

при ограничениях

Алгоритм градиентного метода

Найти градиент функции и, решая уравнение , определить стационарные точки, которые удовлетворяют системе (3.15). Вычислить значения целевой функции (3.14) в этих точках.

Найти градиенты функции и определить те стационарные точки, которые принадлежат соответствующей -й границе области. Для этого решить системы уравнений вида

Из всех решений системы (3.16) отобрать те, которые удовлетворяют условиям (3.15) и условию . Вычислить значения целевой функции в этих точках.

Определить пересечения всех граничных гиперповерхностей, решив системы уравнений вида

Отобрать допустимые решения при

и вычислить значения при этих решениях.

В том случае, если ограничения , достаточно найти угловые точки области допустимых решений и вычислить значения целевой функции в этих точках.

Сравнить значения целевой функции во всех точках, определенных в пунктах 1—3 и выбрать и .

Пример задачи №24

Определить градиентным методом максимум функции

начиная итерационный процесс с точки .

Решение:

Определим градиент функции начальной точке .

Выбираем новую точку

Найдем градиент функции в новой точке:

Решаем уравнение

откуда имеем

Получен нулевой градиент, следовательно, точка является стационарной. Так как целевая функция является выпуклой (как сумма выпуклых функций

то в найденной точке достигается

Ответ.

Пример задачи №25

Минимизировать функцию

при ограничениях

Решение:

Систему ограничений запишем в виде

Определим градиент целевой функции

Определим стационарную точку

Данная точка не является допустимой, так как не удовлетьоряет системе ограничений. Следовательно, внутри области допустимых решений экстремума целевой функции нет, глобальный экстремум может достигаться только на границах или в вершинах области решений.

Рассмотрим граничную линию

Составим для нее систему вида (3.16):

Имеем

откуда получаем

Так как точка

удовлетворяет системе ограничений и , то данная точка является стационарной.

Рассматриваем следующую граничную линию:

Для нее и система (3.16) имеет вид

Решение этой системы:

Однако точка

не удовлетворяет первому ограничению, следовательно, не является допустимой. Следующая граничная линия

Имеем систему

откуда

Так как , стационарных точек на грани нет. Аналогично,

Имеем систему

откуда

Так как , стационарных точек на грани нет.

Решая систему уравнений граничных линий, находим угловые точки области допустимых решений: (6; 5), (8; 0), (0; 8). Находим значения в этих точках и ранее найденной точке

Следовательно,