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

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

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

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

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

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

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

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

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

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

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

Таблица 6.3

Необходимо из имеющихся исходных заготовок изготовить 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, что является минимальным из всех возможных вариантов разрезания исходных заготовок.

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

1. Какая типовая задача оптимизации положена в основу задачи об изготовлении стержней?

2. К какому классу задач относится задача об изготовлении стержней и почему?

3. С помощью какой модели решаются задачи этого класса?

4. Что является исходными переменными математической модели задачи об изготовлении стержней?

5. Какой вид имеет математическая постановка данной задачи?

6. Какая система ограничений типа неравенств формирует множество допустимых альтернатив решения задачи?

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