Решение задач распределения
Рассмотрим примеры задач распределения.
Пример 7.1. Планирование производства материалов
Фирма выпускает два вида строительных материалов: А и В. Продукция обоих видов поступает в продажу. Для производства материалов используются два исходных продукта: I и II. Максимально возможные суточные запасы этих продуктов составляют 7 и 9 тонн соответственно. Расходы продуктов I и II на одну тонну соответствующих материалов приведены в табл. 7.1.
Изучение рынка сбыта показало, что суточный спрос на материал В никогда не превышает спроса на материал А более чем на 1 т. Кроме того, спрос на материал А никогда не превышает 3 т в сутки. Оптовые цены одной тонны материалов равны: 4000 у.е. для В и 3000 у.е. для А. Какое количество материала каждого вида должна производить фабрика, чтобы доход от реализации был максимальным?
Таблица 7.1 - Расход продуктов
| Исходный продукт | Расход исходных продуктов, т (на одну тонну материалов) | Максимально возможный запас, т | |
| Материал А | Материал В | ||
| I | |||
| II |
1. Формулировка математической модели задачи:
1) переменные для решения задачи: x1 – суточный объем производства материала А, x2 – суточный объем производства материала В;
2) определение функции цели (критерия оптимизации): суммарная суточная прибыль от производства x1 материала А и x2 материала В:
F = 4000x2 + 3000x1,
поэтому цель фабрики – среди всех допустимых значений x2 и x1 найти такие, которые максимизируют суммарную прибыль от производства материалов F:
F = 4000x2 + 3000x1 → max;
3) ограничения на переменные:
а) объем производства красок не может быть отрицательным, т.е.
x2 ≥ 0, x1 ≥ 0;
б) расход исходного продукта для производства обоих видов материалов не может превосходить максимально возможного запаса данного исходного продукта, т. е.:
2x2 + 3x1 ≤ 7,
3x2 + 2x1 ≤ 9
ограничения на величину спроса на материалы:
x1 - x2 ≤ 1,
x1 ≤ 3.
Таким образом, получаем математическую модель задачи:
- найти максимум следующей функции:
- F = 4000x2+3000x1 →max
- при ограничениях вида:
2x2 + 3x1 ≤ 7,
3x2 + 2x1 ≤ 9,
x1 - x2 ≤ 1,
x1 ≤ 3,
x1 ≥ 0, x2 ≥ 0.
2. Подготовка листа рабочей книги MS Excel для вычислений: на рабочий лист вводим необходимый текст, данные и формулы в соответствии с рис. 7.2. Переменные задачи x1 и x2 находятся в ячейках С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. Математическая модель задачи.
Пусть:
- xA1, xB1, xC1, xD1 – количество химических веществ A, B, C, D, используемых для получения удобрения вида 1;
- xA2, xB2, xC2, xD2 – количество химических веществ A, B, C, D, используемых для получения удобрения вида 2;
- 
– количество используемого i-го минерала.
Найти максимум функции:
F = 320(xA1+ xB1+ xC1+ xD1)+350(xA2+ xB2+ xC2+xD2)-40y1-50y2-60y3→max
при следующих ограничениях:
а) на состав вида удобрения (см.табл. 7.3):
xA1 ≤ 0,7 (xA1+ xB1+ xC1+ xD1),
xB1 ≤ 0,4 (xA1+ xB1+ xC1+ xD1),
xB2 ≤ 0,5 (xA2+ xB2+ xC2+xD2),
xB2 ≥ 0,3 (xA2+ xB2+ xC2+xD2),
xC2 ≥ 0,25 (xA2+ xB2+ xC2+xD2),
xD2 ≤ 0,65 (xA2+ xB2+ xC2+xD2),
б) на характеристики и состав минералов (см.табл. 7.4):
xA1+xA2 ≤ 0,3y1+0,2y2+0,15y3,
xB1+xB2 ≤ 0,2y1+0,3y2+0,15y3,
xC1+xC2 ≤ 0,15y1+0,1y2+0,4y3,
xD1+xD2 ≤ 0,35y1+0,4y2+0,3y3,
в) на диапазоны переменных:
xi1 ≥ 0, xi2 ≥ 0, 
;
0 ≤ y1 ≤ 1200,
0 ≤ y2 ≤ 2500,
0 ≤ y3 ≤ 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. Оптимальное решение задачи о производстве удобрений