Реферат: Исследование операций

 Правила ветвления:

1)    Выбирается переменная, у которой дробная часть наиболее близка к 0,5.

2)    Выбирается переменная с наибольшим приоритетом по какому — либо  качественному или количественному значению.

3)    Переменная выбирается произвольно.

Ограничения введенные при ветвлении добавляются к ограничениям задачи ЛП.

В каждой из вершин находим оптимальные решения полученных путем добавления новых ограничений задач ЛП – 2 и ЛП – 3. Если не у одной из них мы не получили целочисленных оптимальных решений, то мы выбираем ту вершину, в которой получено наибольшее значение целевой функции и производим дальнейшее ветвление. Так продолжается до получения целочисленного оптимального решения одной из задач ЛП.

Вершина называется прозондированной, если:

1)    Мы нашли в ней оптимальное целочисленное решение – решение задачи ЦЛП.

2)    В данной вершине нет оптимальных решений задачи ЛП.

3)    Значение Z в оптимальном решении задачи ЛП не больше текущей нижней границы.

Прочие вершины называются висящими.

   Решение задачи методом целочисленного линейного программирования.

                                      Метод ветвей и границ. 

Начальные условия берутся из решения задачи ЛП (решение см. выше).

  

1.    Вершина 1  x1 = 6,17       x2 = 0,9        x3 = 4,9       Z1 = 6048,24

Начнем ветвление по x1 = 6,17, тогда получаем дополнительные ограничения а) x1  6 (1 ветвь) б) x2  7 (2 ветвь).

Решаем сначала ветвь 1. К ограничениям задачи ЛП добавляем ограничение а.

Получаем седьмым ограничением ограничение x1  6;

Решение:

2.    Вершина 2  x1 = 6    x2 = 1,2       x3 = 4,8      Z2 = 6033,7212

Мы получили одно целочисленное решение x1 = 6, следовательно дальнейшее ветвление мы будем проводить по x2 или x3.

Решаем ветвь 2. К ограничениям задачи ЛП добавляем ограничение б.

Седьмым ограничением становится ограничение x1  7.

Решение:

 
                              

Второй строкой является ограничение задачи ЛП по максимально возможному объему руды с 2 предприятия:

120x1  740 или  x16,16666, что противоречит введенному нами условию 6 (б)  x1  7. Дальнейшее ветвление из вершины 3 невозможно.

Продолжим ветвление из вершины 2. Как было уже сказано выше, мы можем продолжить ветвление по x2 или x3. Продолжим ветвление по x2. x2 = 1,2, следовательно восьмое ограничение для 1 ветви будет x2  1, а для другой x2. Движемся сначала по ветви 1 в вершину 4.

Решение:

X1 = 6         x2 = 1       x3  = 5       Z4 = 5993,3501

Мы получили, что все три переменных имеют целочисленное значение,

но, чтобы данное решение являлось решением задачи ЦЛП необходимо и достаточно показать, что при ветвлении по ветви 2 в вершине 5 мы получим значение целевой функции Z5 < Z4. Найдем решение в вершине 5.

Решение:

Z5 = 5991,0396, следовательно Z5 < Z4, значит в вершине 4 мы получили решение задачи ЦЛП.

         

                Интерпретация решения с помощью блок – схемы:

                                     

                                                                           x1=6,1

                                      Z1=6048                       x2=0,9

                                                                           x3=4,9   

                                                                 

                                      x16                                   x17         

            x1=6

            x2=1,2                                                                                   Система      

            x3=4,8                                                                                   несовместна

         x21                               x22

           

                 x1=6                                               x1=5,6

                 x2=1                                               x2=2

                 x3=5                                               x3=4  

Z=5993                                           Z=5991      

Вершина	Ограничение	№ ограничения
2	x16	7
3	x17	7
4	x1 6               x21	7                 8
5	x16           x22	7                 8

Вывод:

В результате решения я получил, что целочисленное оптимальное решение получается в вершине 4, так как все значения x1=6, x2=1,x3=5 в этой вершине целочисленные и Z5(5991)<Z4(5993), следовательно получено оптимальное решение. Висящая вершина 5  и прозондированные 1,2,3,4.

Плановые задания:

, где P – плановое задание тыс. тонн, q – производительность состава, x – количество составов, i – номер предприятия.

Для предприятия 1:

тыс. тонн;

Для предприятия 2:

тыс. тонн;

Для предприятия 3:

тыс. тонн.

                                  Нелинейное программирование.

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

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

Разделяют задачи безусловной и условной оптимизации. Задачами безусловной оптимизации называются задачи оптимизации функции многих переменных без дополнительных ограничений. Существуют следующие методы безусловной оптимизации: покоординатного спуска, градиентные, сопряженных направлений, метод Ньютона.  Задачами условной оптимизации называются задачи о оптимизации целевой функции многих переменных f(x1, …, xn) при условии, что эти переменные  удовлетворяют следующим ограничениям:

               qi(x1, …, xn) = 0,  

Страницы: 1, 2, 3, 4, 5, 6