Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Компьютеры, Программирование Компьютеры, Программирование

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

Крючки с поводками Mikado SSH Fudo "SB Chinu", №4BN, поводок 0,22 мм.
Качественные Японские крючки с лопаткой. Крючки с поводками – готовы к ловле. Высшего качества, исключительно острые японские крючки,
58 руб
Раздел: Размер от №1 до №10
Чашка "Неваляшка".
Ваши дети во время приёма пищи вечно проливают что-то на ковёр и пол, пачкают руки, а Вы потом тратите уйму времени на выведение пятен с
222 руб
Раздел: Тарелки
Мыло металлическое "Ликвидатор".
Мыло для рук «Ликвидатор» уничтожает стойкие и трудно выводимые запахи за счёт особой реакции металла с вызывающими их элементами.
197 руб
Раздел: Ванная

ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РФ КАФЕДРА МТЕМАТИКИ КУРСОВАЯ РАБОТА тема: Применение метода ветвей и границ для задач календарного планирования Студент группы МЭК 1-1 Клеймёнов И.Д. Научный руководитель Солодовников А.С. МОСКВА, 2001г. План 1.Постановка задачи целочисленного программирования 3 2. Понятие о методе ветвей и границ 4 3.Применение метода ветвей и границ для задач календарного планирования 13 Летература 201.Постановка задачи целочисленного программирования По смыслу значительной части экономических задач, относятся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число судов при распределениях по линиям, число турбин в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие. Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,.,x ), при котором линейная функция (1) принимает максимальное или минимальное значение при ограничениях =bi , i=1, 2 , m. (2) хj ( 0, j=1, 2,., п. (3) xj — целые числа (4)2. Понятие о методе ветвей и границ Метод ветвей и границ — один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Метод ветвей и границ состоит в следующем: множество допустимых решений (планов) некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи. Алгоритм решения: Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax = F(Xo). Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Покажем, как это можно сделать, предварительно отметив, что F(X0) ( F(X) для всякого последующего плана X. Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла в плане X0 дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу 1. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования: Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев: 1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план.

Тогда этот план и значение целевой функции на нем и дают решение исходной задачи. 2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II). 3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение. Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II). 4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II). Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным. Итак, процесс нахождения решения задачи целочисленного программирования (1)- (4) методом ветвей и границ включает следующие основные этапы: 1°. Находят решение задачи линейного программирования (1)-(3). 2°. Составляют дополнительные ограничения для одной из пере-менных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом. 3°. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений. 4°. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод. Проиллюстрируем метод ветвей и границ на примере. Решить задачу Z = Зх1 х2 — maxпри ограничениях: 4xl Зх2 < 18, x1 2x2 ( 6, 0 ( x1 ( 5, 0 ( x2 ( 4, х1, x2 — целые числа. Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z0 = Z (0; 0) = 0. I этап. Решая задачу симплексным методом, получим Zmax = 13 при Х1 = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х1 дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х1 , т.е. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3: Задача 2 Z=3x1 x2>max при ограничениях: 4xl Зх2 < 18 x1 2x2 ( 6 0 ( x1 ( 4 0 ( x2 ( 4 х1, x2 — целые числа. Задача 3 Z=3x1 x2>max при ограничениях: 4xl Зх2 < 18 x1 2x2 ( 6 5 ( x1 ( 5 0 ( x2 ( 4 х1, x2 — целые числа. Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0= 0. II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплексным методом. Получим, что условия задачи 3 противоречивы.III этап. Решаем задачу 2 симплексным методом. Получим Zmax = 14/3 при X3 = (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3 ) = 14/3 > Z0 = 0, по-прежнему сохраняется Z0 = 0, ибо план нецелочисленный. Так как х2 — дробное число, из области решений исключаем полосу 0 < x2 < 1 и задачу 2 разбиваем на две задачи 4 и 5. Задача 4 Z=3x1 x2>max при ограничениях: 4xl Зх2 < 18 x1 2x2 ( 6 0 ( x1 ( 4 0 ( x2 ( 0 х1, x2 — целые числа. Задача 5 Z=3x1 x2>max при ограничениях: 4xl Зх2 < 18 x1 2x2 ( 6 0 ( x1 ( 4 1 ( x2 ( 4 х1, x2 — целые числа. Список задач: 4 и 5. Значение Z0 = 0. IV этап. Решаем задачу 4 симплексным методом. Получим Zmax = 12 при X4 = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0 = Z(X4 ) = 12, ибо план Х4 целочисленный. V этап. Решаем задачу 5 симплексным методом. Получим Zmax = 12,25 при X5 = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не меняется, т.е. Z0 = 12, ибо план X5 нецелочисленный. Так как х1 — дробное, из области решений исключаем полосу 3max при ограничениях: 4xl Зх2 < 18 x1 2x2 ( 6 4 ( x1 ( 4 1 ( x2 ( 4 х1, x2 — целые числа. Список задач: 6 и 7. Значение Z0 = 12. VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом. Получим, что условия задачи 7 противоречивы. VII этап. Решаем задачу 6 симплексным методом. Получим Zmax = 10,5 ,при X6 = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так какZ(X6 ) = 10,5 < Z0 = 12, то задача исключается из списка. Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X = Х4 = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax = 12 Замечание 1. Нетрудно видеть, что каждая последующая задача, составляемая в процессе применения метода ветвей и границ, отличается от предыдущей лишь одним неравенством — ограничением. Поэтому при решении каждой последующей задачи нет смысла решать ее симплексным методом с самого начала (с I шага).

Налоговое планирование осуществляет: 1) анализ деятельности предприятия в финансово-хозяйственном аспекте; 2) анализ действующего законодательства; 3) изучение конкретных проблем каждого налогоплательщика для выявления схем и методов по оптимизации налогообложения; 4) анализ методов оптимизации налогообложения, используемых конкурентами и партнерами, для применения наиболее эффективных схем на собственном предприятии; 5) применение наиболее результативных схем и методов налогообложения компании. 19. Понятие «бюджет» Понятие «бюджет» в современных условиях получило широкое распространение. Сегодня оно стало очень знакомым и близким понятием. Это связано с тем, что функция бюджета чрезвычайно полезна для контроля над деятельностью предприятия, для избежания непредвиденных ситуаций, для понимания того, на какой стадии развития находится компания. Процесс бюджетирования осуществляет функцию достижения поставленных целей и задач посредством планирования и распределения имеющихся в распоряжении предприятия ресурсов (в натуральных и финансовых показателях)

1. Прикладной системный анализ: сетевой анализ и календарное планирование проектов, метод прогнозного графа

2. Разработка программы поиска решения системы дифференциальных уравнений двумя методами: Рунге-Кутта и Рунге-Кутта-Мерсона

3. Методы вывода человека из бытовой депрессии с использованием общеизвестных направлений и методов научной психологии

4. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

5. Метод ветвей и границ (контрольная)

6. Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса
7. Франц Боас "Границы сравнительного метода в антропологии"
8. Сущность, методы и границы познания

9. Конвертер программы с подмножества языка Си в Паскаль с использованием LL(1) метода синтаксического анализа (выражения)

10. Производственная программа предприятия и методы ее расчета

11. Расчет сетевой модели методом Форда (с программой)

12. Конвертер программы с подмножества языка Си в Паскаль с использованием LL(1) метода синтаксического анализа

13. Вредоносные программы, классификация. Методы защиты

14. Новый подход к построению методов межпроцедурного анализа программ

15. Численные методы. Программа-калькулятор на Pascal

16. Виды, методы и программы налоговых проверок

Набор детской складной мебели "Первоклашка. Осень".
В комплект входит стол-парта и стул с мягким сиденьем, пенал. Металлический каркас. Столешница облицована пленкой с тематическими
1637 руб
Раздел: Наборы детской мебели
Счеты детские "Умный жираф".
Счеты - это не только первый математический прибор, но и увлекательная игра. Пусть ребенок отсчитает столько косточек на счетах, сколько у
377 руб
Раздел: Счетные наборы, веера
Шкатулка для рукоделия "Сундучок", 18x13x8 см, арт. 80863.
Такая шкатулка послужит оригинальным, а главное, практичным подарком, в котором замечательно сочетаются внешний вид и функциональность.
627 руб
Раздел: Шкатулки для рукоделия

17. Исследование природных ресурсов планеты с помощью космических методов

18. Исследование клеточного цикла методом проточной цитометрии

19. ОСНОВНЫЕ МЕТОДЫ ГЕНЕТИКИ

20. Методы психогенетики

21. Обзор методов и способов измерения физико-механических параметров рыбы

22. Новейшие методы селекции: клеточная инженерия, генная инженерия, хромосомная инженерия
23. Зажигательные смеси, состав, средства применения и доставки, вызываемые повреждения, методы лечения и защиты
24. Методы и модели демографических процессов

25. Гидрохимический, атмохический и биогеохимический методы поисков

26. Добыча золота методами геотехнологии

27. Государственное регулирование экономики: формы и методы

28. Сущность, методы и формы государственного регулирования внешнеэкономической деятельности Российской Федерации

29. Предмет, метод, источники Административного права

30. Методы осуществления государственной власти

31. Метод гражданско правового регулирования

32. Формы и методы государственного регулирования экономики в Казахстане

Чайник со свистком Nadoba "Virga", 2,8 л.
Чайники серии Virga изготовлены из высококачественной нержавеющей стали 18/10. Прочное трехслойное капсульное дно изделий не деформируется
2499 руб
Раздел: Чайники из нержавеющей стали
Настольная игра "Колорама".
Ты знаешь цвета и формы? Красные круги, желтые четырехугольники, синие треугольники - пестрая неразбериха! На костях выброшен квадрат и
1363 руб
Раздел: Классические игры
Фломастеры "Замок", 50 цветов.
Количество цветов: 50. Очень качественные фломастеры. Чернила на водной основе и натуральных красителях. Яркие, насыщенные
761 руб
Раздел: Более 24 цветов

33. Швейцарская Конфедерация. Три ветви власти

34. Правила таможенного контроля и оформления транспортных средств, перемещение их через таможенную границу Украины

35. Особенности выбора таможенных режимов при перемещении товаров через таможенную границу

36. Методы комплексной оценки хозяйственно-финансовой деятельности

37. Конституция в киберпространстве: закон и свобода за электронной границей (english/russian)

38. Эффективные методы изучения иностранных языков
39. Метод действенного анализа в режиссуре театра, кино и телевидения
40. Соцреализм как метод искусства

41. Дидактические возможности отдельных методов обучения на уроках литературы в старших классах

42. Методы изучения музыкальных произведений крупной формы в старших классах общеобразовательной школы

43. Цивилизационные методы в изучении истории

44. Методы компьютерной обработки статистических данных. Проверка однородности двух выборок

45. Методичка по Internet Explore

46. Шифрование по методу UUE

47. Разработка методов определения эффективности торговых интернет систем

48. Метод Дэвидона-Флетчера-Пауэлла

Беговел "Funny Wheels Rider Sport" (цвет: голубой).
Беговел - это современный аналог детского велосипеда без педалей для самых маленьких любителей спорта. Удобный и простой в
2900 руб
Раздел: Беговелы
Насадка на кран "Палитра", светодиодная.
Светодиодная насадка «Палитра» включается под напором воды и, в зависимости от ее температуры, подсвечивает проходящий поток в синий,
490 руб
Раздел: Ванная
Чайник эмалированный "Шиповник" EM-40X1/45, с керамической ручкой, 4 л.
Объем: 4 л. Внешнее высокопрочное трехслойное эмалевое покрытие. Внутреннее эмалевое покрытие, устойчивое к воздействию пищевых
1323 руб
Раздел: Чайники эмалированные

49. Защита информации от несанкционированного доступа методом криптопреобразования /ГОСТ/

50. Обучение начальных курсов методам программирования на языке Turbo Pascal

51. Применение методов линейного программирования в военном деле. Симплекс-метод

52. Вычисление площади сложной фигуры методом имитационного моделирования (Windows)

53. Математические методы и языки программирования: симплекс метод

54. Лекции по высокоуровневым методам информатики и программированию
55. Метод Симпсона на компьютере
56. Полином Гира (экстраполяция методом Гира)

57. Компьютерные вирусы, типы вирусов, методы борьбы с вирусами

58. Анализ криптостойкости методов защиты информации в операционных системах Microsoft Window 9x

59. Парольные методы защиты информации в компьютерных системах от несанкционированного доступа

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

61. Решение задач - методы спуска

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

63. Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка

64. Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

Фоторамка на 8 фотографий С31-025 Alparaisa "Love&Family", бронзовый, 70,5x34 см.
Размеры рамки: 70,5x34 cм. Размеры фото: - 15х10 см (4 штуки), - 10х15 см (4 штуки). Фоторамка-коллаж для 8-ми фотографий. Материал:
636 руб
Раздел: Мультирамки
Ручка перьевая "Velvet Prestige", синяя, 0,8 мм, корпус черный/золото.
Перьевая ручка Velvet Prestige. Цвет корпуса: черный/золото. Материал корпуса: металл. Материал пера: иридий.
404 руб
Раздел: VIP-ручки
Сушилка для белья "Ника" напольная складная, 20 метров.
Размер: 200х55х96 см. Длина сушильного полотна: 20 метров. Сушилка для белья классическая для любых помещений. Напольная, складная, с
993 руб
Раздел: Сушилки напольные

65. Использование численных методов для решения дифуpов (2-го порядка) (, демонстрация применения интерполяции в среде MATHCAD-а)

66. Вычисление определенного интеграла методами трапеций и средних прямоугольников

67. Решение нелинейного уравнения методом касательных

68. Методы корреляционного и регрессионного анализа в экономических исследованиях

69. Современные криптографические методы

70. Математические методы в организации транспортного процесса
71. Метод последовательных уступок (Теория принятия решений)
72. Построение графика функции различными методами (самостоятельная работа учащихся)

73. Краткая методичка по логике

74. Методы решения систем линейных неравенств

75. Вычисление двойных интегралов методом ячеек

76. Методы обучения математике в 10 -11 класах

77. Решение задач линейной оптимизации симплекс – методом

78. Приближённые методы решения алгебраического уравнения

79. Решение дифференциальных уравнений 1 порядка методом Эйлера

80. Методы расчета электрических полей

Контейнер прямоугольный, 1850 мл.
Контейнер прямоугольный объемом 1850 мл. Герметичный. Широкий температурный диапазон использования. Материал: стекло, пластик,
447 руб
Раздел: Штучно
Папка-портфолио для школьника, на 4 кольцах, 20 файлов, 10 вкладышей.
Формат - A4. Размер - 245x320 мм. Наличие файлов - 20. Количество вкладышей - 10. Материал папки - твердый картон. Материал вкладыша -
371 руб
Раздел: Портфолио
Мел белый, 72 штуки.
В наборе: 72 мелка.
536 руб
Раздел: Мел

81. Метод Алексея Юрьевича Виноградова для решения краевых задач

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

83. Новый метод «дополнительных краевых условий» Алексея Юрьевича Виноградова для краевых задач

84. Лазерные методы диагностики. Термография

85. Объективные и субъективные признаки усталости, утомления и переутомления, их причины, методы устранения и профилактика

86. Дополнительные методы обследования легочных больных. Основные синдромы при заболеваниях легких
87. Хламидиоз. Методы определения/диагностики
88. Предмет, метод, содержание cудебной медицины

89. Методы оценки кровопотери в акушерстве

90. Метод Фолля

91. Пропедевтика: перкуторные границы органов

92. Современные методы лечения псориаза у детей

93. ДЭНС-ТЕРАПИЯ как новый и современный метод лечения в медицине

94. Русская здрава (методы оздоровления на Руси)

95. Методичка по экспериментальной хирургии (МБФ РГМУ)

96. Современные методы контрацепции

Пробка для шампанского "CooknCo".
Диаметр: 4,5 см. Высота: 5 см. Цвет: металл. Материал: нержавеющая сталь. Внешняя отделка: сатиновая.
410 руб
Раздел: Аксессуары для вина
Доска магнитно-маркерная, 100x150 см.
Размер: 100х150 см. Поверхность доски позволяет писать маркерами и прикреплять листы при помощи магнитов. Перед началом работы – удалить
3857 руб
Раздел: Доски магнитно-маркерные
Простыня на резинке "Беж", 160x200 см.
Трикотажная простыня "Tete-a-Tete" изготовлена из 100% хлопка высокого качества. Натуральный, экологически чистый материал
741 руб
Раздел: Простыни, пододеяльники

97. Некоторые проблемы преступности на государственных границах РФ /по данным 1994-95 гг./

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

99. Понятие и основные методы исследовательской фотографии

100. Загрязнение водных ресурсов и методы очистки


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.