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

Вторым ограничением является суммарное расстояние до порта с продукцией. Значит:,- целые числа.Критерий или целевой функцией является максимальное вознаграждение от сограждан:Далее выбираем порты в порядке убывания отношения , т.е. по приоритетности:;;;;;Начальный план определим таким образом: пусть т.к. соотношение наибольшее. Это значит, что продажа алкоголя в Нью-Йорке обеспечит за наибольшую прибыль при наименьших затратах, зависящих от расстояния. Из суммарного расстояния b=1000 вычтем расстояние до порта, мы получаем расстояние, которое нужно разделить между оставшимися городами:Рассуждая аналогично, получаем далее:В итоге расстояние, оставшееся после других городов, будет меньше 500 миль, поэтому x3 является дробным:Значит начальный опорный план:Значение критерия (целевой функции):Однако, значение обязательно целое. Для того чтобы определить чему равен x3: 1или 0, необходимо вычислить: V- целую часть критерия при имеющееся опорном плане, М - значение критерия в случае целочисленном опорном плане. В данном случаеD – это множество, которому принадлежит , имеет .Поделим его на 2 подмножества D1 и D2, такие что:, здесь x3=0,, здесь x3=1,Проанализируем множество D1:В случае, когда x3=0, целевую функцию и ограничения можно записать в виде:,- целые числа.Построим новый опорный план:Так как 350<650, то x5 является дробным:Тогда новый опорный план: , при,Проанализируем множество D2:В случае, когда x3=1, целевую функцию и ограничения можно записать в виде:,- целые числа,- целые числаПостроим новый опорный план: Так как 100<250, то x1 является дробным:Тогда новый опорный план: , при.Отсеем неперспективное подмножество:.и больше , то оба подмножества можно считать перспективными. Однако М2>М1, поэтому далее будем исследовать подмножествоD2. Разделим его на 2 подмножества, такие что:, здесь x1=0., здесь x1=1.Проанализируем множество D3:Учитывая, что x3=1 и x1=0, целевую функцию и ограничения можно записать в виде:,- целые числаПостроим новый опорный план: Так как 100<600, то x5 является дробным:Тогда новый опорный план: , при.Проанализируем множество D4:Учитывая, что x3=1 и x1=1, целевую функцию и ограничения можно записать в виде:,- целые числа,- целые числаПостроим новый опорный план: Так как 150<300, то x2 является дробным:Тогда новый опорный план: , при,Отсеем неперспективное подмножество:.и больше , то оба подмножества можно считать перспективными. Однако М3>М4, поэтому далее будем исследовать подмножествоD3. Разделим его на 2 подмножества, такие что:, здесь x5=0., здесь x5=1.Проанализируем множество D5:Учитывая, что x3=1, x1=0 и x5=0, целевую функцию и ограничения можно записать в виде:,- целые числаПостроим новый опорный план: Учитывая, что x1=0 и x5=0, ограничение выполняется всегда, при.Проанализируем множество D6:Учитывая, что x3=1, x1=0 и x5=1, целевую функцию и ограничения можно записать в виде:,- целые числаОграничение является несовместным, потому что даже приx2=x4=0 оно невыполнимо. Значит, множества D6 не существует.Учитывая вышеизложенное, оптимальным планом для данной задачи будет:. Получается, что выгоднее всего поставить алкоголь в три города: Детройт, Вашингтон и Нью-Йорк. В этом случае прибыль составит 8700 долларов.3ЗаключениеВ данной работе рассмотрена задача о ранце. Описаны классическая постановка задачи и основные варианты этой задачи.Приведены методы решения задач о ранце и их классификация.В общем виде рассмотрен метод ветвей и границ, а также стратегии данного метода в решении задач.Рассмотрены примеры решения трех разных вариантов задач о ранце. Задача о ранце очень важна с точки зрения ее применения в реальной жизни.Несмотря на свой «возраст», ранец не только не забывается, наоборот, интерес к этой задаче только растет. Оптимальная загрузка транспорта (как в задаче №3) помогает сокращать расходы и получать большую прибыль. Также эта задача и её различные модификации широко применяются на практике в криптографии, прикладной математике, экономике, логистике, для нахождения решения оптимальной загрузки различных транспортных средств: кораблей, самолетов, железнодорожных вагонов и т.д.Список литературыОкулов С.М. Информатика в задачах [Текст] / С.М. Окулов, А.А, Пестов, О.А. Пестов. - Киров: Изд-во ВГПУ, 1998. -- 343с.Кузюрин Н.Н Сложность комбинаторных алгоритмов. Курс лекций [Текст] / Н.Н. Кузюрин, С.А.Фомин. – 2005. – 79 с.Вирт Н. Алгоритмы и структуры данных [Текст] / Н. Вирт. – Пер. с англ.-М.Мир, 1989.-360 с., ил.https://studfile.net/preview/5566699/Визгунов Н.П. Динамическое программирование в экономических задачах с применением системы MATLAB [Текст] / Н.П. Визгунов. – Н.Новгород.: ННГУ, 2006. – 48 с.https://studopedia.ru/19_343030_metod-vetvey-i-granits-reshenie-zadachi-o-ryukzake-metodom-vetvey-i-granits.htmlМетодическое пособие по курсу "Математические основы информатики" для студентов факультета ВМК, специальность "Прикладная информатика"