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

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

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

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

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

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

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

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

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

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

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

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

Практическое задание № 6. Задача об изготовлении стержней

Задание. Определить варианты и возможности изготовления деталей определенных размеров из целых заготовок.

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

Решить задачу методом Ньютона с помощью «Поиска решения» программы МS ЕХСЕL:

1. По последней цифре номера зачетной книжки (или студенческого билета) выбрать номер варианта из табл. 6.1.

Таблица 6.1

№ ва-риан-та	Количество способов разрезания заготовки	Количество комплектов деталей требуемой длины, шт	Заготовки		Детали
			материал	длина, м	требуемые длины, м
0	9	100	арматура	8,0	1,5	1,6	1,7
1	4	90	доски	6,0	1,9	1,7	2,5
2	5	80	трубы	7,0	1,4	2,9	3,8
3	6	70	бревна	4,5	2,1	2,3	0,7
4	7	60	уголок	6,4	2,4	2,6	2,5
5	8	50	швеллер	4,4	1,8	1,5	2,1
6	7	40	доски	6,4	2,4	1,5	0,9
7	6	100	арматура	6,5	1,7	2,4	2,3
8	5	85	трубы	5,5	2,1	2,7	2,2
9	6	70	двутавр	7,2	3,9	2,1	2,4

2. Продумать метод разрезания заготовки из материала.

3. Построить математическую модель.

4. Заполнить пустые ячейки табл. 6.2. Размер таблицы зависит от номера варианта. Количество столбцов этой таблицы соответствует указанному количеству способов разрезания заготовки.

Таблица 6.2

Способы разрезания	1	2	3	4	5	6	7	8	9
Длина 1
Длина 2
Длина 3
Длина 4
Длина n
Сумма отрезков
Остаток

5. Построить макет на листе MS EXCEL, при этом подписывая все исходные данные, т.е. поясняя, в какой ячейке находится то или иное значение.

6. Вписать в ячейки нужные формулы для расчета суммы отрезков, подсчета остатка.

7. Написать формулу для целевой функции.

8. Получить решение задачи и сделать соответствующие выводы.

Работа рассчитана на 1 аудиторный час.

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

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

Постановка задачи об изготовлении стержней

Изготовление стержней заключается в разрезании исходной заготовки на отрезки заданной длины.

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

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

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

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

Пример 6. Производственное предприятие изготавливает металлические стержни трех видов фиксированной длины: 2,9 м, 2,1 м и 1,5 м. Для изготовления этих стержней поступает партия заготовок исходного материала, который также представляет собой металлические стержни длиной 7,4 м. Способ изготовления стержней заключается в разрезании исходной заготовки на отрезки заданной длины.

Рассмотрим шесть способов разрезания указанных отрезков, например, как показано в табл. 6.3. В последней, седьмой, строке указаны остатки, полученные при разрезании стержня длиной 7,4 м на отрезки требуемых длин, размеры которых указаны во 2-й, 3-й, 4-й и 5-й строках табл. 6.3.

Таблица 6.3

Способы разрезания	1-й	2-й	3-й	4-й	5-й	6-й
Длина 1	2,9	2,9	2,1	2,9	2,1	2,9
Длина 2	1,5	2,9	2,1	2,1	1,5	2,1
Длина 3	1,5	1,5	1,5	2,1	1,5	1,5
Длина 4	1,5	0	1,5	0	1,5	0
Сумма отрезков	7,4	7,3	7,2	7,1	6,6	6,5
Остаток	0	0,1	0,2	0,3	0,8	0,9

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

Из стержня длиной 7,4 м можно, например, изготовить один комплект деталей, длины отрезков которых соответственно равны 2,9; 2,1; 1,5 м. Остаток после разрезания стержня будет равен 0,9 м.

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

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

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

Исходными переменными математической модели задачи об изготовлении стержней являются x_i – количество исходных заготовок, разрезанных i-м способом для изготовления отдельных деталей. Математическая постановка данной задачи может быть записана в виде:

,

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

(6.1)

т.к. из табл. 6.3 видно, что размер 2,9 м для х₁ встречается один раз, для х₂ – два раза, для х₃ и х₅ не выбираются, х₄ и х₆ – один раз. Отрезков длиной 2,9 м выбирают не меньше 100 штук. Получаем первое неравенство системы. Точно также рассматриваем отрезки длиной 2,2 м и 1,5 м. Получаем следующие два неравенства. Значения не могут быть отрицательными числами, поэтому четвертое неравенство системы показывает, что каждое значение x_i больше или равно нулю. Предлагается коэффициенты при x_i первоначально выбрать равными единице и полагать x_i целыми.

Математическая модель (6.1) относится к классу задач целочисленного линейного программирования, которая может быть решена с помощь MS EXCEL.

Решение задачи об изготовлении стержней с помощью MS EXCEL

Для решения данной задачи с помощью программы МS ЕХСЕL создать новый лист. Переименовать в «Изготовление стержней». Выполнить подготовительный этап для решения - создать макет листа для исходных данных (рис. 6.1).

Для удобства и наглядности в ячейки А10:A16, B10:G10, H10, I10, H13 внести необходимый текст, ячейки В13 и G13 объединить и также внести текст в полученную ячейку. Текст не влияет на решение рассматриваемой задачи.

В ячейки B12:G12 ввести единицы – значения целевой функции.

В ячейке H11 разместить формулу для целевой функции:

=СУММПРОИЗВ(B11:G11;B12:G12).

Рис. 6.1.

Ячейки B11:G11 оставить незаполненными, в них будут размещены значения, являющиеся результатом решения задачи.

В ячейку Н14, используя Мастер функций, ввести формулу:

=СУММПРОИЗВ($B$11:$G$11;B14:G14).

Эту формулу скопировать в ячейки Н15: Н16.

Вызвав мастер поиска решения из меню Сервис – Поиск решения, установить в появившемся диалоговом окне целевую функцию, указав изменяемые ячейки и ограничения (рис. 6.2). Заполнить необходимые данные в параметрах поиска решения, указав Линейная модель – Неотрицательные значения (рис.6.3).

Рис. 6.2

Рис. 6.3

Выполнить Поиск решения - нажать предварительно ОК в окне Параметры поиска решения и получить решение (рис. 6.4).

Рис. 6.4

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

х₁ = 30, х₂ = 10, х₃ = 0, х₄ = 50, х₅ = 0, х₆ = 0,

которым соответствует значение целевой функции – f_орт = 90.

Вывод. Из имеющихся заготовок для изготовления 100 комплектов деталей требуемых длин следует первым способом разрезать 30 стержней, вторым способом – 10 стержней и четвертым способом – 50 стержней. Общее число израсходованных заготовок будет равно 90, что является минимальным из всех возможных вариантов разрезания исходных заготовок.