Контрольная: Метод ветвей и границ - текст контрольной. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Контрольная

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

Банк рефератов / Экономика и финансы

Рубрики  Рубрики реферат банка

закрыть
Категория: Контрольная работа
Язык контрольной: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 1002 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной работы

Узнайте стоимость написания уникальной работы

Министерство обр азования Р.Ф. Тюменский государственный нефтегазов ый университет Институт нефти и газа Кафедра менеджмента В отраслях ТЭ К Контрольная работа по Дисциплине «Экономическая математика , методы и модели» Вариант № 4 Выполнил : студент гр. МОс 2 Ваганова А.Р. Проверил : Захаров А.В Тюмень 2002 г. Метод ветвей и границ . Рассмотрим з адачу , состоящую в определении максима льн ого значения функции при условиях Как и при решении сф ормулированной задачи методом Г омори , первоначально находим симплексным методом искусственного базиса оптимальный план задач и без учета целочисленности переменных . Пусть им является план X 0 . Если среди компонент этого плана н ет дробных чисел , то тем самым найде но искомое решение задачи и . Если же компонент плана Х 0 имеются дробные числа , то Х 0 не удовлетворяет условию целочисленности и необходимо осуществи ть у порядоченный переход к новым план ам , пока не будет найдено решение задачи . Покажем , как это можно сделать , предварит ельно отметив , что для всякого п оследующег о плана Х. Предполагая , что найденный оптимальный п лан Х 0 не удовлетворяе т условию целочисленности переменных , тем сам ым считаем , что среди его компонент есть дробные числа . Пусть например переменная приняла в пла не Х 0 дробное значение . Тогда в оптимальном целочисленном плане её значение будет по крайней мере либо больше , либо меньше или равно ближайшему меньшему целому числу , либо больше или равно ближайшему большему целому числу . Определяя эт и числа , находим симпл ексным методом р ешение двух задач линейного программирования : Найдем рассмотренными выше методами решение задач линейного программирования ( I ) и ( II ). Очеви дно , здесь возможен один из следующих 4: 1. Одна из задач неразрешима , а д ругая имеет целочисленный оптимальный план . Т огда этот план и значение целевой функции на нём и дают решение исходной задач и. 2. Одна из задач нер азрешима , а другая имеет оптимальный пла н , среди компонент которого есть дробные ч исла . Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент , значение которой равно дробному числу , и строим две задачи , аналогичные за дачам ( I ) и ( II ). 3. Обе задачи разрешимы. Одна из задач имеет оптимальный це лочисленный план , а в оптимальном плане вт орой задачи есть дробные числа . Тогда вычи сляем значение целевой функции на этих пл анах и сравниваем их между собой . Если на целочисленном оптимальном плане значение целевой функ ц ии больше , или рав но ее значению на плане , среди компонент которого есть дробные числа , то данный целочисленный план является оптимальным для исходной задачи и он вместе со значени ем целевой функции на нем дает искомое решение. Если же знач ение целевой фу нкции больше на плане , среди компонент которого есть дробные чи сла , то следует взять одно из таких чи сел и для задачи , план которой рассматрива ется , необходимо построить две задачи , аналоги чные ( I ) и ( II ). 4. Обе задачи разрешимы , и среди оптимальных плано в обеих задач есть д робные числа . Тогда выделяем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач , для которой значение целевой функции является наибольшим . В оптимальном плане этой задачи выбираем одну из компонент , значе н ие котор ой является дробным числом , и строим две задачи , аналогичные ( I ) и ( II ). Таким образом , описанный выше интеграционный процесс может б ыть представлен в виде некоторого дерева , на котором исходная вершина отвечает оптималь ному плану Х 0 задачи (32)-( 34), а каждая соединенная с ней ветвь ю вершина отвечает оптимальным планам задач ( I ) и ( II ). Каждая из этих вершин имеет свои ветвления . При этом на каждом шаге выбирается та вершина , для которой значение является наибольшим . Е сли на некотором шаге будет получен план , имеющий целочисленные компоненты , и знач ение функции на нем окажется больше или равно , чем значение функции в других во зможных для ветвления вершинах , то данный план является оптимальным планом исходной зад ачи целочисленного программирования и значение целевой функции на нем является максимальным. Итак , процесс нахождения решения задачи целочисленного программирования (32)-(35) методом ветве й и границ включает следующие этапы : 1 0 Находят ре шение задачи линейного программирования (32)-(34) 2 0 Составляют дополнительные ограничения для одной из пе ременных , значение которой в оптимальном план е задачи (32)-(34) является дробным числом. 3 0 Находят ре шения задач ( I ) и ( II ), которые получаются из задачи (32)-(34) в результа те присоединения дополнит ельных ограничений. 4 0 В случае необходимости составляют дополнительные ограничен ия для переменной , значение которой является дробным , формулируют задачи , аналогичные зада чам (I) и (II), и находят их решение . Интеграцион ный процесс продолжают до тех п ор , пока не будет найдена вершина , соответствую щая целочисленному плану задачи (32)-(34) и такая , что значение в этой вершине больше или равно значению функции в других возможны х для ветвления вершинах. Описанный выше метод ветвей и границ имеет более прос тую логическую схему расчетов , чем рассмотренный выше метод Го мори . Поэтому в большинстве случаев для на хождения решения конкретных задач целочисленного программирования с использованием ЭВМ примен яется именно этот метод . В частности в рассмотренном выше П ПП «Линейное программирование в АСУ» для отыскания целочис ленного решения конкретных задач используется метод ветвления и границ. 2.51 Методом ветвей и границ найти решение задачи , состоящей в определении максимального значения функции при условиях x j – целые (j= ) Р е ш е н и е . Находим решение сформулированной задачи симплексным методом без учета услов ия целочисленности пер еменных . В результа те устанавливаем , что такая задача имеет о птимальный план Х 0 = (18/5, 3/5, 0, 0, 24/5). При этом плане F= ( X 0 )=39/5. Так как в плане Х 0 значения трех переменных являются дробными числами , то Х 0 не удовлетворяет условию целочисленности , и следовательно , не является оптимальны м планом исходной задачи. Возьмем какую-нибудь переменную , значение которой является дробным числом , например х 1. Тогда эта перем енная в оптимальном плане исходной задачи будет принимать зн ачение , либо меньшее или рав ное трём : , либо больше или равно четырём : . Рассмотрим две зад ачи линейного п рограммирования : ( I ) ( II ) Задача ( I ) имеет оп тимальный план на котором зн ачение целевой функции . Задача ( II ) неразрешима. Исследуем задачу ( I ). Так как среди компонент оптима льного плана этой задачи есть дробные чис ла , то для одной из переменных , например x 2 , вводим дополните льные ограничения : Рассмотрим теперь следующие две задачи : ( III ) ( IV ) Задача ( IV ) неразрешима , а задача ( III ) и меет оптимальный план (3, 1, 3, 3, 3), на котором значение целевой функции задачи Таким образом исходная задача целочисленн ог о программирования имеет оптимальный пл ан Х * = (3, 1, 2, 3, 3). При этом плане целевая функция принимает максимал ьное значение . Схему реализованного выше выч ислительного процесса можно представить в виде дерева , ветвями которого являются со ответствующие ограничения на переменные , а ве ршинами – решения соответствующих задач лине йного программирования (рис 2.5). Дадим геометрическую интерпретацию решения задачи (50)-(53). На рис . 2.6 показана область допустимых решений задачи (50)-(52). Из него видно , что данная задача и меет оптимальный план (18/5, 3/5, 0, 0, 24/5). В то же время не является п ланом задачи (50)-(53), поскольку три переменные имею т дробные значения . Возьмем переменную х 1 и рассмотрим зада чи ( I ) и ( II ) . Как в идно из рис . 2.7задача ( I ) имеет оптималь ный план (3, 3/2, 0, 9/2, 3/2), а из ри с .2.8 следует , что задача ( II ) неразрешима. Поскольку среди компонент плана есть дробные чи сла , выберем переменную х 2 и рассмотрим задачи (III) ( IV ). Задача ( III ) имеет оптимальный план (3, 1, 2, 3, 3) (рис . 2.9), а з адача ( IV ) нераз решима (рис . 2.10). Итак , Х * = (3, 1, 2, 3, 3) является оптимальным планом задачи (50)-(53). При этом плане . Решение задачи , правые части которых содержат параметр. Алгоритм решения задачи (60)-(62) подобе н рассмотренному выше алгоритму решения задач и (57)-(59). Полагая значение параметра t равным некото рому числу t 0 , н ах одим решение полученной задачи линейного прог раммирования (60)-(62). При данном значении параметра t 0 либо определяем оптимальный план , либо устанавливаем неразрешимос ть задачи . В первом случае найденный план является оптимальным для любого , где и числа q i и p i определены компонентами оптимального плана и зависят от t 0 : Если при t = t 0 задача (60)-(62) неразрешима , то , либо целевая функция задачи (60) не огранич ена на множестве планов , либо система урав нений не имеет неотрицательных решений . В первом случае задача неразрешима для всех , а во втором случае определяем все значения параметра , для которых система уравнени й (61) несовместна , и исключа ем их из рассмотрения. После определения промежутка , в котором задача (60)-(62) имеет оди н и тот же оптимальный план или нераз решима , выбираем новое значение параметра t, не принадлежащее найденному промежутку , и наход им решен ие полученной задачи линейного программирования . При этом решение новой за дачи ищем с помощью действенного симплекс-мет ода . Продолжая итерационный процесс , после кон ечного числа шагов получаем решение задачи (60)-(62). Итак , процесс нахождения задачи (60) -(62) включает следующие основные этапы : 1 0 . Считая значени е параметра t равным некоторому числу , находят опти мальный план или устанавливают неразрешимость полученной задачи линейного программирования. 2 0 . Находят значен ия параметра , для которых задача (60)-(62) имеет один и тот же оптимальный план или неразреш има . Эти значения параметра t исключают из рассмотрения. 3 0 . Выбирают значе ния параметра t из оставшейся части промежутка и устанавливают возможность определ ения нового оптимальн ого плана находят его двойственным симплекс-м етодом. 4 0 . Определяют мно жество значений параметра t, для которых задача имеет один и тот же новый оптимальны й план или неразрешима . Вычисления проводят до тех пор , пока не будут исследов аны все значения параметра . 2.66. Для каждого значения параметра найти максимальное значение функции при условиях Р е ш е н и е . Считая значение параметра t в си стеме уравнений (81) равным нулю , находим решение задачи (80)-(82) (табл . 2. 41). Таблица 2.41 i Базис С б Р 0 3 -2 5 0 -4 Р 1 Р 2 Р 3 Р 4 Р 5 1 Р 3 5 12+ t 1 1 1 0 0 2 Р 4 0 8+4 t 2 -1 0 1 0 3 Р 5 -4 10-6 t -2 2 0 0 1 4 20+29 t 10 -1 0 0 0 1 Р 3 5 7+4 t 2 0 1 0 -Ѕ 2 Р 4 0 13+ t 1 0 0 1 Ѕ 3 Р 2 -2 5-3 t -1 1 0 0 Ѕ 4 25+26 t 9 0 0 0 Ѕ Как видно из табл . 2.41, при t =0 есть оптимальный план задачи . Однако является оптимал ьным планом и тогда среди его компонентов не окажется отрицательных чисел , т.е . при 5-3 t 0; 7+4 t 0; 13+ t или при Таким образом , если то - оптимальный план задачи (80)-(82), при котором Исследуем теперь , имеет ли задача оптимальные планы при . Если , то 5-3t<0 и следовательно , X =(0,5 – 3 t , 7+4 t , 13+ t , 0) не является планом задачи . Поэтому при нужно перейти к н овому плану , который был в то же время оп тимальным . Это можно сделать в том случае , когда в строке вектора Р 2 и меются отрицательные числа . В данном случае эт о условие выполняется . Поэтому переходим к новому опорному плану , для чего введем в базис вектор Р 1 и исключаем из него вектор Р 2 (та бл . 2.42). Таблица 2.42 i Базис С б Р 0 3 -2 5 0 -4 Р 1 Р 2 Р 3 Р 4 Р 5 1 Р 3 5 17 + 2 t 0 2 1 0 Ѕ 2 Р 4 0 1 8 -2 t 0 1 0 1 1 3 Р 1 3 -5+3 t 1 -1 0 0 -Ѕ 4 70- t 0 9 0 0 5 Как видно из т абл . 2.42, -оптимальный пл ан задачи для всех t , при которых Следовательно , если является оптимальны м планом исходной задачи , причем . Если t> 17/2, то не является пла ном задачи , так как третья компонента 17 – 2 t есть отрицате льное число . Поскольку среди элементов 1-й строки табл . 2.42 нет отрицательных при t > 17/2 исходн ая задача неразрешима. Исследуем теперь разрешимость задачи при t < -7/4. В эт ом случае Х = (0,5 -3 t , 7+4 t , 13+ t , 0) (см . табл .2.41) не является планом задачи , так как третья компонента 7+4 t есть отрицательное число . Чтобы при данном значени и параметра найти оптимальный план (это можно сделать , так как в строке векто ра Р 3 стоит отрицательное число -1/2), нужно исключить из базиса вектор Р 3 и ввести в базис вектор Р 5 (табл . 2.43). Таблица 2.43 i Базис С б Р 0 3 -2 5 0 -4 Р 1 Р 2 Р 3 Р 4 Р 5 1 Р 5 -4 -14-8 t -4 0 -2 0 1 2 Р 4 0 20+5t 3 0 1 1 0 3 Р 2 -2 12+t 1 1 1 0 0 4 32+30t 11 11 1 0 0 Как видно из табл . 2.43, является оптимал ьным планом задачи для всех значений пара метра t , при которых Таким образом , если , то задача (80)-(82) имеет оптимальный план , при котором Из табл . 2.43 так же видно , что при t <4 задача неразреши ма , поскольку в строке вектора Р 4 нет от рицательных элементов . Итак , если , то задача не имеет оптимального плана ; если оптимальный план , а если , то - оптимальный план , а если , то - оптимальный план , а если , то задача неразрешима.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Это смерть забирает лучших, а военкомат всех подряд.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru