Занятие 4 Тема: Решение задач линейного программирования (злп) средствами Excel

4.1. Задачи на составление оптимальных смесей

0. Под смесью понимается совокупность нескольких разнородных составляющих (ингредиентов), при объединении обладающую особым свойством. С этой точки зрения в качестве смесей можно рассматривать как совокупность физических ингредиентов (питательные, горюче-смазочные, химические смеси), так и совокупность составляющих абстрактного типа (портфель ценных бумаг, набор депозитов). Как правило, состав смесей подлежит оптимизации с целью эффективного их изготовления и использования. При этом нужно выдержать определенные требования по количественному и качественному составу смесей. Эти требования обычно выписываются как требования к %-му содержанию определенных компонент смеси относительно общего веса, объема и т.д.

Словесная формулировка. Имеется n ингредиентов, из которых изготовляется смесь. Содержание каждой из m компонент смеси в единице каждого ингредиента известно. Цены ингредиентов заданы. Требуется определить количества каждого из ингредиентов, при которых полученная смесь имела бы минимальную стоимость, и в то же время отвечала бы требованиям по качеству, выраженных в заданных минимальном и максимальном %-м содержании компонент; кроме того, общий вес (объем) смеси должен быть не меньше некоторого заданного уровня.

Формальная постановка. Пусть x_j – искомое количество j-го ингредиента, с_j – его цена, а_ij – содержание i-й компоненты в единице j-го ингредиента, u_k и d_k – соответственно верхняя и нижняя границы содержания k-й компоненты в смеси, заданные в процентных долях, р – минимальное количество смеси. Тогда задача минимизации стоимости смеси при удовлетворительном ее качестве принимает вид:

(1)

(2)

Полученная задача (1)-(2) может быть представлена в классической форме записи ЗЛП, для чего необходимо просто привести подобные в ограничениях. В результате получим эквивалентную задачу

(3)

(4)

Задачи (1)-(2) и (3)-(4) эквивалентны. Вместе с тем у каждой из этих постановок есть свои преимущества и недостатки.

Основным достоинством постановки (1)-(2) является то, что изменения табличных данных, отражающих состав компонент в ингредиентах смеси не требуют никакой предварительной переработки. Табличные данные в явном виде присутствуют в (2). Поэтому постановка (1)-(2) как бы «ближе» к исходным данным и позволяет более просто подходить к моделированию различных возможных ситуаций. Особенно просто и наглядно решение задачи в этой постановке на Excel, которое можно назвать «решением с листа». Недостатком постановки (1)-(2) является то, что она не является классической постановкой задачи линейного программирования и поэтому требует переработки в задачу (3)-(4) при использовании отличных от Excel программных средств.

Основным достоинством постановки (3)-(4) является то, что она готова к решению с помощью любой стандартной компьютерной программы, предназначенной для решения задач линейного программирования. Недостатком постановки (3)-(4) является ее некоторая оторванность от исходных данных, поскольку коэффициенты при неизвестных в ограничениях (4) придется пересчитывать всякий раз, когда качество исходных ингредиентов меняется.

Ниже приведены примеры так называемых задач о диете, имеющих дело с оптимизацией питательных смесей.

Пример 1. На ферме растут 20000 цыплят, которые после достижения 8-недельного возраста и соответствующей обработки поступают в продажу. Расход корма, представляющего собой смесь известняка, зерна и бобов, составляет не менее 8 кг на одного цыпленка за весь откормочный период. Требования к качеству корма выражаются условиями, выраженными в процентах. Кормовая смесь должна содержать (по весу):

1) не менее 0,8%, но не более 1,2% кальция; 2) не менее 22% белка; 3) не более 5% клетчатки.

Содержание данных химических веществ в 1кг ингредиента приведено в таблице:

Ингредиент	Содержание химических веществ, кг/(кг ингредиента)			Стоимость, долл./кг
	кальций	белок	клетчатка
Известняк	0,38	0	0	0,04
Зерно	0,001	0,09	0,02	0,15
Соевые бобы	0,002	0,50	0,08	0,40

Требуется определить количество (в кг) каждого ингредиента, образующих смесь минимальной стоимости при соблюдении требований к общему расходу кормовой смеси и ее качеству.

Решение «с листа». Введем обозначения: – содержание известняка, – содержание зерна, – содержание соевых бобов в кормовой смеси. Стоимость всего корма, таким образом, выразится целевой функцией .

Теперь задача получения минимальной стоимости кормовой смеси сводится к задаче минимизации целевой функции при ограничениях, исходящими из требований по общему весу и качеству корма. В соответствии с введенными обозначениями имеем:

На каждого из 20000 цыплят нужно не менее 8 кг корма. Отсюда вытекает следующее ограничение по весу:

.

Из табличных данных имеем:

кальция в смеси: ; белка в смеси: ; клетчатки в смеси: .

Кормовая смесь должна содержать не менее 0,8%, но не более 1,2% кальция, следовательно,

,

.

Кормовая смесь должна содержать не менее 22% белка, следовательно,

.

Поскольку по условию кормовая смесь должна содержать не более 5% клетчатки, то

.

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

; (5)

(6)

Полученная задача (5)-(6) соответствует постановке (1)-(2) и может быть решена «с листа» (рис. 1):

Рис. 1. Шаблон с решением задачи примера 1 «с листа»

Решение в классической форме. Приводя подобные в каждом неравенстве из (6), получаем классическую задачу линейного программирования:

; (7)

(8)

Полученная задача (7)-(8) соответствует классической постановке ЗЛП (3)-(4) и также может быть решена на Excel:

Рис. 2. Шаблон с решением задачи примера 1 в классической постановке (7)-(8)

Пример 2. Человеку ежедневно необходимо потреблять не менее 118 г белков, 56 г жиров, 500 г углеводов, 8 г минеральных солей. Количество питательных веществ, содержащихся в 1 кг каждого вида потребляемых продуктов, а также цены продуктов приведены в следующей таблице

Питательные вещества	Содержание (г) питательных веществ в 1 кг продуктов
	мясо	рыба	молоко	масло	сыр	гречка	картофель
Белки	180	190	30	10	260	130	21
Жиры	20	3	40	865	310	30	2
Углеводы	-	-	50	6	20	650	200
Мин. соли	9	10	7	12	60	20	10
Цена (руб/кг)	105	60	18	156	186	51	15

Состав «корзины» указанных продуктов считается качественным, если выполняются следующие требования: 1) белков в «корзине» не менее 10% и не более 40% от общего веса; 2) жиров не менее 10% и не более 30% от общего веса; 3) углеводов не менее 25% и не более 50% от общего веса; 4) общий вес всего рациона не должен превышать 1,2 кг, а содержание минеральных солей не должно превышать 18 г.

Решение. Действуя по аналогии с решением примера 1, получаем следующий шаблон, соответствующий «решению с листа»:

Рис. 3. Шаблон с решением задачи примера 2 «с листа»

Ответ: оптимальный состав корзины продуктов (в кг) и ее стоимость (руб) приведены в таблице:

мясо	рыба	молоко	масло	сыр	гречка	картофель	Стоимость
0	0,084	0,067	0,086	0	0,763	0	58,53