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




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

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

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

Рис.11

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

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

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

Еще один случай нарушения линейности – требование целочисленности хотя бы части управляемых переменных. Это бывает в том случае, если соответствующий параметр измеряется в штуках. В этом случае при добавлении ограничения мы заполняем поле Ссылка на ячейку, адресом соответствующей ячейки, а в среднем поле из раскрывающегося списка выбираем цел. Поле Ограничение заполнять не нужно. Дальше задача решается обычным образом. Если задача большая по объему, то для ускорения решения можно решить задачу без условия целочисленности, а затем добавить это условие и продолжить решение с теми начальными данные, которые получились при решении первой задачи.

Лабораторная работа

«Распределение удобрений в условиях дефицита»

Хозяйство из-за нехватки денежных средств закупило недостаточное количество комплексных удобрений, всего 200 т. Требуется распределить эти удобрения между зерновыми культурами так, чтобы сделать максимальной прибыль от прибавки урожая. Необходимые данные приведены в таблице.

Культура Озимая пшеница Яровая пшеница Рожь Ячмень Овес
Площадь, га          
Норма удобрений, т/га 0,8 0,9 0,6 0,5 0,7
Урожайность без внесения удобрений, ц/га          
Урожайность с полной нормой удобрений, ц/га          
Закупочная цена, руб/т          

 

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

Потребность (6) находится умножением площади (1) на норму (2). В строке (7) находятся значения управляемых переменных. План на поле (8) получается умножением площади (1) на план на гектар (7). В дополнительной ячейке этой строки суммируются все значения строки. Полученное значение не должно будет превышать имеющееся количество 200, записанное в следующей ячейке.


 

Культура Озимая пшеница Яровая пшеница Рожь Ячмень Овес  
  Площадь, га            
  Норма удобрений, т/га 0,8 0,9 0,6 0,5 0,7  
  Урожайность без внесения удобрений, ц/га            
  Урожайность с полной нормой удобрений, ц/га            
  Закупочная цена, руб/т            
  Потребность, т            
  План внесения удобрений, т/га           План полный,т В наличии, т
  План на поле, т              
  Прибавка урожая, ц             Цена реализации, руб

Прибавка урожая (9) рассчитывается из предположения, что она пропорциональна количеству внесенных удобрений по отношению к норме. Она в этом случае рассчитывается по следующей формуле. Пусть А – норма на гектар, В – урожайность без внесения удобрений, С – урожайность при внесении полной нормы удобрений, Х – количество внесенных удобрений (все в пересчете на гектар). Тогда прибавка урожая на гектар равна (С – В)*Х/А. В строке (9) должна стоять прибавка на все поле, то есть полученное выражение нужно еще умножить на площадь. Все параметры формулы расположены в предыдущих строках.

Наконец, в дополнительной ячейке последней строки вычисляется значение целевой функции. Используется функция СУММПРОИЗВ, прибавка урожая умножается на закупочную цену.

Теперь для получения решения используем Поиск решения. Целевая ячейка – это цена реализации. Управляемые ячейки в строке (7). Ограничения заключаются в том, что план внесения удобрений на гектар не превышают норму, то есть значения ячеек в строке (7) не превышают соответствующие значения в строке (2). Эти ограничения можно ввести не по одному, а списком. Кроме этого, план полный должен быть равен тому, что имеется в наличии.

Далее нажимаем клавишу Параметры и ставим флажки в поля Неотрицательные значения и Линейная модель.

Закончив всю подготовительную работу, нажимаем Выполнить и получаем решение.

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

Скопируем рабочий лист, копию назовем «Нелинейная », а первый лист «Линейная ». Во втором листе изменим формулу для расчета прибавки урожая (9). Вместо (С – В)*Х/А возьмем (С – В)*sin(1,5Х/А), это выражение также умножаем на площадь.

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



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: