Задача о ранце решение в excel
Условие 0-1 knapsack problem:
Из множества предметов со свойствами «стоимость» и «вес», отобрать некоторое их число таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.
Динамическое программирование. Что меня поразило в этом алгоритме
Ведь задан вес - Р.
Кажется, кратчайшее решение - это рассматривать наборы только этого веса.
Число сочетаний С из n по m возрастает с увеличением m [от 1 до n/2], а затем будет убывать.
Так зачем рассматривать промежуточные наборы и тратить время.
Отсортировать предметы по убыванию «стоимости» и перебирать в цикле, проверяя условие: вес ячейки одной строки) и увеличивая количество предметов от 1 до n (внешний цикл > увеличение номера строки) становится возможной автоматическая оптимизация.
Делая выбор для очередной ячейки, выбирается максимум из двух вариантов:
Первый вариант: ячейка в этой же колонке, но на строку выше (т.е. просто, не брать этот предмет в ранец, т.к. предыдущий набор предметов для данного веса «ценнее»).
Второй вариант: стоимость предмета + ячейка, которая на строку выше и левее на величину веса предмета (т.е. берем предмет, но выбрасываем из ранца другие предметы на величину его веса).
А как красиво заполняется таблица Иногда, оказывается, следует выбрасывать предметы с большей удельной стоимостью, чтобы достичь максимальной загрузки ранца и от этого получить максимум стоимости в результат.
И даже сортировка излишня. Без нее результат абсолютно тот же. Предмет с большим удельным весом всегда будет размещаться алгоритмом (в строке таблицы) левее, чем остальные.
Экспериментируйте. Все наглядно.
В желтых ячейках можно задать параметры.
Кнопки Random, Sort, Massiv запускают определенные макросы.
Пример решений задачи на VBA Excel 2007 и выше
А это Задача о ранце (рюкзаке) на VBA Excel 2010.
Рис.1 Пример решений задачи на VBA Excel
Так может выглядеть главная форма.
Пример решений задачи на C++ Visual Studio 2012
Так может выглядеть главная форма.
Рис.3 Пример решений задачи на C++ Visual Studio 2012
Замена фото (файл the_foto.jpg) на форме AboutForm - вопрос на любителя… Можно форму «О разработчике» удалить, если не требуется.
Пример решений задачи на Delphi 7, XE
Рис.5 Пример решений задачи на Delphi 7, XE
Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку .
Если на этой странице не нашлось того, что Вы так искали.
460040, г.Оренбург ©2010 Учебные программы и сайты для студентов
В общем виде задача о рюкзаке формулируется следующим способом: имеется рюкзак определенного объема и неограниченное количество предметов. Для каждого предмета известен его объем (вес) и ценность (стоимость, эффективность). В рюкзак можно положить целое число предметов различного типа. Цель состоит в том, чтобы суммарная ценность всех находящихся в рюкзаке предметов была максимальна, а их объем (вес) не превышал заданной величины. К подобной формулировке может быть сведена задача максимального использования грузоподъемности подвижного состава, грузовместимости судна, автомобиля и т.п. Такая задача часто возникает при выборе оптимального управления в экономико-финансовых областях (например распределение бюджета отдела по проектам).
Решение задачи в классической постановке
Подобные задачи легко решаются с помощью надстройки "Поиск решения". Подготовлены исходные данные (рисунок ниже). Задача состоит в том, чтобы за счет подбора значений ячеек B16:B19 добиться максимального значения целевой функции (значение ячейки D20).
На первом рисунке ниже показаны ограничения на значения изменяемых ячеек. На втором рисунке ниже приводится результат расчета. Во многих практических случаях данная постановка задачи является слишком упрощенной. Далее будут рассмотрены варианты усложнения постановки задачи.
Модифицированная задача
Одним из дополнительных ограничений, возникающих при практическом использовании данной задачи, могут быть ограничения на необходимое количество предметов определенных видов, которые можно положить в рюкзак. При этом могут возникать варианты задачи, когда требуется строго определенное количество предметов или требуется не менее (не более) заданного количества предметов.
На рисунке ниже показаны исходные данные модифицированного варианта задачи. В этом случае предполагается, что в рюкзак может быть положено не менее некоторого количества предметов.
На следующем рисунке показаны ограничения на значения изменяемых ячеек B16:B19. В данном случае к ограничениям добавлено условие 16:19>=8:11, то есть задано минимальное необходимое количество предметов различных видов.
Решение задачи представлено последнем рисунке.
При необходимости дополнительное условие 16:19>=8:11 может быть изменено. Например, можно установить отдельные ограничения для всех предметов, назначив для некоторых из них точное количество предметов, в то время как для других — условие «не менее» или «не более»
Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .
Задача
Предприятие выпускает продукт (только один вид изделия и ничего более) и ему необходимо выполнить заказ клиента. На предприятии 3 типа оборудования. Все типы оборудования выпускают один и тот же продукт. Производительность каждого типа оборудования разная. Каждый тип оборудования имеет постоянную и переменную часть расходов. Переменная часть расходов пропорциональна количеству произведенных изделий. Имеется ограниченное количество единиц оборудования каждого типа (но общее количество оборудования избыточно для выполнения заказа). Требуется минимизировать расходы на оборудование при условии выполнения заказа.
Создание модели
На рисунке ниже приведена модель, созданная для решения задачи (см. файл примера ).
Предприятие несет расходы в зависимости от типа оборудования: использование оборудования типа Alpha-3000 самое дорогое в эксплуатации, но оно и самое производительное. Оборудование типа Alpha-1000 самое дешевое в эксплуатации, но оно и менее производительное. Задача Поиска решения выбрать наиболее дешевое оборудование, так чтобы заказ был выполнен (мощностей Alpha-1000 не хватит для выполнения заказа). Казалось бы, решение очевидно (взять по максимуму дешевое оборудование, остальную производительность обеспечить более дорогим). Однако, если учесть, что из-за низкой производительности дешевых машин приходится их брать больше, неся существенные постоянные расходы, то решение уже не кажется очевидным.
Переменные (выделено зеленым) . В качестве переменных модели следует взять количество задействованных единиц оборудования каждого типа и суммарное количество продукции, выпущенное на каждом типе оборудования (производительность задается не для каждой единицы, а для типа в целом). Переменные выделены зеленым. Для наглядности диапазонам ячеек, содержащих переменные, присвоены имена Машин_Задействовано и Продукции_выпущено.
Ограничения (выделено синим) . Количество задействованных машин должно быть целым числом. Количество задействованных машин каждого типа должно быть не больше, чем имеется в наличии. Всего должно быть выпущено продукции не меньше чем величина заказа. Также необходимо ограничить производительность задействованного оборудования. Производительность задается не для каждой единицы, а для типа в целом. Максимальная производительность задействованного оборудования рассчитывается формулой массива = Машин_Задействовано* Макс_производительность Макс_производительность – это именованный диапазон . Ограничения выделены синим цветом.
Целевая функция (выделено красным) . Целевая функция задается формулой = СУММПРОИЗВ(Продукции_выпущено_По_типу; Расходы_переменные)+ СУММПРОИЗВ(Машин_Задействовано; Расходы_постоянные) Это просто суммарные операционные расходы (переменная и постоянные части). Результат вычисления этой формулы должен быть минимизирован (выделено красным).
Убедитесь, что метод решения соответствует линейной задаче. Теперь в диалоговом окне можно нажать кнопку Найти решение .
Результаты расчетов
Поиск решения найдет оптимальный набор единиц оборудования по типам и их производительность, при котором операционные расходы будут минимальные, а заказ выполнен. Обратите внимание, что значение переменных (количество продукции, выпущенное на каждом типе оборудования) – целые числа, хотя в ограничениях этого прописано не было. Изменив значения максимальной производительности с 40 на, например, 40,3 (ячейка D 7 ) и пересчитав еще раз, получим нецелые значения выпущенной продукции. Т.е. Поиск решения сам «догадался», что нам требуются целые значения переменной, т.к. в качестве ограничения были указаны значения без дробной части. Двигаемся дальше. В условии задачи предполагается, что выпуск продукции осуществляется лишь в течение одного периода. В статье Поиск решения MS EXCEL (1.3). Распределение ресурсов (ограничение по количеству оборудования, несколько периодов) решим задачу определения наилучшего распределения ресурсов в случае нескольких периодов.
Создадим модель для нахождения наилучшего распределения ресурсов, при котором минимизируются затраты, понесенные за несколько периодов (Allocation Problem). Расчет будем проводить с помощью надстройки Поиск решения.
Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .
Задача
Предприятие выпускает монопродукт (только один вид изделия и ничего более) и ему необходимо выполнить заказ клиента. Выпуск продукции осуществляется в течение 5 дней. Отгрузка заказа ежедневная. На предприятии 3 типа оборудования. Каждый тип оборудования выпускает один и тот же продукт. Производительность каждого типа оборудования разная. Каждый тип оборудования имеет постоянную и переменную часть расходов. Переменная часть расходов пропорциональна количеству произведенных изделий. Имеется ограниченное количество единиц оборудования каждого типа (но общее количество оборудования избыточно для выполнения заказа). Требуется минимизировать расходы на оборудование при условии выполнения заказа.
Создание модели
На рисунке ниже приведена модель, созданная для решения задачи (см. файл примера ).
Предприятие несет расходы в зависимости от типа оборудования: использование оборудования типа Alpha-3000 самое дорогое в эксплуатации, но оно и самое производительное. Оборудование типа Alpha-1000 самое дешевое в эксплуатации, но оно и менее производительное. Задача Поиска решения выбрать наиболее дешевое оборудование, так чтобы заказ был выполнен (мощностей Alpha-1000 не хватит для выполнения заказа). Казалось бы, решение очевидно (взять по максимуму дешевое оборудование, остальную производительность обеспечить более дорогим). Однако, если учесть, что из-за низкой производительности дешевых машин приходится их брать больше, неся существенные постоянные расходы, то решение уже не кажется очевидным.
Переменные (выделено зеленым) . В качестве переменных модели следует взять количество задействованных единиц оборудования каждого типа и суммарное количество продукции, выпущенное на каждом типе оборудования (производительность задается не для каждой единицы, а для типа в целом). Для наглядности диапазонам ячеек, содержащих переменные, присвоены имена Машин_Задействовано и Продукции_выпущено.
Ограничения (выделено синим) . Количество задействованных машин должно быть целым числом. Количество задействованных машин каждого типа должно быть не больше, чем имеется в наличии (используются именованные диапазоны Alpha XXXX _Задействовано и Alpha XXXX _в_наличии ). Всего должно быть выпущено продукции не меньше чем величина заказа (используется именованный диапазон Продукции выпущено_Итого ). В день возможно производить больше продукции, чем требуется в день заказа, излишек переносится на следующий день. Также необходимо ограничить производительность задействованного оборудования. Производительность задается не для каждой единицы, а для типа в целом (используются именованные диапазоны Продукции выпущено и Макс_производительность_задейств_машин ).
Целевая функция (выделено красным) . Целевая функция – это сумма операционных расходов за 5 дней. Операционные расходы, понесенные за день, задается формулой =СУММПРОИЗВ(B19:B21; Расходы_переменные)+ СУММПРОИЗВ(B13:B15; Расходы_постоянные) B19:B21 – количество продукции, выпущенной в определенный день. B13:B15 - количество задействованных машин в определенный день.
Это суммарные операционные расходы (переменная и постоянные части). Сумма операционных расходов за 5 дней должна быть минимизирована.
Убедитесь, что метод решения соответствует линейной задаче. Параметры Поиска решения были выбраны следующие:
Теперь в диалоговом окне можно нажать кнопку Найти решение .
Результаты расчетов
Поиск решения подберет оптимальный набор единиц оборудования по типам и их производительность, при котором операционные расходы будут минимальные, а заказ выполнен. В нашей задаче было установлено целочисленное ограничение, что существенно усложняет задачу поиска и, соответственно, сказывается на скорости расчета. Как показано на рисунке выше, Целочисленная оптимальность была выбрана 0% ( Целочисленная оптимальность (Integer Optimality) позволяет Поиску решения остановить поиск, в случае, если он найдет целочисленное решение, в пределах указанного процента от оптимального). В нашем случае (0%), требуется найти лучшее из известных Поиску решения решений. Поиск в этом случае занял 8 секунд, результат 23 311,50. Установив Целочисленную оптимальность 1%, поиск займет 0,2 сек, результат 23 370,50 (отличие на 0,3%). Это информация к размышлению: стоит ли увеличение точности на 0,3% уменьшения скорости расчетов более чем на порядок? Решать Вам. В любом случае, первые расчеты модели лучше проводить при Целочисленной оптимальности не равной 0%.
= Мир MS Excel/Задача о рюкзаке - Мир MS Excel
Войти через uID
Войти через uID
В продолжении темы "Подбор слагаемых под нужную сумму" (сумма подмножеств)
Предлагаю решение "Задачи о рюкзаке"
Во вложении два алгоритма:
Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость.
Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.
В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.
UPD 13/08/2015
Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро
В продолжении темы "Подбор слагаемых под нужную сумму" (сумма подмножеств)
Предлагаю решение "Задачи о рюкзаке"
Во вложении два алгоритма:
Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость.
Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.
В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.
UPD 13/08/2015
Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро MCH
Во вложении два алгоритма:
Первый подбирает предметы суммарным весом не более необходимого, имеющие максимальную стоимость.
Второй подбирает перечень предметов суммарным весом и стоимостью в определенном диапазоне от минимального до максимального.
В основе решения динамическое программирование, отсюда ограничения - работа с целыми числами, и существенное увеличение времени решения и количество выделяемой памяти от размеров рюкзака.
UPD 13/08/2015
Добавил решение классической "задачи о рюкзаке" жадным алгоритмом
Не всегда находит наилучшее решение, но работает достаточно быстро Автор - MCH
Дата добавления - 12.08.2015 в 20:40
Читайте также: