Задача об оптимальном производстве красок

Рассмотрим следующую задачу планирования производства. Небольшая фабрика выпускает 2 типа красок: для внутренних нужд (I) и наружных работ (Е). Продукция обоих видов поступает в оптовую продажу. Для производства используются два исходных продукта – А и В. Максимально возможные запасы этих продуктов составляют 6 т и 8 т соответственно. Расходы А и В на 1 т соответствующих красок приведены в табл. 7.1.

Таблица 7.1–Исходные данные задачи о производстве красок

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

Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки.

Оптовые цены одной тонны красок равны: 3000 руб. для краски Е и 2000 руб. для краски I.

Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Для решения этой задачи необходимо сначала построить математическую модель. Процесс построения модели можно начать с ответа на следующие вопросы:

- Для определения каких величин строится модель? Другими словами, что является переменными модели?

- В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?

- Каким ограничениям должны удовлетворять неизвестные?

В нашем случае фабрике необходимо спланировать объем производства красок так, чтобы максимизировать прибыль. Поэтому переменными являются

- х_I суточный объем производства краски I;

- x_E суточный объем производства краски E.

Суммарная суточная прибыль от производства х_I краски I и х_Е краски Е равна:

z = 3000 х_I + 2000 x_E

Целью фабрики является определение среди всех допустимых значений х_I и x_E таких, которые максимизируют суммарную прибыль, т. е. целевую функцию z.

Перейдем к ограничениям, которые налагаются на x_I и x_E. Объем производства красок не может быть отрицательным. Следовательно,

х_Е, x_I ³0.

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

x_E + 2x_I £6,

2х_Е + x_I £8.

Кроме того, ограничения на величину спроса на краски имеют вид:

x_I – x_E £1,

x_I £2.

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

Максимизировать:

z = 3000х_Е + 2000х_I,

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

x_E + 2x_I £6,

2х_Е + x_I £8.

x_I – x_E £1,

x_I £2,

х_Е, x_I ³0

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

Перейдем к вводу исходных данных на рабочем листе для решения задачи о красках. Для этого:

1. Отведите ячейки A3 и В3 под значения переменных х_Е и x_I соответственно (рис. 7.1).

2. Введите в ячейку С4 функцию цели

=3000*АЗ+2000*ВЗ

3. Введите в ячейки диапазона А7:А10 левые части ограничений, а в ячейки диапазона В7:В10 соответствующие правые части ограничений:

Ячейка	Формула	Ячейка	Значение
А7	=АЗ+2*ВЗ	В7
А8	=2*АЗ+В3	В8
А9	=ВЗ-А3	В9
А10	=ВЗ	В10

Рис. 7.1. Диапазоны, отведенные под переменные, целевую функцию и ограничения в задаче о производстве красок

Решим задачу при помощи средства Поиск решения. Оноявляется одной из надстроек Excel. Если в меню Сервисотсутствует команда Поиск решения,для ее установки необходимо выбрать команду Сервис – Надстройки.На экране отобразится диалоговое окно Надстройки.В списке Список надстроеквыберите Поиск решения и нажмите кнопку ОК.

Переходим к нахождению оптимального производства красок.

1. Выберите команду Сервис – Поиск решения.На экране отобразится диалоговое окно Поиск решения(рис. 7.2).

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

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

3. Нажмите кнопку Выполнить.На экране отобразится окно Результаты поиска решения(рис. 7.3).

4. После нажатия кнопки ОК, результаты будут внесены в рабочий лист.

Рис. 7.3. Оптимальное решение задачи о производстве красок

7. 2. Задача об оптимальном планировании штатного расписания

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

Таблица 7.2–Потребности в стюардессо-часах в задаче об оптимальном планировании штатного расписания

Месяц	Потребность, с.-ч.	Месяц	Потребность, с.-ч.
Январь		Апрель
Февраль		Май
Март		Июнь

Подготовка стюардессы к выполнению своих обязанностей на регулярных авиалиниях занимает один месяц. Следовательно, прием на работу должен, по крайней мере, на месяц опережать "ввод стюардессы в строй". Кроме того, каждая обучаемая стюардесса должна в течение месяца, отведенного на ее подготовку, пройти 100-часовую практику непосредственно во время полетов. Таким образом, за счет каждой обучаемой стюардессы в течение месяца освобождается 100 ч. рабочего времени, отведенного для уже обученных стюардесс.

Каждая полностью обученная стюардесса в течение месяца может иметь налет до 150 ч. Авиакомпания в начале января уже имеет 60 опытных стюардесс. При этом ни одну из них не снимают с работы. Установлено также, что приблизительно 10% обученных стюардесс увольняются по собственному желанию по семейным или другим обстоятельствам.

Опытная стюардесса обходится авиакомпании в $800, а обучаемая – в $400 в месяц. Необходимо спланировать штат авиакомпании, минимизирующий издержки за отчетные шесть месяцев.

Для данной задачи также можно выписать математическую модель, но ее удобнее проанализировать в более развернутой форме. А именно:

1. Отведите диапазон ячеек В3:В8 под число новых стюардесс, принимаемых на работу с января по июнь (рис. 7.4).

2. В ячейку В2 введем число работающих стюардесс в декабре.

3. В ячейках диапазона D3:D8 будем вычислять число постоянно работающих стюардесс в текущем месяце. Для этого:

• в ячейку D3 введите формулу

=В2;

• в ячейку D4 введите формулу

=D3+0.9*B3;

• выберите ячейку D4, расположите указатель мыши на ее маркере авзаполнения и протяните его вниз на диапазон D5:D8. Теперь, в ячейках диапазона D3:D8 будем вычислять число постоянно работающих стюардесс в текущем месяце.

Рис. 7.4. Исходные данные задачи о штатном расписании

4. В ячейках диапазона ЕЗ:Е8 вычислим налет по месяцам. Для этого:

введите в ячейку Е3 формулу

=D3*$G$12+B3*$F$12

• где в ячейки F12 и G12 введен допустимый налет обучаемой и работающей стюардессы.

• выберите ячейку Е3, расположите указатель мыши на ее маркере автозаполнения и протяните его вниз на диапазон Е4:Е8. Теперь, в ячейках диапазона ЕЗ:Е8 будет вычисляться налет по месяцам.

5. В ячейках диапазона F3:F8 вычислим затраты по месяцам. Для этого:

• введите в ячейку F3 формулу

=D3*$E$12+B3*$D$12

где в ячейки D12 и Е12 введены зарплата обучающейся и работающей стюардессы;

• выберите ячейку F3, расположите указатель мыши на ее маркере автозаполнения и протяните его на диапазон F4:F8.

6. Осталось только вычислить суммарные затраты за планируемый период. Для этого в ячейку F9 введите формулу

=CYMM(F3:F8).

Теперь все готово для решения задачи о составлении штатного расписания при помощи средстваПоиск решения.

1. Выберите команду Сервис – Поиск решения.

2. На экране отобразится диалоговое окно Поиск решения.Заполните диалоговое окно Поиск решения,как показано на рис. 7.5.

Рис. 7.5. Окно команды Поиск решения в задаче о штатном расписании

Результаты расчета оптимального штата стюардесс приведены на рис. 7.6.

Рис. 7.6. Найденное решение задачи о штатном расписании

7. 3. Транспортная задача

Рассмотрим еще один пример применения средства Поиск решения.Фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики располагаются в Денвере, Бостоне, Нью-Орлеане и Далласе с производственными возможностями соответственно 200, 150, 225 и 175 единиц продукции ежедневно. Распределительные центры располагаются в Лос-Анджелесе, Далласе, Сент-Луисе, Вашингтоне и Атланте с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно, соответственно. Хранение на фабрике не поставленной в центр распределения единицы продукции обходится в $0,75 в день, а штраф за просрочку поставки заказанной потребителем в центре распределения единицы продукции, но там не находящейся, равен $2,5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в табл. 7.3.

Таблица 7.3–Транспортные расходы

	Лос-Анджелес	Даллас	Сент-Луис	Вашингтон	Атланта	Производство
1 Денвер	1,5		1,75	2,25	2,25
2 Бостон	2,5		1,75		1,5
3 Нью-Орлеан		1,5	1,5	1,75	1,75
4 Даллас		0,5	1,75	1,75	1,75
Потребность

Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.

Для решения данной задачи построим ее математическую модель. Неизвестными здесь являются объемы перевозок: Пусть х_ij — объем перевозок с i-ой фабрики в j-ый центр распределения. Функцией цели являются суммарные транспортные расходы, т. е.

где с_ij — стоимость перевозки единицы продукции с с i-ой фабрики в j-ый центр распределения. Кроме того, неизвестные должны удовлетворять следующим ограничениям:

- неотрицательность объема перевозок;

- т. к. модель сбалансирована, то вся продукция должна быть вывезена с фабрик, и потребность всех центров распределения должна быть полностью удовлетворена.

Таким образом, мы имеем следующую модель:

минимизировать

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

где а_i – объем производства на i-ой фабрике; b_j – спрос в j-ом центре распределения.

Выполните следующую подготовительную работу для решения транспортной задачи с помощью средства Поиск решения(рис. 7.7).

1. Введите в ячейки диапазона В3: F6 стоимости перевозок.

2. Отведите ячейки диапазона В8:F11 под значения неизвестных (объемов перевозок).

3. Введите в ячейки диапазона Н8:Н11 объемы производства на фабриках.

4. Введите в ячейки диапазона В13:F13 потребность в продукции в пунктах распределения.

Рис. 7.7. Исходные данные для транспортной задачи

5. В ячейку В16 введите функцию цели

=СУММПР0ИЗВ(ВЗ:F6;В8:F11)

6. В ячейки диапазонов G8:G11 введите формулы, вычисляющие объемы производства на фабриках, в ячейки диапазона B12:F12 объемы доставляемой продукции в пункты распределения. А именно:

Ячейка	Формула	Ячейка	Формула
G8	=CУMM(B8:F8)	B12	=СУММ(В8:В11)
G9	=CУMM(B9:F9)	C12	=СУММ(С8:С11)
G10	=CУMM(B10:F10)	D12	=CУMM(D8:D11)
G11	=CУMM(B11:F11)	E12	=СУММ(Е8:Е11)
		F12	=CУMM(F8:F11)

7. Выберите команду Сервис – Поиск решенияи заполните диалоговое окно Поиск решения,как показано на рис. 7.8.

8. Нажмите кнопку Выполнить.Средство Поиск решениянайдет оптимальный план поставок продукции и соответствующие ему транспортные расходы (рис. 7.9).

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

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

Задача о назначении

В данном разделе продемонстрируем, как средство Поиск решенияпозволяет решать задачу о назначении.

В нашем конкретном случае задача о назначении формулируется следующим образом. Имеются четыре рабочих и четыре вида работ. Стоимости С_ijвыполнения i-ым рабочим j-ой работы приведены в таблице, где под строкой понимается рабочий, а под столбцом – работа:

Стоимость выполнения работ

Рабочие
Виды работ

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

Замечание. Данная задача является сбалансированной, т. е. число работ совпадает с числом рабочих. Если задача несбалансированна, то перед началом решения ее необходимо сбалансировать, введя недостающее число фиктивных строчек или столбцов с достаточно большими штрафными стоимостями работ.

Для решения данной задачи сначала построим ее математическую модель. Обозначим символом Х_ij переменную, имеющую только два допустимых значения: 0 или 1. Такие переменные называются двоичными. Причем, будем считать, что:

- Х_ij = 1, если i-ым рабочим выполняется j-ая работа;

- Х_ij = 0, если i-ым рабочим не выполняется j-ая работа.

Тогда математическую модель задачи о назначении можно сформулировать следующим образом:

минимизировать

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

Для решения этой задачи с помощью средства Поиск решениянеобходимо выполнить некоторые предварительные действия:

1. В ячейки диапазона А2: D5 введите стоимости работ.

2. Отведите ячейки диапазона F2:I5 под неизвестные.

3. Введите в ячейку J1 функцию цели, вычисляющую стоимость работ:

=СУММПРОИЗВ(А2:D5; F2:I5)

4. В ячейки диапазонов J2:J5 и F6:I6 введите формулы, задающие левые части ограничений и представленные в следующей ниже таблице.