Задача составления смесей

Несмотря на то что оба рассмотренных примера оказались моделями максимизации, многие реальные задачи сводятся к задачам минимизации. Когда целью является прибыль, ее необходимо максимизировать, но если цель — уменьшить затраты, то приходим к задаче минимизации. В качестве модели ми­нимизации рассмотрим следующий пример.

При создании сплава для новой продукции компании Eastern Steel используется же­лезная руда, получаемая с четырех различных шахт. Как показал анализ, чтобы получить сплав с нужными свойствами, необходимо удовлетворить минимальные требования по трем основным элементам, которые для простоты обозначили А, В и С. В частности, ка­ждая тонна руды должна содержать не менее 5 фунтов элемента А, 100 фунтов элемента В и 30 фунтов элемента С. Эти данные приведены в табл. 6.

Таблица 6. Требования к содержанию основных элементов

Элемент	Минимальное содержание, фунт/т
А	5
В	100
С	30

Руда с каждой шахты содержит все три основных элемента, но в разных количествах.

Состав руды (содержание элементов) приведен в табл. 7.

Таблица 7. Состав руды с различных шахт

Шахта (содержание элементов, фунт/т)
Элемент	1	2	3	4
А	10	3	8	2
в	90	150	75	175
С	45	25	20	37

Заметим, что тонна руды с первой шахты содержит 10 фунтов элемента А и, следова­тельно, удовлетворяет минимальному требованию к содержанию данного элемента (5 фунтов в тонне). Кроме того, она содержит 90 фунтов элемента В и 45 фунтов элемен­та С, таким образом требование к содержанию элемента С удовлетворяется, а к содержа­нию элемента В — нет. Аналогично тонна руды со второй шахты не удовлетворяет требо­ваниям к содержанию элементов А и С, тонна руды с третьей шахты— требованиям к содержанию В и С, а с четвертой — требованию к содержанию А. Однако можно соста­вить разнообразные смеси (в которых в различных пропорциях будут смешиваться руды с разных шахт), удовлетворяющие минимальным требованиям по всем основным эле­ментам. Пример такой смеси: 1/2 тонны руды с шахты 1 и 1/2 тонны руды с шахты 4. Со­держание элемента А в тонне такой смеси вычисляется по формуле:

содержание А = (1/2) х (содержание А в тонне руды с шахты 1) +

+ (1/2) х (содержание А в тонне руды с шахты 4).

Таким образом, содержание элемента А = (1/2)х10 + (1/2)х2 = 5+1=6.

Поскольку 6 ≥ 5, требование по минимальному содержанию элемента А удовлетворено.

Аналогично можно рассчитать содержание элемента В в тонне смеси:

содержание В = (1/2) х (содержание В в тонне руды с шахты 1) + (1/2) х

х (содержание В в тонне руды с шахты 4).

Следовательно, содержание элемента В = (1/2)х90 + (1/2)х175 = 132,5. Наконец, содер­жание элемента С в тонне смеси равно (1/2)х45 + (1/2)х37 = 41.

Сравнивая полученные значения с требуемым содержанием В (100 фунтов) и С (30 фунтов), видим, что данная смесь (1/2 тонны с шахты 1 и 1/2 тонны с шахты 4) удов­летворяет всем требованиям по минимальному содержанию элементов, следовательно, она является допустимой смесью. Существует много других смесей, которые также удов­летворяют всем требованиям и являются допустимыми. Однако, поскольку руда с разных шахт имеет различную стоимость, стоимость смесей также различается. Стоимостные данные содержатся в табл. 8.

Таблица 8. Стоимость руды с различных шахт

Шахта	Стоимость тонны руды, $
1 2 3 4	800 400 600 500

Например, стоимость допустимой смеси, тонна которой состоит из половины тонны руды с шахты 1 и половины тонны руды с шахты 4, вычисляется по формуле:

(1/2)х(стоимость тонны руды шахты 1) + (1/2)х(стоимость тонны руды шахты 4) =

= (1/2)х800 + (1/2)х500 = $650.

Можно попробовать сравнить эту стоимость со стоимостью других допустимых сме­сей. Цель компании Eastern Steel — найти самую дешевую допустимую смесь. Сформули­руем данную задачу в виде модели линейного программирования.

Поскольку нужно найти оптимальный состав одной тонны смеси, зададим перемен­ные решения следующим образом:

Т₁ — часть тонны, состоящая из руды с шахты 1,

Т₂ — часть тонны, состоящая из руды с шахты 2,

Т₃ — часть тонны, состоящая из руды с шахты 3,

Т₄ — часть тонны, состоящая из руды с шахты 4.

С помощью данных табл. 6 вычислим количества основных элементов в одной тон­не смеси:

(9), (10), (11).

Теперь скомбинируем выражения (9), (10), (11) с требованиями по минималь­ному содержанию элементов, приведенными в табл. 6, и получим три ограничения.

(12), (13), (14).

Существуют ли в данной модели другие ограничения? Необходимо включить условия неотрицательности переменных решения Т1,, Т2, Т3, Т4, однако есть еще одно важное ог­раничение. Поскольку тонна смеси состоит только из руды указанных четырех шахт, сумма составляющих смеси должна быть равна 1:

(15).

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

Ограничения модели линейного программирования могут быть как равенствами, так и неравенствами.

Используя данные табл. 7, легко получить формулу для вычисления стоимости тон­ны любой смеси:

стоимость 1 т смеси = 800Т₁, + 400 Т₂ + 600 Т₃ + 500 Т₄.

Теперь можем составить полную символическую модель.

Минимизировать 800Т₁, + 400Т₂ + 600Т₃ + 500Т₄;

при ограничениях

Все функции модели являются линейными, следовательно, это модель линейного программирования.

На этом закончим с формализацией моделей ЛП, предназначенных для последую­щего применения средства Поиск решения. Вернемся к основной теме книги, т.е. созда­нию моделей, которые могут помочь при принятии решений. Однако прежде чем перехо­дить к следующему разделу, рекомендуем читателям проверить свои возможности по соз­данию моделей на базе электронных таблиц и применению средства Поиск решения на основе модели составления рудной смеси для компании Eastern Steel. Реализуйте ее в ви­де табличной модели в Excel, придерживаясь предложенных в данной главе рекоменда­ций. Затем оптимизируйте полученную модель с помощью средства Поиск решения.