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

Контрольная

Решение задачи о ранце методом ветвей и границ

Банк рефератов / Программирование

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

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

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

10 Лабораторная работа № 6 Телешовой Елизаветы , гр . 726, Решение задачи о ранце методом ветвей и границ. 1. Постановка задачи. 1929 год . В США великая депрессия , введен сухой закон . Страна просто задыхается без спиртного . В этот сложный момент группа инициативных граждан под руководством Аль Капоне решает помочь родной стране . Ими планируется поставка алкогольной продукции из Ливерпуля в Штаты . Благодарные сограждане из 5 крупных городов США готовы платить большие деньги за тонну спиртного : 2000 долл . в Бостоне , 3000 в Детройте , 2500 в Вашингтоне , 3200 в Нью-Йорке и 1800 долл в Чикаго . Все 5 городов находятся на разном расстоянии от порта , куда прибывает груз : Бостон – 250 миль , Детройт – 300 миль , Вашингтон – 500 миль , Нью-Йорк – 100 миль и Чикаго – 600 миль . Требуется выбрать города , в которых можно получить максимальную приб ы ль от продажи спиртного . При этом суммарное расстояние от этих портов до порта с грузом не должно превышать 1000 миль. 2. Решение задачи. Данная задача является задачей о ранце вида : , (1) где критерием является функция , (2) которая может быть устремлена и к максимуму , и к минимуму . Для начала составим следующую математическую модель : Пусть – j -тый город , откуда соответственно . При этом , если в j -тый город будет разгружаться алкогольная продукция , то , иначе . Другим ограничением будет являться суммарное расстояние до порта с грузом . Таким образом : ; Целевой функцией или критерием будет являться максимальная благодарность сограждан : . Далее отбираем п орты по приоритетности , т.е . в порядке убывания отношения : (3); (2); (4); (1); (5). После этого определяем начальный план следующим образом : пусть , поскольку отношение наибольшее , и следовательно продажа спиртного в Нью-Йорке даст наиб ольшую прибыль при наименьших затратах , которые зависят от расстояния . Вычитая из суммарного расстояния расстояние до порта мы получим расстояние , которое ра зделяется между остальными городами , т.е .: , ; Аналогично рас суждая , далее получаем : , ; , ; В последнем случае оставшееся после других городов расстояние меньше 500 миль , поэтому будет дробным : , => . Таким образом , начальный опорный план : . Значение целевой функции : . Но обязательно целое . Поэтому чтобы определить , чему все же равен : 0 или 1 вычислим следующие значения : ; – целая часть критерия при существующем опорном плане . ; – значение критерия при целочисленном опорном плане , т.е . . Множество D , которому принадлежит имеет , . Разделим его на 2 подмножества , такие что : ; - здесь . - здесь . 1) Анализ множества D 1 . Поскольку целевая функция и ограничения будут иметь вид : Строим новый опорный план : , ; , ; , ; Т.к . , поэтому б удет дробным : , => . Таким образом , новый опорный план : . ; , при . 2) Анализ множества D 2 . Поскольку целевая функция и ограничения будут иметь вид : => . Строим новый опорный план : , ; , ; Т.к . , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; , при . 3) Отсев неперспективного подмножества. . Так как и больше Rec , то оба подмножества можно считать перспективными , но поскольку , то далее мы будем исследовать подмножество D 2 . Разделим его на 2 подмножества , такие что : ; - здесь . - здесь . 4) Анализ множества D 3 . Поскольку , целевая функция и ограничения будут иметь вид : . Строим новый опорный план : , ; , ; Т.к . , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; , при . 5) Анализ множества D 4 . Поскольку , целевая функция и о граничения будут иметь вид : => . Строим новый опорный план : , ; Т.к . , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; , при . 6) Отсев неперспективного подмножества. . Так как и больше Rec , то оба подмножества можно считать перспективными , но поскольку , то далее мы будем исследовать подмножество D 3 . Р азделим его на 2 подмножества , такие что : ; - здесь . - здесь . 7) Анализ множества D 5 . Поскольку , , целевая функция и ограничения будут иметь вид : . Строим новый опорный план , очевидно : . При , ограничение выполняется всегда. ; , при . 8) Анализ множества D 6 . Поскольку , , целевая функция и ограничения будут иметь вид : . Ограничение несовместное , поскольку даже при оно не выполняется . Следовательно множество D 6 не существует. Таким образом , оптимальным планом данной задачи буд ет : , то есть алкоголь выгоднее всего поставлять в 3 города : Детройт , Вашингтон и Нью-Йорк . При этом прибыль составит 8700 долл. 3. Постановка задачи о мног омерном ранце. В связи с тем , что спиртное стало хорошо раскупаться , Аль Капоне решил увеличить поставки . Но чтобы мирно спящее ФБР не дай бог не проснулось , было решено осуществлять поставки через три разных порта на восточном побережье . Цены на спиртное в пяти вышеуказанных городах не изменились , расстояние же от них (в милях ) до портов указано в следующей таблице : Бостон Детройт Вашингтон Нью-Йорк Чикаго Порт 1 250 300 500 100 600 Порт 2 100 200 700 400 300 Порт 3 500 400 300 550 150 Во всех трех сл учаях суммарное расстояние от порта до городов не должно превышать 1000 миль . Требуется решить тот же самый вопрос : в какие города выгоднее поставлять продукцию ? 4. Решение задачи о многомерном ранце (вручную ). Задача о многомерном ранце имеет следующую ма тематическую модель : , (3) где критерием является функция , (4) От задачи об одномерном ранце она отличается наличием нескольких ограничений . Таким образом , математическая модель : Пусть – j -тый город , откуда соответственно . При этом , если в j -тый город будет разгружаться алкогольная продукция , то , иначе . ; Целевой функцие й или критерием будет являться максимальная благодарность сограждан : . Решим задачу оценки критерия для каждого ограничения в отдельности . Пусть множество относится к перво му ограничению , – ко второму , а – к третьему. 1) Анализ множества . (3); (2); (4); (1); (5). Определяем начальный план : , ; , ; , ; В последнем случае оставшееся после других городов расстояние меньше 500 миль , поэтому будет дро бным : , => . Таким образом , начальный опорный план : . ; 2) Анализ множества . (1); (2); (5); (3); (4). Определяем начальный план : , ; , ; , ; В последнем случае оставшееся после других городов расстояние также равно 300 миль , по этому будет целым : , => . Таким образом , опорный план : . ; 3) Анализ множества . (5); (2); (3); (4); (1). Определяем начальный план : , ; , ; , ; В последнем случае оставшееся после других городов расстояние меньше 550 миль , поэтому будет дробным : , => . Таким образом , опорный план : . ; 4) Вычислени е верхней и нижней границ. Вычисляем верхнюю границу : ; – третье ограничение более жесткое , далее будем исследовать опорный план . Определяем опорные планы для третьего ограничения : a ) , ; , ; В последнем случае оставшееся после других городов расстояние равно 50 миль , поэтому . Таким образом : . б ) , ; , ; В последнем случае оставшееся пос ле других городов расстояние равно 100 миль , поэтому . Таким образом : . в ) В этом случае . Вычисляем нижнюю границу : ; ; ; . 5) Ветвление множества D . ; - здесь . - здесь . 6) Анализ множества D 1 . a ) Определяем начальный план для : , ; , ; В последнем случае оставшееся после других городов расстояние меньше 500 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; б ) Определяем начальный план для : , ; , ; , ; В последнем случае оставшееся после других городов расстояние меньше 700 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; в ) Опр еделяем начальный план для : , ; , ; , ; В последнем случае оставшееся после других городов расстояние меньше 100 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; г ) Вычисление верхней и нижней границ. Вычисляем верхнюю границу : ; – первое ограничение более жесткое. Определяем опорные планы для первого ограничения : – В этом случае . – , ; , ; В последнем случае оставшееся после других городов рас стояние равно 450 миль , поэтому . Таким образом : . – , ; , ; В последнем случае оставшееся после других городов расстояние равно 100 миль , поэтому . Таким образом : . Вычисляем нижнюю границу : Т.к . , то ; ; . 7) Анализ множества D 2 . Поскольку , то : . => ; a ) Определяем начальный план для : , ; , ; В последнем случае оставшееся после других городов расстояние меньше 500 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; б ) Определяем начальный план для : , ; , ; , ; Таким образом , новый опорный план : . ; в ) Определяем начальный план для : , ; В последнем случае оставшееся после других городов расстояние меньше 400 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; г ) Вычисление верхней и нижней границ. Вычисляем верхнюю границу : ; – третье ограничение более жесткое. Определяем опорные планы для третьего ограничения : – , ; В последнем случае оставшееся после других городов расстояние равно 50 миль , поэтому . Таким образом : . – , ; , ; В последнем случае оставшееся после других городов расстояние равно 50 миль , поэтому . Таким образом : . – В этом случае . Вычисляем нижнюю границу : Т.к . , то ; ; . 8) Отсев неперспективного подмножества. . Так как и больше Rec , то оба подмножества перспективные , но поскольку , то далее мы будем исследовать , как более перспективное. ; - здесь . - здесь . 9) Анализ множества D 3 . Поскольку , то : a ) Определяем начальный план для : , ; , ; В последнем случае оставшееся после других городов расстояние меньше 600 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; б ) Определяем начальный план для : , ; , ; В последнем случае оставшееся после других городов расстояние меньше 700 миль , п оэтому будет дробным : , => . Таким образом , новый опорный план : . ; в ) Определяем начальный план для : , ; В последнем случае оста вшееся после других городов расстояние меньше 350 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; г ) Вычисление верхней и нижней границ. Вычисляем верхнюю границу : ; – третье ограничение более жесткое. Определяем опорные планы для третьего ограничения : – , ; , ; В посл еднем случае оставшееся после других городов расстояние равно 100 миль , поэтому . Таким образом : . – , ; , ; В последнем случае оставшееся после других городов расстояние равно 30 0 миль , поэтому . Таким образом : . – В этом случае . Вычисляем нижнюю границу : ; Т.к . , то ; . 10) Анализ множества D 4 . Поскольку , то : . => ; a ) Определяем начальный план для : , ; В последнем случае оставшееся после других городов расстояние меньше 500 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; б ) Определяем начальный план для : , ; , ; Таким образом , новый опорный план : . ; в ) Определяем начальный план для : В этом случае оставшееся после других городов расстояние меньше 150 миль , поэтому будет дробным : , => . Таким образом , новый опорный план : . ; г ) Вычисление верхней и нижней границ. Вычисляем верхнюю границу : ; – третье ограничение более жесткое. Определяем опорные планы для третьего ограничения : Очевидно , что поскольку , то . Вычисляем нижнюю границу : Т.к . , то ; . Так как и больше Rec , то оба подмножества перспективные , но поскольку , то подмножество более перспективное , следовательно оптимальным планом будет . То есть города , удовлетв оряющие всем 3 условиям и при этом дающие максимальную прибыль – Детройт и Нью-Йорк.
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