Задача о ранце

Рис.. Основные этапы решения задачи о раскрое материалов средствами MS Excel

Выполнив оптимизацию средствами MS Excel получим оптимальное решение рассматриваемой задачи о смеси:

х₁ = 571,429; х₂ = 0; х ₃= 142,857; х₄ =285,714; min f(X) = 57143.

(оптимальные значения остальных переменных равны нулю).

Таким образом, предлагаются следующие рекомендации по производству смеси:

- для производства смеси компонент №1 берется в количестве 571,429т;

- компонент №3 берется в количестве 142,857т;

- компонент №4 берется в количестве 285,714т.

При таком смешении ожидаются минимальные затраты на производство смеси равные 57143(ден.ед.).

Приведем два примера задач дискретной оптимизации: задачу о ранце (обычные условия дискретности – физическая неделимость объектов) и задачу об инвестициях (особые условия дискретности – вариантность выбора).

Задача о ранце

В терминах задачи о ранце (рюкзаке) формулируются многие задачи загрузки в некоторую емкость тех или иных предметов.

Постановка задачи. Организация арендует баржу грузоподъемностью 83т, на которой предполагает перевозить груз, состоящий из предметов четырех типов. Веса и стоимости предметов равны, соответственно, 24т, 22т, 16т, 10т и 96у.е., 85у.е., 50у.е., 20у.е. Требуется погрузить на баржу груз максимальной стоимости.

Экономико-математическая модель. Введем необходимые обозначения, пусть x_j (j=1,2,3,4) – число предметов j-го типа, которое следует погрузить на баржу. Т.о. формально план погрузки представляется вектором Х=(х₁,х₂,х₃,х₄).Тогда математическая модель задачи о подборе для баржи допустимого груза максимальной ценности запишется следующим образом:

max f (x_1,x_2, x_3, x₄) = 96x₁ + 85x₂ + 50x₃ +20x₄

24x₁ + 22x₂ +16x₃ +10x₄ £ 83,

x_j (j=1,2,3,4) – целые неотрицательные.

Получение решения. Приведенная ЭММ является моделью задачи целочисленного линейного программирования (ЦЛП). Для реализации этой модели средствами Excel в диалоговом окне режима Поиска решения с помощью кнопки Добавить следует ввести ограничение целочисленности переменных (целые числа в изменяемых ячейках).

Специализированный (рабочий) лист может быть подготовлен в виде, представленном на рис. 4. Формулы этого листа очевидны.

Диалоговое окно, отвечающее приведенному выше рабочему листу, также показано на рис.4.

Рис. 4. Начальная рабочая таблица и диалоговое окно

Результаты реализации разработанной ЭММ задачи о ранце приведены ниже (рис.5).

Рис.5. Результаты решения.

Таким образом, рекомендуемое управленческое решение с позиций принятого критерия оптимальности – следует погрузить три предмета первого типа и один предмет четвертого типа. В этом случае стоимость груза составит 308 у.е. и одна тонна грузоподъемности будет не использована (ее можно использовать на другие цели).

Приведем пример задачи дискретного программирования с особыми условиями дискретности – булевостью переменных.

Дата добавления: 2015-07-16