Исследование задачи размещения станочного парка

1. Математическое моделирование

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

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

Управляемыми переменными являются переменные x_i, i= - количество станков i-го типа, размещаемых в цехе. Управляемые переменные могут принимать только целые значения.

Тогда можно записать математическую модель задачи:

Имеем две линейные целевые функции и одно ограничение, управляемые переменные могут принимать только целые значения. Таким образом, задача относится к категории задач линейного целочисленного программирования (в дальнейшем ЛЦП).

Для программного решения данной задачи, можно представить ее в виде задачи о ранце:

В данном случае целевой функцией будет L₀, а единственным ограничением является ограничение по площади.

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

2. Обоснование и выбор метода решения

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

(4) — для нахождения нижней границы 1-й целевой функции

— для нахождения верхней границы 1-й целевой функции

— для нахождения нижней границы 2-й целевой функции

— для нахождения верхней границы 2-й целевой функции После решения данных задач мы получаем очертания области критериев. Для нахождения четкой границы области изменения критериев, необходимо разбить интервал, в котором изменяется критерий L1 на равномерные отрезки, и для каждой точки интервала C_i решить задачи ЛЦП с условием:

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

Суть метода состоит в следующем: конусом назовем пространственный угол, образованный лучами, идущими из общей вершины и ограниченными в каждой плоскости углом 90⁰. Направление ограничивающих лучей соответствует направлению оптимизации критериев. Для получения множества Парето достаточно установить вершину конуса на все точки границы области критериев, если при этом ни один луч не пересекает область, то вершина лежит в области Парето, а если пересекает, то нет. [1]

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

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

где — вес каждой компоненты критерия, чем эта величина больше, тем большее влияние оказывает этот критерий. [1]

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

(10)

Решив задачу ЛЦП для данной целевой функции при заданных ограничениях, мы найдем оптимальное решение.

Для программной реализации поиска оптимального решения была выбрана форма представления задачи в виде задачи о ранце. Она удобна тем, что оперирует понятиями, имеющими аналоги в структурах данных в языках программирования высокого уровня. Так, например, решение задачи о ранце — это вектор, который легко представляется в виде одномерного массива. А сам алгоритм обработки векторов и поиска оптимального решения хорошо представляется в виде рекурсии. В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия). Это связано с тем, что алгоритм обработки векторов решений одинаков для каждого вектора, поэтому достаточно лишь каждый раз передавать в качестве параметра новый вектор. Подробное описание программной части описано в разделе «СОЗДАНИЕ ПРОГРАММЫ RANEC».

3. Решение задачи с использованием Excel

В данной работе для решения задач линейного программирования использовался программный продукт Microsoft EXCEL.

Для начала было необходимо ввести исходные данные для решения задачи. Следуя инструкции, представленной в методическом пособии по решению задач линейного программирования в EXCEL, была составлена форма, представленная на рисунке 1. [2]

Рисунок 1. Лист с исходными данными Входными данными являются производительность станков, стоимость, а также площадь цеха. Также на данной форме задаем целевые функции L1 и L2, выражая их через значения, записанные в ячейках таблицы.

Ниже приведены значения целевых функций и ограничения:

Для нахождения решения задач ЛЦП использовался встроенный инструмент «поиск решения». Данный инструмент позволяет решать задачи ЛЦП различными методами, в том числе симплекс-методом. Окно данного инструмента приведено на рисунке 2.

В поле «оптимизировать целевую функцию» вводится имя ячейки, в которой задана целевая функция. В поле «изменяя ячейки» переменных вносит имена ячеек, соответствующие переменным x1 — x7, соответствующие количеству станков каждого типа.

Рисунок 2. Окно инструмента «поиск решения»

В поле «в соответствии с ограничениями» вводим ограничение по площади цеха, а также устанавливаем требование цело численности для ячеек, соответствующих переменным x1 — x7, т. к. количество станков не может быть дробным числом. После чего выбираем опцию «найти решение» и в ячейках, соответствующих целевой функции и управляемым переменным получим решение задачи ЛЦП. [2]

Используя данный алгоритм, мы находим решения задач (4), (5), (6) и (7). Они приведены ниже.

Решение:

4)

Решение:

6)

Решение:

7)

Решение:

Таким критерий L1 изменяется в промежутке от 0 до 2460, а критерий L2 изменяется в промежутке от 0 до 246,1.

Для нахождения границы области изменения критериев разобьем промежуток изменения критерия L1 на интервалы длинной в 240 ед. и будем решать задачи вида (8) и (9) для каждой точки.

Результаты решения данных подзадач в EXCEL представлены на рисунке 3.

Рисунок 3. Результаты нахождения точек — границ области изменения критериев L1 и L2

На рисунке 4 представлено графическое отображение границы изменения критериев.

Рисунок 4. Область изменения критериев L1, L2

Методом обхода конусом, находим точки, принадлежащие области Парето. Список данных точек представлен в таблице 1.

Таблица 1. Множество Парето-оптимальных точек

Расположение Парето-оптимальных точек в области изменения критериев, представлено на рисунке 5.

Рисунок 5. Расположение Парето-оптимальных точек в области критериев На следующем этапе нам необходимо найти единственное решение задачи. Для этого мы составили новую целевую функцию. Теперь решаем задачу ЛЦП для данной функции, включив выражения для L1 и L2 в ограничения. Результаты решения представлены в таблице 2.

Таблица 2. Результаты поиска оптимального решения

Так как, коэффициенты вес компоненты критерия L1=50, а L2=1, то оптимальным решением выбирается то, которое обеспечивает максимум по критерию L1.

Таким образом оптимальным решением задачи является заполнение площади цеха 12-ю станками 6-го типа и 6-ю станками 7-го типа.

4. Создание программы Ranec

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

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

Для унификации представления данных и работы с ними были созданы два класса: Vector и Ranec. Их листинги представлены в приложении к работе. В данных классах описаны параметры, характеризующие соответственно вектор решений и ранец, а также включают в себя методы — набор типизированных действий, производящихся над вектором решений над данными типами. Например, в классе вектор описаны методы проверки вектора решений на неравенство нулю всех его составляющих, нахождения рекорда для вектора, нахождения индекса последнего ненулевого элемента и пр. Основными методами класса вектор являются метод, который упорядочивает компоненты по удельному весу, метод нахождения лексикографического максимального вектора для данной задачи.

Основным методом программы является метод класса Ranec — Solution, осуществляющий алгоритм поиска решения задачи. На вход метода подаются параметры: текущий вектор, рекорд и оценка. После этого происходит обработка вектора в соответствии с алгоритмом задачи о ранце и поученные новые вектор, рекорд и оценка передаются в качестве параметра в данный метод. Метод прекращает свою работу, когда на вход поступает вектор со всеми нулевыми компонентами.

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

1. Ввод данных. Создание экземпляра класса Ranec с введенными данными для текущей задачи.

2. Упорядочиваем векторы по удельному весу.

3. Запускаем метод Solution для лексикографически максимального вектора.

4. Отображение результата работы программы на экране.

На рисунках 6 и 7 представлен процесс работы программы и вывод на экран рекорда.

Рисунок 6. Процесс работы программы Рисунок 7. Окончание работы, вывод рекорда

5. Трактовка полученного результата

По итогам решения на EXCEL были получены следующие результаты:

Для оптимального размещения станков с учетом их производительности и стоимости оборудования, необходимо разместить в цехе 12 станков 6-го типа и 6 станков 7-го типа. Такое размещение станков дает максимальное значение производительности, а т. к. данный критерий имеет вес 50, а критерий стоимости имеет вес 1, то максимум целевой функции достигается именно при таком размещении и данное решение является единственно верным.

Список источников

1. Есипов Б. А. Методы исследования операций: Учебное пособие. Ї СПб.: Издательство «Лань», 2010. Ї 256 с.: ил. Ї (Учебники для вузов. Специальная литература).

2. Методическое пособие по использованию EXCEL — СГАУ им. академика Королева С. П., 1996. Ї 14 с.

3. Статья «Задача о рюкзаке. А что же внутри?» — http://habrahabr.ru/post/93 698/ - 2010. — 1 с.