Работа рассчитана на 1 аудиторный час. Постановка задачи о размещении объекта

Постановка задачи о размещении объекта

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

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

Рассмотрим конкретно один из вариантов этой задачи.

Имеются четыре производственных помещения, расположенных на некотором производстве. Определить местоположение объекта (помещения) для размещения. Для примера объектом размещения выберем новый склад.

Требуется разместить новый склад в удобном для рабочих месте, предполагая, что сумма расстояний от нового объекта до всех производственных помещений будет минимальным значением (рис. 5.1). Это значение и является целевой функцией, которую необходимо определить, используя функции среды MS EXCEL.

Рис. 5.1.

Другие варианты задачи о строительстве или размещении объектов могут быть сформулированы как для различных значений количества производственных помещений, местоположения этих помещений, так и для различных видов целевой функции.

Математическая постановка задачи о местоположении объекта

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

x₁ x₂ x x₃ x₄

Рис. 5.2.

Координаты исходных производственных помещений могут быть записаны как координаты соответствующих точек в виде (х_i, у_i), где i Є {1, 2, 3, 4}.

Координаты для нового склада, который предполагается спроектировать и разместить, можно положить равными (х, у). Очевидно, они служат переменными рассматриваемой задачи оптимизации, каждая из которых по своему характеру может принимать действительные значения.

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

В качестве целевой функции данной задачи будем рассматривать сумму расстояний от искомой точки (х, у)до каждой из заданных точек (х_i, у_i), где i Є {1, 2, 3, 4}.

Расстояние от i -го помещения до склада определяется по формуле:

, (5.1)

где .

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

(5.2)

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

, (5.3)

где R – область значений для х и у.

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

Решение задачи о местоположении объекта с помощью MS EXCEL

Для решения данной задачи создать новый лист. Переименовать его в «Задача о размещении нового склада». Выполнить подготовительный этап для решения - создать макет листа (рис. 5.3).

Рис. 5.3.

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

В ячейку G12 поместить значение целевой функции. Формула для ее вычисления: =СУММ(B7:B10).

В ячейку B7 будет ввести формулу:

=КОРЕНЬ(($B$12-B2)^2+($D$12-D2)^2).

Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню Сервис – Поиск решения (рис. 5.4).

Рис. 5.4

В поле с именем Установить целевую ячейку ввести абсолютный адрес ячейки $G$12 – значение целевой функции, а в поле с именем Изменяя ячейки ввести абсолютный адрес ячеек $B$12:$D$12 (рис. 5.4). Поля с ограничениями можно оставить пустыми, поскольку целевая функция является выпуклой на всем множестве допустимых значений. Параметры поиска решения можно оставить без изменения (рис. 5.5).

Рис. 5.5

Параметры поиска решения задаются в каждом случае отдельно. Результат выполнения задачи о размещении склада вместе с графическим представлением показан на рис. 5.6.

Рис. 5.6

Замечание. Графическое представление размещения производственных помещений и нового склада выполнено с применением Мастера диаграмм (рис. 5.7). Для этого выделить предварительно массив данных, т.е. ячейки B14:C19. Затем выбирать тип диаграммы – Стандартные – Точечная (рис. 5.7), выполнить последовательно четыре шага Мастера диаграмм и получить готовую диаграмму решения задачи (см. рис. 5.6).

Рис. 5.7

Контрольные вопросы

1. К какому классу задач оптимизации относится задача о размещении объекта?

2. Что представляют собой независимые переменные в математической модели задачи о размещении объекта?

3. Могут ли быть значения координат объектов отрицательными?

4. Каким методом решается задача о размещении объекта в программе МS ЕХСЕL?

5. Что рассматривается в качестве целевой функции задачи о размещении объекта?

6. Какие обозначения следует ввести для математической постановки задачи о размещении объекта?

7. Почему переменные задачи оптимизации размещения объекта могут принимать действительные значения?

8. Почему задача о размещении объекта относится к классу задач нелинейного программирования без ограничений?

9. С помощью какой процедуры поиска решения МS ЕХСЕL находят оптимальное значение формулы, содержащейся в целевой ячейке? С какими ячейками работает данная процедура?

10. Почему поля с ограничениями можно оставить пустыми?

11. С помощью каких функциональных возможностей можно обеспечить графическое представить решение задачи в МS ЕХСЕL?

Поиск по сайту: