Вопрос 5. Формирование таблиц для ввода исходных данных (модель транспортной задачи).
Решение задач методом поиска решения требует приведения условий задачи к определенному виду (этап 1 и 2). Для ввода исходных данных необходимо сформировать две таблицы. В случае производственной задачи первая предназначена для задания критерия оптимальности, ввода первоначального плана и вывода оптимального решения, а вторая - для формирования матрицы ограничений. В случае транспортной задачи первая таблица используется для формирования решения и расчета суммарных перевозок, а вторая содержит данные по стоимости перевозок, объемы запасов поставщиков и заказов потребителей.
-
Производители
Потребители
Объем производства
В1
В2
В3
В4
А1
35
30
10
10
53
А2
21
41
53
10
28
А3
39
32
27
20
61
Спрос
47
38
23
24
=СУММ(B6:F6)
= СУММ
(F3:F6)
Производители
Потребители
Объем производства
В1
В2
В3
В4
В5
А1
=B3
=C3
=D3
=E3
0
=F3
А2
=B4
=C4
=D4
=E4
0
=F4
А3
=B5
=C5
=D5
=E5
0
=F5
Спрос
=B6
=C6
=D6
=E6
10
=СУММ
(B14:G14)
=СУММ(G11:G14)
Производители
Потребители
Объем производства
В1
В2
В3
В4
В5
А1
1
1
1
1
1
=СУММ(B19:F19)
А2
1
1
1
1
1
=СУММ(B20:F20)
А3
1
1
1
1
1
=СУММ(B21:F21)
Спрос
=СУММ
(B19:B21)
=СУММ
(C19:C21)
=СУММ
(D19:D21)
=СУММ
(E19:E21)
=F7-G6
=СУММПРОИЗВ
(B11:F13;B19:F21)
=СУММ
(B22:G22)
=СУММ(G19:G22)
Рисунок. Лист электронной таблицы с условием и сформированными таблицами исходных данных для решения транспортной задачи.
Рассмотрим структуру первой таблицы. Первая таблица должна содержать матрицу стоимостей перевозок (исходные данные), а также векторы объемов заказов каждого потребителя (правый столбец) и запасы производителя (нижняя строка). Для решения задачи необходимо убедиться, что данная модель закрыта, т.е. что общий объем заказа равен общему объему потребностей. Следовательно, проконтролировать суммы значений по строке и столбцу с помощью функций СУММ или SUM. В противном случае эту задачу требуется искусственно привести к закрытому типу путем ввода дополнительного условного потребителя или производителя. При этом в таблицу вводится новая строка или столбец из единиц, а во вторую строка или столбец где в качестве стоимости перевозки указываются нулевые значения стоимостей.
В основе второй таблицы матрица объемов перевозок (начальные значения, обычно единицы), в которой количество столбцов и строк равно количеству поставщиков и потребителей. Правее необходимо сформировать столбец расчета объема перевозок каждого из потребителей, а ниже строку расчета объема перевозок каждого из поставщиков. В основе расчета лежит функция суммирования по строкам и столбцам соответственно (в одной клетке вводится формула, а для других копируется маркером автозаполнения).
Формируем критерий оптимальности, место его расположения может быть любым. Критерием оптимальности будет суммарные затраты на перевозку грузов от каждого поставщика к каждому потребителю, следовательно, в основе расчета будет функция СУММАПРОИЗВ (SUMPRODUCT) для диапазонов содержащих матрицы стоимости и объемов перевозок (начальные значения и исходные данные). Естественно, что затраты на перевозку должны быть минимизированы.
Сформируем условие задачи в рамках надстройки Поиск решения. Откроем соответствующее окно: Меню Сервис → Поиск решения (Optimization Solver) . В качестве целевой ячейки зададим адрес клетки, содержащей суммарные затраты на перевозку (функция СУММАПРОИЗВ или SUMPRODUCT). Направление оптимизации - минимум целевой функции. Изменяемые ячейки – матрица объемов перевозок (первая таблица без столбца и строки с расчетными формулами). В окне ограничения введем с помощью кнопки Добавить (Add) необходимые условия исходя из следующих соображений:
количества перевезенных грузов не могут превышать производственных возможностей производителей (нельзя перевести больше, чем есть запасов у производителя), в терминах задачи это означает, что строка суммарных объемов каждого производителя последняя в первой таблице меньше или равна (обычно здесь используется знак точно равно) строке запасов второй таблицы;
Рисунок. Окно электронной таблицы для ввода условий
транспортной задачи.
количество доставляемых грузов не должно быть меньше, чем требуется потребителю (все потребности должны быть удовлетворены), т.е. производство должно быть не меньше потребности; в терминах задачи столбец суммарных потребностей последний в первой таблице больше или равен (обычно здесь используется знак точно равно) соответствующему столбцу второй таблицы.
число перевозок не может быть отрицательным (т.е. все значения в клетках диапазона начальных значений больше или равны нулю).
Замечание. В рассмотренной модели не учитывается «кратность» перевозимых партий товаров в соответствии с вместимостью транспортного средства.
Лекция 5. Базы данных. Основы функционирования Access.
Основные вопросы: