Задача о диете, задача о ранце. Постановка, модель, методы решения

52. Задача о диете, задача о ранце. Постановка, модель, методы решения.

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

1.  Постановка задачи

Турист собирается в поход и наполняет свой ранец N предметами и известен вес каждого предмета (W_j) и известна эффективность каждого предмета (E_j)

W – емкость каждого предмета (максимальный вес)

Сколько предметов каждого вида должен полоижить турист, чтобы эффективность была максимальной

2.  Модель

x_j – количество предметов j-го вида

1 вариант

2 вариант

3.  Методы решения

·  Метод Гомори

·  Метод ветвей и границ

Задача о диете

1.  Постановка

В диету может быть включено n продуктов, каждый из который содержит m веществ, известно содержание i-го вещества в единице j-го продукта

b_i –минимально необходимое содержание i-го вещества в рационе

c_j – цена единицы j-го продукта

Составить рацион с минимальными затратами.

x_j – количество j-го продукта в рационе

2.  Модель