Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





 

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

Шаг 1. Решаем сформулированную задачу как задачу ЛП (обозначим ЛП-1), рассматривая все ее переменные как непрерывные. Пусть W1 - оптимальное значение ее целевой функции. Допустим, в оптимальном решении ЛП-1 некоторые целочисленные переменные принимают дробные значения. Тогда оптимальное решение исходной задачи не совпадает с оптимальным решением ЛП-1. В этом случае W1 - верхняя граница оптимального значения W исходной задачи.

В решенном нами примере 9.1 линейного программирования “Оптимизация размещения побочного производства лесничества” верхняя граница соответствует 34 тыс. руб. при x1=3.6 и x2=6.4. Очевидно, что переменные x1 (число откармливаемых бычков) и x2 (количество выращиваемых партий продукта растениеводства) должны быть целочисленны.

Шаг 2. Производим ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении ЛП-1. Выбор переменной, по которой производим ветвление, осуществляется по ряду правил:

· выбор целочисленной переменной, значение которой в оптимальном решении ЛП-1 имеет наибольшее дробное значение;

· расстановка приоритетов и ветвление по переменным с наибольшим приоритетом (данная переменная представляет важное решение, ее коэффициент стоимости или прибыли в целевой функции существенно превосходит остальные и т.д.);

· Произвольные правила выбора (например, переменную с наименьшим порядковым номером).

В рассматриваемой целочисленной версии примера 9.1 в качестве переменной, по которой будет вестись ветвление, следует рассматривать x1, т.к. коэффициент стоимости при этой переменной максимален.

Шаг 3. Пусть ветвление происходит по xi, дробное значение которой в ЛП-1 равно bi. Далее рассматриваются уже две новые задачи ЛП-2 и ЛП-3, которые образуются путем введения двух дополнительных ограничений xi£ai , xi ³gi, где ai - наибольшее целое, не превосходящее bi, gi - наименьшее целое, большее bi. Допустим, оптимальные значения ЛП-2 и ЛП-3 содержат дробные значения целочисленных переменных и поэтому не являются допустимыми.

Для рассматриваемого примера b1=3,6, a1=3, g1=4.

Шаг 4. Производим ветвление в вершине 2 или 3, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления осуществляется с помощью специальных правил:

· использование наибольшего оптимального значения целевой функции;

· “последним пришел - первым вышел”.

Шаг 5. Процесс ветвления и решения задач ЛП продолжаем до получения целочисленного решения одной из задач ЛП. Значение W в полученной точке представляет собой нижнюю границу оптимального значения ЦФ исходной задачи ЦП. На этом этапе все вершины (задачи ЛП), для которых оптимальное значение W не превосходит полученной нижней границы (“прозондированные” вершины). Вершина является прозондированной в следующих случаях:

· оптимальное решение, соответствующее данной вершине, целочисленно;

· задача ЛП не имеет допускаемого решения;

· оптимальное значение W не превосходит текущей нижней границе.

Ветвление происходит до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наилучшим W дает оптимальное решение исходной задачи ЦП.

Процесс ветвления и решения рассматриваемой задачи представлен на рис. 10.1. Оптимальное решение - W=32,5 млн. руб.; x1=4; x2=5.

 

  ЛП-1 W1=34 тыс.руб. x1=3,6, x2=6,4, b1=3,6, a1=3, g1=4.    
  x1£a1 x1³g1  
   
ЛП-2 W1=32,5 тыс.руб. x1=3, x2=7. Оптимальное решение   ЛП-3 W1=33.3 тыс.руб. x1=4, x2=5,33, b3=5,33, a3=5, g3=6.
      x2£a3   x2³g3
 
    ЛП-4 W1=33,13 тыс.руб. x1=4,125, x2=5, b1=4,125, a1=4, g1=5.   ЛП-5 Допустимое решение отсутствует
  x1£a4 x1³g4  
       
ЛП-6 W1=32,5 тыс.руб. x1=4, x2=5. Оптимальное решение   ЛП-7 W1=25 тыс.руб. x1=5, x2=0.  
                 

Рис. 10.1. Процесс ветвления для примера 9.1 в целочисленной постановке методом ветвей и границ

Date: 2016-07-25; view: 445; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию