Рассаживаем учащихся по автобусам
Заполните таблицу.
Таблица
|
|
|
|
D |
E |
1 |
Класс |
экскурсию |
автобус |
Второй автобус |
Третий автобус |
2 |
10 А |
23 |
|
|
|
3 |
10 Б |
17 |
|
|
|
4 |
10 В |
22 |
|
|
|
5 |
10 Г |
8 |
|
|
|
6 |
11 А |
18 |
|
|
|
7 |
11 Б |
6 |
|
|
|
8 |
11 В |
19 |
|
|
|
9 |
11 Г |
14 |
|
|
|
10 |
Итого в автобусе |
|
|
|
В ячейках столбцов С, D и Е должны находиться либо 1 (единица), либо 0 (нуль), либо ничего (что аналогично нулю). Единица ставится в ячейку тогда и только тогда, когда класс, указанный в строке, целиком едет в автобусе, указанном в столбце. Обратите внимание, что при занесении чисел они прижимаются к правому краю столбца.
Перед тем как начинать «рассаживание» классов по автобусам, необходимо заполнить формулами нижний этаж ячеек С10, D10, Е10. Так, в ячейке С10 должна стоять формула
С2*В2 + СЗ*ВЗ + С4*В4 + С5*В5 + С6*В6 + С7*В7 + С8*В8 + С9*В9.
Это позволит в дальнейшем контролировать загрузку автобусов. Запишите нужные формулы в соответствующие ячейки. Обратите внимание, что в качестве знака умножения в формулах, записываемых в ячейки электронной таблицы, употребляется «*».
Ваша задача – расставить единицы и нули в таблице таким образом, чтобы в каждом автобусе ехало не более 45 человек. Выполните эту работу.
Составители учебника предлагают решить нам эти задачи методом подбора, используя электронную таблицу. Для реализации оптимизационных расчетов в Open Calc необходимо использовать надстройку Поиск решения с помощью команды системного меню Сервис. Модель использует целевую функцию, которая записывается в виде формулы в отдельной ячейке. Для целевой функции указывается: максимизация, минимизация или равенство фиксированному значению. В процесс поиска решения изменяются значения в указанных ячейках, соответствующие переменным, при соблюдении ограничений.
Построим математическую модель задачи. Введем переменную хij, значение которой равно 1, если i-й класс едет в j-ом автобусе, и равно 0 в противном случае. Тогда условие того, что 10 А класс может ехать только в одном автобусе выражается равенством х11 + х12 + х13 = 1. Аналогично записываются равенства относительно других классов. Таким образом, получаем систему: . Обозначим число учащихся, едущих в первом автобусе через у1, тогда у1 = 23 х11 + 17 х21 + 22 х31 + 8 х41 + 18 х51 + 6 х61 +19 х71 + 14 х81 . Аналогично у2 = 23 х12 + 17 х22 + 22 х32 + 8 х42 + 18 х52 + 6 х62 +19 х72 + 14 х82 – число учащихся, едущих во втором автобусе, у3 = 23 х13 + 17 х23 + 22 х33 + 8 х43 + 18 х53 + 6 х63 +19 х73 + 14 х83 – число учащихся, едущих в третьем автобусе. Так как в каждый автобус можно посадить не более 45 человек, то у1 ≤ 45, у2 ≤ 45 и у3 ≤ 45. Обозначим число всех учащихся, поместившихся в автобусы через F, тогда F = у1 + у2 + у3 .
Таким образом, задача состоит в определении таких значений неизвестных хij (), удовлетворяющих системе уравнений , ограничениям у1 ≤ 45, у2 ≤ 45 и у3 ≤ 45, при которых достигается максимальное значение функции F = у1 + у2 + у3 .
Подготовим данные оптимизационной модели на рабочем листе. Заполните таблицу.
Таблица
|
|
|
|
D |
E |
F |
1 |
Класс |
экскурсию |
автобус |
Второй автобус |
Третий автобус |
Ограничения |
2 |
10 А |
23 |
|
|
|
|
3 |
10 Б |
17 |
|
|
|
|
4 |
10 В |
22 |
|
|
|
|
5 |
10 Г |
8 |
|
|
|
|
6 |
11 А |
18 |
|
|
|
|
7 |
11 Б |
6 |
|
|
|
|
8 |
11 В |
19 |
|
|
|
|
9 |
11 Г |
14 |
|
|
|
|
10 |
Итого в автобусе |
|
|
|
|
|
Двойной рамкой в таблице выделен блок ячеек С2:E9, в котором содержатся значения переменных.
В ячейку F2 введите формулу = SUM(C2:E2), которая соответствует левой части равенства х11 + х12 + х13 =1.
Скопируйте эту формулу в ячейки F3:F9.
В ячейку С10 введите формулу =SUMPRODUCT($B$2:$B$9;C2:C9), которая соответствует у1.
Скопируйте эту формулу в ячейки D10 и E10.
В ячейку F10 введите формулу =SUM(C10:E10), которая соответствует целевой функции F = у1 + у2 + у3 .
В диалоговом окне Поиск решения укажите:
Установить целевую ячейку: $F$10
Равной: максимальному значению
Изменяя ячейки: $C$2:$E$9
Для ввода ограничений, нажмите кнопку Добавить
В диалоговом окне Добавление ограничения для ввода первого ограничения $F$2:$F$9 = 1укажите:
Ссылка на ячейку: $F$2:$F$9
Раскройте кнопку списка и выберите знак =
Ограничение: 1
Аналогично введите ограничения $C$2:$E$9 = двоичное и $C$10:$E$10 ≤ 45 и нажмите кнопку Ок.
В диалоговом окне Поиск решения нажмите кнопку Параметры, установите Линейная модель и нажмите Ок.
В диалоговом окне Поиск решения нажмите кнопку Выполнить. На экране диалоговое окно Результаты поиска решения в котором сообщается о результате решения. Укажите: Сохранить найденное решение и нажмите Ок, чтобы вернуться к рабочему листу. В блоке ячеек $C$2:$E$9, где хранились переменные, появится решение задачи. Приведем один из возможных вариантов ответов (табл. ).
Таблица
Класс |
Едут на экскурсию |
Первый автобус |
Второй автобус |
Третий автобус |
Ограничения |
10 А |
23 |
0 |
0 |
1 |
1 |
10 Б |
17 |
1 |
0 |
0 |
1 |
10 В |
22 |
0 |
1 |
0 |
1 |
10 Г |
8 |
1 |
0 |
0 |
1 |
11 А |
18 |
1 |
0 |
0 |
1 |
11 Б |
6 |
0 |
0 |
1 |
1 |
11 В |
19 |
0 |
1 |
0 |
1 |
11 Г |
14 |
0 |
0 |
1 |
1 |
Итого в автобусе |
127 |
43 |
41 |
43 |
127 |
Из таблицы видно, что в первом автобусе едут 10 Б, 10 Г и 11 А классы. Во втором – 10 В и 11 В, в третьем – 10 А, 11 Б и 11 Г. Из 127 желающих попасть на экскурсию всех можно разместить в три автобуса, в первом поедут 43 человека, во втором 41 и в третьем – 43.