Главная База знаний "Allbest" Программирование, компьютеры и кибернетика Метод ветвей и границ

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

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

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 05.03.2012
Размер файла 4,0 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Содержание

  • Введение
  • 1. Метод ветвей и границ
  • 2. Выполнение расчета №1 по теме "Графический метод решения задач линейного программирования"
  • 3. Выполнение расчета №2 по теме "Решение задач линейного программирования симплекс-методом"
  • 4. Выполнение расчета №3 по теме "Решение транспортной задачи"
  • 5. Слайды презентации
  • Заключение
  • Список использованных источников

Введение

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

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

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

ветвь граница линейное программирование

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

Алгоритм метода ветвей и границ предусматривает декомпозицию исходной задачи линейного программирования (ЗЛП) на последовательность задач, содержащих дополнительные ограничения на переменные, которые затем оптимизируются.

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

2. Если некоторая переменная, не получила целочисленного значения, то производится ветвление на две новые задачи ЗЛП-1, ЗЛП-2. Одна из задач ЗЛП-1 представляет собой задачу ЗЛП-0, дополненную ограничением где - целая часть числа . Вторая образуется путем добавления к задаче ЗЛП-0 ограничения . Следует отметить, что выбор целочисленной переменной может быть произвольным определяться следующим образом:

по возрастанию или убыванию индексов;

переменная представляет важное решение принимаемое в рамках данной задачи;

коэффициент в целевой функции при этой переменной существенно превосходит все остальные.

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

Процесс решения можно представить в виде дерева, в котором вершина ЗЛП-0 отвечает начальному плану решения задачи, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану следующей задачи.

Рассмотрим следующий пример. Максимизировать целевую функцию

при ограничениях

Воспользуемся графическим методом решения задачи линейного программирования.

1. Решим исходную задачу без учета требования целочисленности переменных.

Обозначим эту задачу линейного программирования ЗЛП-0.

На рисунке 1.1 штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным.

Следующий шаг метода ветвей и границ состоит в ветвлении по одной из целочисленных переменных, имеющих дробное значение, например . Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений . Таким образом, в процессе ветвления создаются две новые задачи ЗЛП-1 и ЗЛП-2.

Рисунок 1.1 Решение задачи ЗЛП-0

ЗЛП-1

ЗЛП-2

2. Решим задачу ЗЛП-1 графически.

На рисунке 1.2 изображена допустимая область задачи ЗЛП-1. Максимальное значение достигается в точке . Решение задачи нецелочисленное.

Рисунок 1.2 Решение задачи ЗЛП-1

3. Решим задачу ЗЛП-2 графически.

В данном случае множество допустимых решений пусто (рисунок 1.2). Система ограничений несовместна, и задачу ЗЛП-2 можно исключить из дальнейшего рассмотрения.

Рисунок 1.3 Решение задачи ЗЛП-2

Теперь продолжим исследование задачи ЗЛП-1, поскольку значение нецелое. Произведем еще одно ветвление, путем введения ограничений и . В результате получаем две новые задачи ЗЛП-3 и ЗЛП-4.

ЗЛП-3

ЗЛП-4

4. Решим задачу ЗЛП-3 графически.

На рисунке 1.3 изображена допустимая область задачи ЗЛП-3. Максимальное значение достигается в точке . Решение задачи целочисленное.

Рисунок 1.4 Решение задачи ЗЛП-3

5. Решим задачу ЗЛП-4 графически.

На рисунке 1.5 изображена допустимая область задачи ЗЛП-4. Максимальное значение достигается в точке . Решение задачи целочисленное.

Таким образом, ветвление всех задач закончено. Получено 2 целочисленных решения:

· в задаче ЗЛП-3 - точка ;

· в задаче ЗЛП-4 - точка .

Рисунок 1.5 Решение задачи ЗЛП-4

Оптимальному решению соответствует точка с наибольшим значением целевой функции. В данном случае .

Информацию, полученную из задач ЗЛП-0 - ЗЛП-4, можно отметить на дереве решений рисунок (1.6)

Рисунок 1.6. Дерево решений задачи

2. Выполнение расчета №1 по теме "Графический метод решения задач линейного программирования"

Задание 2.1

Решить графически задачу линейного программирования:

при ограничениях:

Решение

Построим многоугольник решений (рисунок 2.1). Для этого изобразим граничные прямые:

(1);

(2);

(3);

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

Рисунок 2.1 - Решение задачи 2.1

Находим вектор-градиент целевой функции = (1; - 1). Перпендикулярно градиенту проводим прямую и перемещаем её параллельно самой себе в направлении градиента.

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

Найдем координаты точки С (точка пересечения прямых (2) и (3)), решая систему уравнений:

С (2;

3). Подставляя значения и в целевую функцию, получим:

.

Найдем координаты точки D (точка пересечения прямых (1) и (3)), решая систему уравнений:

D (; ).

Ответ: Оптимальное решение данной задачи - и .

3. Выполнение расчета №2 по теме "Решение задач линейного программирования симплекс-методом"

Задание 3.1

Решить симплекс - методом задачу линейного программирования:

при ограничениях:

Решение

Приведем задачу линейного программирования к предпочтительному виду:

Базисные переменные: , , . Свободные переменные: , . Строим начальную симплекс таблицу 3.1.

Таблица 3.1 - Начальный опорный план

План

Базисные переменные

Ресурсы

Значение коэффициентов

переменных

Q

6

1

3

1

0

0

-

7

2

1

0

1

0

-

1

-1

1

0

0

1

1/1

Индексная строка

0

1

-1

0

0

0

-

Начальный опорный план имеет вид: = (0; 0; 6; 7;

1). Значение целевой функции начального опорного плана: =-1*0+1*0=0.

Данный опорный план не является оптимальным, так как в индексной строке таблицы 3.1 есть отрицательная оценка. Составим новую симплекс таблицу (таблица 3.2) по следующему плану:

1. Выбираем ведущий столбец. Ведущим столбцом будет столбец №2, так как только данный столбец имеет отрицательное значение в индексной строке.

2. Выбираем ведущую строку. Ведущей строкой будет строка №3, так как только в данной строке элемент, находящийся в выбранном столбце, больше 0.

3. Выбираем ведущий элемент. Ведущим элементом будет элемент, находящийся на пересечении ведущего столбца и ведущей строки, то есть 1.

4. Переходим к новой симплекс таблице 3.2.

Таблица 3.2 - Опорный план №1

План

Базисные переменные

Ресурсы

Значение коэффициентов переменных

Q

3

4

0

1

0

-3

-

6

3

0

0

1

-1

-

1

-1

1

0

0

1

-

Индексная строка

1

0

0

0

0

1

-

Опорный план №1 имеет вид: = (0; 1; 3; 6; 0) является оптимальным и единственным. Подставляя значения и в целевую функцию, получим:

=1*0+1*1=1

Замечание: Решение не совпадает с графическим решением, так как область допустимых решений лежит в треугольнике EBK (рисунок 2.1), поэтому симплекс метод находит оптимальное решение в точке (0;

1). Задание 3.2

Для задачи из задания 2.1 расчета №1 составить математическую модель двойственной задачи и выписать её решение из симплексной таблицы.

Решение

Составим двойственную задачу к прямой задаче, которая решена симплексным методом в задании 3.1

Прямая задача

Двойственная задача

Задачи образуют симметрическую пару двойственных задач. Решение прямой задачи найдено симплекс - методом и оптимальный план имеет вид

= (0; 1; 3; 6; 0), а значение целевой функции равняется =1*0+1*1=1.

Используя последнюю итерацию прямой задачи (таблица 3.3), находим оптимальный план двойственной задачи.

Таблица 3.3 - Оптимальный план прямой задачи

План

Базисные переменные

Ресурсы

Значение коэффициентов переменных

Q

3

4

0

1

0

-3

-

6

3

0

0

1

-1

-

1

-1

1

0

0

1

-

Индексная строка

1

0

0

0

0

1

-

Согласно соответствиям между переменными прямой и двойственной задач имеем: значения переменных , , по индексной строке соответствуют значениям переменных , , , то есть =0, =0, =1, а значения переменных и по индексной строке соответствуют значениям переменных и , то есть =0, =0.

Оптимальный план двойственной задачи = (0, 0, 1, 0, 0) и значение целевой функции равняется =1*0+1*1=1.

4. Выполнение расчета №3 по теме "Решение транспортной задачи"

Задание 3.1

В производится однородная продукция в количествах ед. Себестоимость единицы продукции в пункте равна . Готовая продукция поставляется в пункты потребности которых составляют ед. Стоимости перевозки единицы продукции из пункта в заданы матрицей размера 3*4. Требуется:

ТЗ является открытой, так как , поэтому вводим фиктивного поставщика (m+1), при этом . Сведем исходные данные в таблицу 4.1:

Таблица 4.1 - Исходные данные

Определяем начальное допустимое базисное решение (опорный план). Находим опорный план (ОП) по методу минимальной стоимости (таблица 4.2)

Таблица 4.2 - Начальный опорный план

Построим начальный опорный план:

Определяем суммарные затраты на продукцию:

Решаем ТЗ методом потенциалов для нахождения оптимального плана.

Находим число занятых клеток в начальном ОП:

m+n-1=3+5-1=7 ОП

является невырожденным (то есть число занятых клеток равно числу свободных? m - количество поставщиков, n - количество потребителей).

Определяем потенциалы занятых клеток (таблица 4.1):

Таблица 4.3 Потенциалы

Считаем оценки свободных клеток таблицы 4.3:

S13=6- (0+5) =-1

S21=4- (4-3) =3

S22=5- (2-3) =6

S24=3- (2-3) =4

S31=4- (0+4) =0

S32=4- (0+2) =2

S41=0- (4-5) =1

S42=0- (2-5) =3

S44=0-- (2-5) =3

План X0 - является оптимальным планом, так как нет отрицательных оценок, при этом единственным, так как нет оценок равных 0.

Ответ: План перевозок продукции, при котором минимизируются суммарные затраты на её изготовление и доставку потребителям, при обязательном условии, что продукция пункта 1, в котором себестоимость её производства наименьшая, распределяется полностью равен X0? суммарные затраты =435

5. Слайды презентации

Данная тема "Метод ветвей и границ" представлена презентацией в Microsoft PowerPoint. Изложение данной темы было представлено в сжатом, но доступном и понятном виде. Начало презентации открывается слайдом названия темы дисциплины (рисунок 5.1) и слайдом по названию темы (рисунок 5.2):

Рисунок 5.1 - Слайд первый

Рисунок 5.2 - Слайд второй

Далее предоставляется слайд с содержанием презентации (рисунок 5.3):

Рисунок 5.3 - Слайд третий

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

Рисунок 5.4 - Слайд четвертый

Рисунок 5.5 - Слайд пятый

Рисунок 5.6 - Слайд шестой

На четвертом, пятом, шестом и седьмом слайдах (рисунок 5.4, рисунок 5.5, рисунок 5.6, рисунок 7.6) можно увидеть основные определения метода ветвей и границ.

Рисунок 5.7 - Слайд седьмой

Далее, начиная с восьмого слайда, идет пример решения задачи линейного программирования методом ветвей и границ (рисунки 5.8-5.15).

Рисунок 5.8 - Восьмой слайд

Рисунок 5.9 - Девятый слайд

Рисунок 5.10 - Десятый слайд

Рисунок 5.11 - Слайд одиннадцатый

Рисунок 5.12 - Слайд двенадцатый

Рисунок 5.13 - Слайд тринадцатый

Рисунок 5.14 - Слайд четырнадцатый

Рисунок 5.15 - Слайд пятнадцатый

На шестнадцатом слайде (рисунок 5.16) представляется дерево решений задачи.

Рисунок 5.16 - Слайд шестнадцатый

На последнем слайде (рисунок 5.17) представляется информация об авторе данной презентации. С последнего слайда можно вернуться на содержание, на предыдущий слайд либо произвести выход из презентации, нажав на крайнюю правую кнопку выхода:

Рисунок 5.17 - Слайд семнадцатый

Заключение

В данном курсовом проекте была разобрана и изучена тема: "Метод ветвей и границ", по которой представлена презентация. В презентации были рассмотрены следующие разделы: основные понятия, пример целочисленного решения задачи линейного программирования графическим методом. Слайды презентации подробно описаны в пояснительной записке.

Так же были выполнены три практических расчета по темам: "Графический метод решения задач линейного программирования", "Симплекс - метод решения задач линейного программирования", "Решение транспортных задач".

Список использованных источников

1. Месхи Б.Ч. , Соболь Б.В. , Каныгин Г.И. (Феникс 2009 г)

2. Т.Л. Партыка, И.И. Попов. Математические методы: уч. - М.: Форум, 2007. - 464с. - (Проф. Образование).

3. Н.Ш. Крамер, Б.А. Путко, 2004г.

Размещено на Allbest.ru


Подобные документы

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены