Методичка по информационным технологиям

61

От 40 до 60% металла II

В Не менее 30% металла III Не более 70% металла IV

Характеристики и запасы руд, из которых получаются металлы I, II, II и IV

Пусть цена 1 т сплава A равна $200, а 1 т сплава B — $210. Необходимо максимизировать прибыль от продажи сплавов A и B.

Обозначим x1A, x2А, x3A, и x4A , (x1B, x2B, x3B, и x4B) количество I, II, III и IV металлов, использованных для получения сплава A (B), a yi где i [1; 3] — количество

использованной i-й руды.

Тогда математическая модель данной задачи имеет вид:

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

z=200(x1A+x2A+x3A+x4A)+210(x1B+x2B+x3B+x4B)-30y1-40y2-50y3

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

на состав сплавов:

x1A ≤ 0,8(x1A+x2A+x3A+x4A), x2A ≤ 0,3(x1A+x2A+x3A+x4A), x2B ≤ 0,6(x1B+x2B+x3B+x4B), x2B ≥ 0,4(x1B+x2B+x3B+x4B), x3B ≥ 0,3(x1B+x2B+x3B+x4B), x3B ≤ 0,7(x1B+x2B+x3B+x4B),

на характеристики и состав руды:

x1A+x1B ≤ 0,2y1+0,1y2+0,05y3, x2A+x2B ≤ 0,1y1+0,2y2+0,05y3, x3A+x3B ≤ 0,3y1+0,3y2+0,7y3, x4A+x4B ≤ 0,3y1+0,3y2+0,2y3,

на диапазоны использования переменных: xiA ≥ 0, xiB ≥ 0. i [1;4]

0 ≤ y1 ≤ 1000,

0 ≤ y2 ≤ 2000,

0 ≤ y3 ≤ 3000.

Первоначально надо ввести исходные данные в ячейки рабочего листа.

1.Отведите под переменные xiA, xiB диапазон ячеек C3:D6, а под переменные уi —

F3:F5.

2.Введите:

•в диапазон ячеек G3:G5— имеющиеся запасы руд;

•в диапазон ячеек НЗ:Н5— цены за одну тонну руды;

•в диапазон ячеек I3:М5 - характеристики состава руд.

3. В ячейку G9 введите функцию цели, которая в данном случае является функцией массива. Поэтому не забудьте завершить ее ввод нажатием комбинации клавиш <Shift>+<Ctrl>+<Enter>.

=200*СУММ(СЗ:С6)+210*СУММ(D3:D6)-СУММ(НЗ:H5*F3:F5)

Примечание. Четыре последние формулы — это формулы массивов. Поэтому не забудьте завершить ввод каждой из них нажатием комбинации клавиш

<Shift>+<Ctrl>+<Enter>.

Теперь можно перейти к непосредственному решению задачи при помощи средства Поиск решения.

На рабочем листе отобразятся результаты найденного решения.

Задание 34. Об оптимальном планировании штатного расписания

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

63

пройти предварительную подготовку. Потребности в количестве (с.-ч.) летного времени известны:

Подготовка стюардессы к выполнению своих обязанностей на регулярных авиалиниях занимает один месяц. Следовательно, прием на работу должен по крайней мере, на месяц опережать «ввод стюардессы в строй».

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

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

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

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

1.Отведите диапазон ячеек B3:B8 под число новых стюардесс, принимаемых на работу с января по июнь.

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

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

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

=B2

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

=D3+0.9*ВЗ

• Выберите ячейку D4, расположите указатель мыши на ее маркере заполнения

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

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

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

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

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

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

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

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

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

64

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

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

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

=CУMM(F3:F8)

Теперь все готово для решения задачи о составлении штатного расписан при помощи средства Подбор параметра. Выберите команду Поиск решения. Заполните диалоговое окно. Нажмите кнопку Выполнить. На рабочем листе отобразятся результаты найденного решения.

Примечание. Интересной особенностью этого решения является то, что фирма в последний месяц планового периода берет на обучение 17 новых стюардесс. Предположим, что авиакомпания не так уверена в будущих перспективах и решила в июне не брать на обучение новых сотрудников. Тогда в поле Ограничения диалогового окна Поиск решения надо добавить В8=0. Оптимальное решение при этом дополнительном ограничении приведет к временному повышению текущих затрат.

Задание 35. Транспортная задача

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

Каждый магазин в состоянии реализовать определенное, известное нам количество товара. Каждый из складов имеет ограниченную вместимость. Задача состоит в том, чтобы рационально выбрать – с какого склада в какие магазины нужно доставлять товар, чтобы минимизировать общие транспортные расходы.

65

В математике подобные задачи выбора оптимального маршрута по нескольким точкам относят к классу так называемых «транспортных задач» (Vehicle Routing Problems, VRP). И, конечно же, давно разработаны

способы их решения. Excel предоставляет пользователю один из них – с помощью мощной надстройки Поиск решения (Solver) в меню Сервис (Tools).

Перед началом оптимизации необходимо составить таблицу на листе Excel –математическую модель, описывающую ситуацию:

Подразумевается, что:

(B3:G5) описывает стоимость доставки единицы от каждого склада до каждого магазина.

(C14:G14) описывают необходимое для каждого магазина количество товаров на реализацию.

(J10:J11) отображают емкость каждого склада – предельное количество товара, которое склад может вместить.

(C12:G12) и (H10:H11) – соответственно, суммы по строке и столбцу для ячеек (C10:G12).

Общая стоимость доставки (E17) вычисляется как сумма произведений количества товаров на соответствующие им стоимости доставки.

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

Чтобы выполнить такую оптимизацию запустим Поиск решения (Solver) на вкладке Данные (Data). И зададим следующие настройки:

66

Целевая ячейка (Target cell) – тут необходимо указать конечную главную цель нашей оптимизации, т.е. ячейку с общей стоимостью доставки (E17). Целевую ячейку можно минимизировать (если это расходы, как в нашем случае), максимизировать (если это, например, прибыль) или попытаться привести к заданной константе.

Изменяемые ячейки (By changing cells) – здесь укажем ячейки (C10:G11),

варьируя значения которых мы хотим добиться нашего результата – минимальных затрат на доставку.

Ограничения (Subject to the Constraints) – список ограничений, которые надо учитывать при проведении оптимизации. В нашем случае это ограничения на вместимость складов и потребности магазинов. Для добавления ограничений в список нужно нажать кнопку Добавить (Add) и ввести условие в появившееся окно:

Кроме очевидных ограничений, связанных с физическими факторами (вместимость складов и средств перевозки, ограничения бюджета и сроков и т.д.) иногда приходится добавлять ограничения «специально для Excel». В нашем случае, например, нужно будет добавить вот такое ограничение:

Оно дополнительно уточнит, что объем перевозимого товара не может быть отрицательным.

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

67

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

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

Бывают, однако, ситуации, когда Excel не может найти подходящего решения. Имитировать такой случай можно, если указать в нашем примере требования магазинов в сумме большие, чем общая вместимость складов. Тогда при выполнении оптимизации Excel попытается приблизиться к решению, насколько это возможно, а затем выдаст сообщение о невозможности найти решение. Тем не менее, даже в этом случае мы имеем массу полезной информации – в частности

68

можем видеть «слабые звенья» наших бизнес-процессов и понять направления совершенствования.

Задание 36. Задача о назначениях

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

Внашем конкретном случае задача о назначении формулируется так.

Имеется четыре рабочих и четыре вида работ. Стоимости cij выполнения i-м рабочим j-й работы приведены в таблице, где под строкой понимается рабочий, а под столбцом— работа:

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

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

Прежде всего, построим математическую модель задачи. Обозначим через xij переменную, имеющую только два допустимых значения: 0 и 1. Будем считать, что:

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

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

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

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

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

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

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

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

3.Введите в ячейку J1 функцию цели, вычисляющую стоимость работ =СУММПРОИЗВ(A2:D5;F2:I5)

69

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

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

Задание 37. Самостоятельно. Оптимальные поставки песка.

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

Дано: запасы (предложения) песка на карьерах (поставщиков); потребности (спрос) песка строиплащадок (потребителей); затраты (цена) на транспортирования между каждой парой «поставщик-потребитель».

70

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

Задание 38. Самостоятельно

Ванечка Уточкин пользуется огромным успехом у девушек 10 А класса. Пробегав весь семестр по свиданиям, к концу декабря Ванечка обнаружил, что почти по всем предметам ему грозит «неуд». Помочь Ванечке вызвались все 10 девушек, вот только успехи в учебе у всех разные, да и объяснить каждая может только один предмет.

При заданной матрице эффективности найти оптимальный вариант распределения девочек по предметам таким образом, чтобы общая эффективность от помощи была максимальной.

Замечание: в качестве эффективности берется оценка, полученная девочкой по предмету за прошлый семестр, при условии, что в школе принята 10-бальная система оценок.

Задание 39. Самостоятельно

На ёлку в старшую группу детского садика пришёл Дед Мороз. Подарков у него в мешке ровно столько, сколько мальчиков и девочек ему предстоит поздравить. Чтобы помочь ему в выборе подарка для каждого ребёнка, воспитательница попросила всех заполнить анкетку.Рядом с наименованием подарка малыш должен был поставить число от 1 до 9, которое будет показывать, насколько желательным данный подарок окажется для него или для нее. Собрав все анкетки, воспитательница получила следующую матрицу предпочтений (см. левее)

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

Задание 40. Контрольная работа.

Вариант 1. Фирма имеет возможность рекламировать свою продукцию, используя местные радио и телевизионную сеть. Затраты на рекламу в бюджете фирмы ограничены суммой $1ООО в месяц. Каждая минута радиорекламы обходится в $5, а каждая минута телерекламы — в $100. Фирма хотела бы использовать радиосеть, по крайней мере, в два раза чаще, чем