Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Тема 2. 1 нелинейное программирование

Пример.

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

Пункты отправления Пункты назначения Запасы
В1 В2 В3 В4
А1          
А2          
А3          
Потребности          

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

Метод северо-западного угла.

Пункты отправления Пункты назначения Запасы
В1 В2 В3 В4
А1          
А2          
А3          
Потребности          

S=1*30+2*20+3*10+1*10+5*10+4*10=200

Метод минимальной стоимости.

Пункты отправления Пункты назначения Запасы
В1 В2 В3 В4
А1          
А2          
А3          
Потребности          

S=1*30+2*10+1*10+3*20+5*10+4*10=210

Метод аппроксимации Фогеля

 

Пункты отправления Пункты назначения Запасы        
В1 В2 В3 В4        
А1                 -
А2                  
А3                  
Потребности                  
                   
      -            
      - -          
  -   - -          

S=1*30+4*10+1*10+3*20+5*10+2*10=210

 

Основываясь на опорном плане, найденного методом северо-западного угла, проверим его на оптимальность.

Составим систему уравнений

 

Полагая α1=0, получим β1= 1, β2=2, β3=0, β4=4, α3=0, α2=-1. Для каждой свободной клетки вычисляем. Имеем. План не явлется оптимальным.

Пункты отправления Пункты назначения Запасы
В1 В2 В3 В4
А1   2 - -4 1 + 3  
А2 0 3 +   5 -  
А3 -2 0 -4    
Потребности          

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

Следующие этапы проводим аналогично.

РАЗДЕЛ 2. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.

В общем виде задача нелинейного программирования состоит в определении максимального (минимального) значения функции

(1)

при условии, что её переменные удовлетворяют соотношениям

(2)

где f и gi – некоторые известные функции n переменных, а bi – заданные числа.

Здесь имеется в виду, что в результате решения задачи будет определена точка координаты которой удовлетворяют соотношениям (2) и такая, что для всякой другой точки удовлетворяющей условиям (2), выполняется неравенство.

Если f и gi линейные функции, то задача (1), (2) является задачей линейного программирования.

Соотношения (2) образуют систему ограничений и включают в себя условия неотрицательности переменных, если такие условия имеются. Условия неотрицательности переменных могут быть заданы и непосредственно.

В евклидовом пространстве En система ограничений (2) определяет область допустимых решений задачи. В отличие от задачи линейного программирования она не всегда является выпуклой.

Если определена область допустимых решений, то нахождение решения задачи (1) – (2) сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня:. Указанная точка может находится как на границе области допустимых решений, так и внутри нее.

Процесс нахождения решения задачи нелинейного программирования (1) – (2) с использованием её геометрической интерпретации включает следующие этапы:

10. Находят область допустимых решений задачи, определяемую соотношениями (2) (если она пуста, то задача не имеет решения).

20. Строят гиперповерхность.

30. Определяют гиперповерхность наивысшего (наинизшего) уровня или устанавливают неразрешимость задачи из-за неограниченности функции (1) сверху (снизу) на множестве допустимых решений.

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

3.1. Найти максимальное значение функции

(3)

при условиях

(4)

(5)

Р е ш е н и е. Так как целевая функция (3) нелинейная, то задача (3) – (5) является задачей нелинейного программирования. Областью допустимых решений данной задачи является многоугольник ОАВС (рис. 3.1). Следовательно для нахождения её решения нужно определить такую точку многоугольника ОАВС, в которой функция (3) принимает максимальное значение. Построим линию уровня, где h – некоторая постоянная, и исследуем её поведение при различных значениях h. При каждом значении h получаем параболу, которая тем выше отдалена от оси Оx1, чем больше значение h (рис. 3.1). Значит, функция F принимает максимальное значение в точке касания одной из парабол с границей многоугольника ОАВС. В данном случае это точка D (рис. 3.1), в которой линия уровня касается стороны АВ многоугольника ОАВС.

Координаты точки D можно найти из системы уравнений

(6)

Решая эту систему, получим. Итак, при

Как видим, в задаче (3) – (5) точка максимального значения целевой функции не является вершиной многоугольника решений. Поэтому процедура перебора вершин, которая использовалась при решении задач линейного программирования, неприменима для решения данной задачи.

 

<== предыдущая лекция | следующая лекция ==>
Определение опорного плана транспортной задачи | Метод множителей Лагранжа
Поделиться с друзьями:


Дата добавления: 2014-01-15; Просмотров: 423; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.