Материал: 4708

2. Составление математической модели Рассмотрим самую простую задачу, когда имеется неограниченное коли-

чество пиломатериалов одного типа и требуется составить оптимальный (обеспечивающий минимальные затраты пиломатериалов) план раскроя для выпиловки заданного количества заготовок нескольких типов. Предположим, что схемы раскроя для условий такой задачи составлены. Примем за неизвестные величины количество стандартных заготовок, раскраиваемых по одной схеме раскроя. Обозначим каждое искомое число буквой xi (i=1,2,…,m). Индекс i определяет схему раскроя, m – общее количество схем раскроя. Количество заготовок j-го вида обозначим Bj (j=1,2,…,n). Индекс j обозначает тип заготовки. Каждой схеме раскроя соответствует свой набор заготовок. Количество заготовок j-го типа, получаемое из доски, раскраиваемой по i-той схеме, обозначается bij. Запишем исходные данные в матричной форме (табл. 12).

33

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

b11X1 ... bi1 Xi ... bm1 X m B1;

b1n X1 ... bin Xi ... bmn Xm Bn .

Цель задачи – минимальный расход древесины можно записать так:

X1 X 2 X3 ... X m min .

В более строгой форме написанную задачу можно сформулировать так: требуется найти m переменных ( X1,..., X m ), которые минимизируют линейную функцию.

где i – номер схемы раскроя;

xi – количество досок раскраиваемых по i-той схеме; j – тип заготовок;

Bj – количество заготовок j-го типа, заданное по спецификации;

34

bij – количество заготовок j-го типа, выкраиваемых по i-той схеме рас-

кроя.

3. Составление оптимального плана раскроя с помощью симплекс-метода Добавим к условиям примера, рассмотренного выше, ограничения по количеству заготовок каждого типа. Пусть требуется напилить заготовок первого типа 300 штук, второго типа – 400 штук и третьего типа 300 штук. Требуется составить оптимальный план раскроя. Сведем исходные данные и результаты расчетов для приведенного примера и вышеуказанные ограничения по количе-

ству заготовок в табл. исходных данных 13.

35

Запишем условия задачи в виде

12X1 0X2 0X3 4X4 8X5 4X6 8X7 0X8 0X9 0X10 4X11 300; 0X1 15X 2 0X3 10X 4 5X5 0X 6 0X 7 5X8 10X9

15X10 5X11 400;

0X1 0X 2 32X3 0X 4 0X5 24X 6 8X 7 24X8 16X98X10 16X11 800.

(23)

X 0

Целевая функция

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 min .

Разделив правую и левую часть первого уравнения на 12, второго уравнения на 15 и третьего уравнения на 32, приведем систему уравнений (22) к каноническому виду

Для удобства решения целевую функцию преобразуем к виду

X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 max .

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

Чтобы найти элементы индексной строки, нужно все элементы столбца, соответствующего каждой переменной, умножить на соответствующие оценки