|
|
Методы отсекающих плоскостейМетоды отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП).
обладающее двумя свойствами:
Такое ограничение называется правильным отсечением. Затем решается расширенная непрерывная задача ЛП, т.е. непрерывная задача с добавленным ограничением. Если полученное решение не является целочисленным, добавляется новое правильное отсечение и т.д. Процесс повторяется до тех пор, пока решение очередной расширенной непрерывной задачи ЛП не окажется целочисленным. Таким образом, решение целочисленной задачи ЛП сводится к решению некоторой последовательности обычных задач ЛП. Геометрически добавление каждого такого линейного ограничения означает проведение гиперплоскости, отсекающей от многогранника допустимых решений очередной непрерывной задачи ЛП оптимальную точку с нецелочисленными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому методы, опирающиеся на эту идею, получили название методов отсечений. Решение: За основу берем уже решенный прямой симплекс-метод.
Таблица 2.9.1
Так как решение не является целочисленным, вводим дополнительное ограничение по формуле: - - Решаем задачу ЛП с дополнительным условием. Составляем симплекс-таблицу.
Таблица 2.9.2
Так как решение не является целочисленным, вводим дополнительное ограничение по формуле:
Таблица 2.9.4
Полученное решение является целочисленным. Расчет закончен.
Метод ветвей и границ Суть метода ветвей и границ состоит в последовательном переборе вариантов, рассмотрении лишь тех из них, которые по определенным признакам оказываются перспективными, и отбрасывании бесперспективных вариантов. При использовании метода ветвей и границ область допустимых решений (ОДР) исходной задачи определенным способом разбивается на непересекающиеся подмножества, и решаются подзадачи, т.е. задачи на этих подмножествах с той же ЦФ и без учета условия целочисленности (как задачи ЛП). Если в результате получено оптимальное нецелочисленное решение, ОДР подзадачи снова разбивается на части и этот процесс продолжается до тех пор, пока не будет найдено оптимальное целочисленное решение исходной задачи. Если в задаче на максимум при решении подзадач получаются оптимальные целочисленные решения, то запоминаются те из них, которым соответствуют возрастающие значения ЦФ. Если полученное «непрерывное» решение подзадачи оказывается не лучше сохраненного целочисленного решения, то такая подзадача исключается из списка задач. Название этого метода объясняется тем, что в процессе решения задача последовательно «ветвится», разбиваясь на более простые подзадачи.
L = 11x1 + 12x2 →max 12x1 + 11x2 ≤ 132; 10x1 + 15x2 ≤ 150; x1 ≥ 0, x2 ≥ 0, x1, x2
L = 134
Начинаем вводить ограничения:
Итак, оптимальное целочисленное решение равно 129 при x1 = 3; x2 = 8.
  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...  Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
.
- 
+ 
- 
+ 
= 
= 
- 
+ 
- 
= 
= 
- 
- 
Z
; x1 = 4 
; x2 = 6 
.
12 x1 + 11*6 = 132;
x1 = 5 
; x2 = 6;
L = 132 
10 x1 +15*7 = 150
x1=4 
10*4 +15x2 = 150;
x1 = 4; x2 = 7 
15х2=100
х1=5; х2=6 
Решений нет.
10х1 + 15*8 = 150
х1 = 3; х2 = 8;
L=129 Получено целочисленное решение, прекращаем ветвление..