Проблема дієти

кожного продукту

Однією з перших проблем оптимізації, вивчених протягом 30-х років, була так звана проблема дієти, яка полягає у досягненні збалансованого харчування за мінімально можливих витрат.

Більш конкретно, людина повинна вживати певну мінімальну кількість ряду основних елементів харчування, які містяться в різних продуктах харчування. Знаючи, яка кількість кожного елемента в кожній одиниці кожного з продуктів і вартість одиниці кожного продукту, мова йде про мінімізацію витрат на дієту, але покриття мінімальних харчових потреб.

Одним із перших, хто вирішив цю проблему, був Жорж Дж. Штіглер, який за допомогою евристичного методу отримав оптимальне рішення при річній вартості 39,93 доларів США за цінами 1939 року.

Через роки, у 1947 році, Джек Ландерман вирішив проблему, використовуючи симплексний метод, працюючи з 9 обмеженнями і 77 невідомими. Його рішення, отримане за допомогою настільних калькуляторів, що використовувались протягом 120 робочих днів, коштувало 39,69 доларів на людину на рік. Тобто евристичне рішення Штіглера відрізнялося від реального лише на 24 центи.

Сьогодні можна вирішити цю проблему набагато швидше, про що ви можете переконатися самі на сторінці:

Приклад проблеми дієти

Припустимо, що мінімальні щотижневі потреби людини у білках, вуглеводах та жирах - це ті, що вказані в наступній таблиці:

На ринку є два товари ДО Y B вміст та витрати на кілограм:

Скільки кілограмів кожного продукту ми повинні споживати щотижня, щоб вартість нашої дієти була мінімальною?

Проблема транспортування

У цьому випадку пропонується оптимальний розподіл серії товарів між різними центрами виробництва та споживання. Іншими словами, певний товар виготовляється в декількох центрах і повинен бути відправлений у різні пункти призначення. Знаючи вартість транспорту між кожним виробничим центром і кожним центром споживання, кількість, отриману в кожному виробничому центрі, і кількість, необхідну в кожному центрі споживання, загальну вартість транспорту слід мінімізувати.

Голландський Купманс, піднятий під час Другої світової війни, план вантажних перевезень між різними портами. У своїй статті "Коефіцієнти обміну між зарядами на різних маршрутах", опублікованій у 1942 році, він описує проблему за допомогою графіка (мережі), вершинами якого є порти, а дуги якого пов'язані з тоннажем, зафрахтованим між кожною парою портів.

У 1958 р. Методи Лінійного програмування були застосовані до конкретної проблеми: розрахунку оптимального плану транспортування будівельного піску до будівельних майданчиків міста Москви. У цій задачі було 10 початкових та 230 кінцевих точок. Оптимальний транспортний план, розрахований за допомогою комп’ютера Strena на 10 днів червня, зменшив витрати на 11% порівняно з очікуваними витратами.

Приклад транспортної проблеми

Компанія має два заводи ДО Y B, в якому вона виробляє певний товар із розрахунку 500 та 400 одиниць на день відповідно. Виготовлений продукт повинен згодом розподілятися у три пакувальні центри, що називаються Я, II Y III. Кожен із цих центрів повинен отримувати 200, 300 та 400 одиниць щодня відповідно.

У наступній таблиці наведено транспортні витрати між фабриками та пакувальними центрами.