Решение задач распределения

Рассмотрим примеры задач распределения.

Пример 7.1. Планирование производства материалов

Фирма выпускает два вида строительных материалов: А и В. Продукция обоих видов поступает в продажу. Для производства материалов используются два исходных продукта: I и II. Максимально возможные суточные запасы этих продуктов составляют 7 и 9 тонн соответственно. Расходы продуктов I и II на одну тонну соответствующих материалов приведены в табл. 7.1.

Изучение рынка сбыта показало, что суточный спрос на материал В никогда не превышает спроса на материал А более чем на 1 т. Кроме того, спрос на материал А никогда не превышает 3 т в сутки. Оптовые цены одной тонны материалов равны: 4000 у.е. для В и 3000 у.е. для А. Какое количество материала каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?

 

Таблица 7.1 - Расход продуктов

Исходный продукт	Расход исходных продуктов, т (на одну тонну материалов)	Максимально возможный запас, т
Материал А	Материал В
I
II

 

1. Формулировка математической модели задачи:

1) переменные для решения задачи: x₁ – суточный объем производства материала А, x₂ – суточный объем производства материала В;

2) определение функции цели (критерия оптимизации): суммарная суточная прибыль от производства x₁ материала А и x₂ материала В:

F = 4000x₂ + 3000x₁,

поэтому цель фабрики – среди всех допустимых значений x₂ и x₁ найти такие, которые максимизируют суммарную прибыль от производства материалов F:

F = 4000x₂ + 3000x₁ → max;

3) ограничения на переменные:

а) объем производства красок не может быть отрицательным, т.е.

x₂ ≥ 0, x₁ ≥ 0;

б) расход исходного продукта для производства обоих видов материалов не может превосходить максимально возможного запаса данного исходного продукта, т. е.:

2x₂ + 3x₁ ≤ 7,

3x₂ + 2x₁ ≤ 9

ограничения на величину спроса на материалы:

x₁ - x₂ ≤ 1,

x₁ ≤ 3.

Таким образом, получаем математическую модель задачи:

- найти максимум следующей функции:

- F = 4000x₂+3000x₁ →max

- при ограничениях вида:

2x₂ + 3x₁ ≤ 7,

3x₂ + 2x₁ ≤ 9,

x₁ - x₂ ≤ 1,

x₁ ≤ 3,

x₁ ≥ 0, x₂ ≥ 0.

2. Подготовка листа рабочей книги MS Excel для вычислений: на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7.2. Переменные задачи x₁ и x₂ находятся в ячейках С3 и С4 соответственно. Целевая функция находится в ячейке С6 и содержит формулу:

= 4000*С4 + 3000*С3.

Ограничения на задачу учтены в ячейках С8:D11.

 

Рис. 7.2. Рабочий лист MS Excel для решения задачи планирования производства материалов

 

3. Работа с надстройкой Поиск решения: воспользовавшись командой Сервис – Поиск решения, вводим необходимые данные для рассматриваемой задачи (установка данных в окне Поиск решения приведена на рис. 7.3). Результат работы по поиску решения помещен на рис. 7.4–7.7.

 

 

Рис. 7.3. Установка необходимых параметров задачи планирования материалов

в окне Поиск решения

Рис. 7.4. Результат надстройки Поиск решения

Отчет по результатам (рис. 7.5): таблица Целевая ячейка выводит сведения о целевой функции; таблица Изменяемые ячейки показывает значения искомых переменных, полученных в результате решения задачи; таблица Ограничения отображает результаты оптимального решения для ограничений и для граничных условий. В поле Формула приведены зависимости, которые были введены в окно Поиск решения, в поле Разница – величины использованного материала. Если материал используется полностью, то в поле Статус указывается связанное, при неполном использовании материала в этом поле указывается не связан. Для граничных условий приводятся аналогичные величины в той лишь разницей, что вместо величины неиспользованного продукта показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

Рис. 7.5. Отчет по результатам поиска решения

Отчет по устойчивости (рис. 7.6): в таблице Изменяемые ячейки приводится результат решения задачи. В таблице Ограничения выводятся значения для ограничений, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.

 

Рис. 7.6. Отчет по устойчивости поиска решения

Отчет по пределам (рис. 7.7): в отчете показано, в каких пределах может изменяться количество материалов, вошедших в оптимальное решение, при сохранении структуры оптимального решения; приводятся значения переменных в оптимальном решении, а также нижние и верхние пределы изменения значений переменных; здесь также указаны значения целевой функции при выпуске данного типа продукции на верхнем и нижнем пределах.

 

Рис. 7.7. Отчет по пределам поиска решения

 

Пример 7.2. Определение состава удобрений

Для получения удобрений видов 1 и 2 используются химические вещества A, B, C, D, требования к содержанию которых в удобрениях приведены в таблице 7.2.

Характеристики и запасы минералов, используемых для производства химических веществ A, B, C, D указаны в таблице 7.3.

Цена 1 т удобрения вида 1 равна 320 у.е., цена 1 т удобрения вида 2–350 у.е. Необходимо максимизировать прибыль от продажи удобрений видов 1 и 2.

Таблица 7.2 - Требования к содержанию химических веществ в удобрениях

Вид удобрения	Требования к содержанию химических веществ
	Не более 70 % вещества А Не более 40 % вещества В
	От 30 до 50 % вещества В Не менее 25 % вещества С Не более 65 % вещества D

Таблица 7.3 - Характеристики и запасы минералов

Минерал	Максимальный запас, т	Состав, процент	Цена, у.е./т
A	B	C	D

1. Математическая модель задачи.

Пусть:

- x_A1, x_B1, x_C1, x_D1 – количество химических веществ A, B, C, D, используемых для получения удобрения вида 1;

- x_A2, x_B2, x_C2, x_D2 – количество химических веществ A, B, C, D, используемых для получения удобрения вида 2;

- – количество используемого i-го минерала.

Найти максимум функции:

F = 320(x_A1+ x_B1+ x_C1+ x_D1)+350(x_A2+ x_B2+ x_C2+x_D2)-40y₁-50y₂-60y₃→max

при следующих ограничениях:

а) на состав вида удобрения (см.табл. 7.3):

x_A1 ≤ 0,7 (x_A1+ x_B1+ x_C1+ x_D1),

x_B1 ≤ 0,4 (x_A1+ x_B1+ x_C1+ x_D1),

x_B2 ≤ 0,5 (x_A2+ x_B2+ x_C2+x_D2),

x_B2 ≥ 0,3 (x_A2+ x_B2+ x_C2+x_D2),

x_C2 ≥ 0,25 (x_A2+ x_B2+ x_C2+x_D2),

x_D2 ≤ 0,65 (x_A2+ x_B2+ x_C2+x_D2),

б) на характеристики и состав минералов (см.табл. 7.4):

x_A1+x_A2 ≤ 0,3y₁+0,2y₂+0,15y₃,

x_B1+x_B2 ≤ 0,2y₁+0,3y₂+0,15y₃,

x_C1+x_C2 ≤ 0,15y₁+0,1y₂+0,4y₃,

x_D1+x_D2 ≤ 0,35y₁+0,4y₂+0,3y₃,

в) на диапазоны переменных:

x_i1 ≥ 0, x_i2 ≥ 0, ;

0 ≤ y₁ ≤ 1200,

0 ≤ y₂ ≤ 2500,

0 ≤ y₃ ≤ 3100.

2. Подготовка рабочей книги MS Excel. Разместим данные для решения задачи на рабочем листе в соответствии с рис. 7.8 и табл. 7.4.

 

Таблица 7.4 - Формулы для расчета, используемые при решении задачи

Описание	Ячейка	Формула
Целевая функция	D11	=320*СУММ(C5:C8)+350*СУММ(D5:D8)-40*F5-50*F6-60*F7
Ограничения	В14	=C5-0,7*СУММ(C5:C8)
	В15	=C6-0,4*СУММ(C6:C9)
	В16	=C7-0,5*СУММ(C7:C10)
	В17	=0,3*СУММ(D5:D8)-D6
	В18	=0,25*СУММ(D6:D9)-D7
	В19	=D8-0,65*СУММ(D5:D8)
	В20	=СУММ(C5:D5)-0,3*$F$5-0,2*$F$6-0,15*$F$7
	В21	=СУММ(C6:D6)-0,2*$F$5-0,3*$F$6-0,15*$F$7
	В22	=СУММ(C7:D7)-0,15*$F$5-0,1*$F$6-0,4*$F$7
	В23	=СУММ(C8:D8)-0,35*$F$5-0,4*$F$6-0,3*$F$7

Рис. 7.8. Лист рабочей книги для решения задачи производства удобрений

3. Ввод данных в окно Поиск решения осуществим в соответствии с рис. 7.9. Не следует забывать о заполнении необходимых опций в окне Параметры поиска решения.

Рис. 7.9. Заполнение окна Поиск решения для задачи о производстве удобрений

4. Результаты поиска решения, т.е. решение задачи об определении состава удобрений, представлены на рис. 7.10.

Рис. 7.10. Оптимальное решение задачи о производстве удобрений