Задачи раскроя.

Широкое применение рационального раскроя промышленных материалов как важнейшего источника экономики материальных ресурсов составляет одну из наиболее важных задач промышленных предприятий. Опыт показал, что рацион раскрой обеспечивает повышение коэффициента использования длинномерных материалов (прутков, труб, круг леса, досок) на 2-5%, а листовых (фанера, листов стали) на 3-7%.

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

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

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

Математическая модель прямолинейного раскроя.

i – виды заготовок (i=1 m) – A, B, C.

b_i – необходимое количество i-ых заготовок

j – варианты раскроя

a_ij – количество заготовок i-го вида раскрываемых по j-му варианту из единицы исходного материала

x_j – количество исходного материала, раскраиваемых по j-му варианту

c_j – отходы от единицы исходного материала, раскраиваемых по j-му варианту

L – показатель эффективности (суммарные отходы)

Найти min L= при условии , x_j

ПРИМЕР 2.3.

Листы материала размером нужно раскроить так, чтобы получились заготовки типа А - 40 штук размером , а также В – 400 шт размером .

Возьмем 4 способа раскроя, определим отходы от каждого способа

j=1 j=2

отходы c₁=12 c₂=2

j=3 j=4

c₃=4 c₄=0

По результатам анализа вариантов раскроя составим таблицу

заготовки	способы раскроя aij
	J=1	j=2	j=3	j=4
A=40 B=400	3 1	2 6	1 9	0 13
отходы	12	2	4	0

Математическая модель

х_j – количество заготовок, раскраиваемых по j-способу

3 x₁+2x₂+x₃ 40

x₁+6x₂+9x₃+13x₄ 400

x _j 0

L=12x₁+2x₂+4x₃ Þmin

2.Основная задача линейного программирования (озлп)

Рассмотрим основную задачу линейного программирования (ОЗЛП):

Найти неотрицательные значения переменных x1 , x2 , …, xn , которые удовлетворяли бы условиям-равенствам

и обращали бы в максимум линейную функцию этих переменных:

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

ПРИМЕР 2.4.

Студенту, чтобы получить зачет, необходимо набрать не менее 60 баллов. Ему предлагаются задания двух видов, минимальная оценка которых 6 и 12 баллов соответственно. Общее количество заданий 14. На каждое задание 1–ого вида он тратит в среднем 2часа, а 2-ого вида – 3 часа. Требуется минимизировать время сдачи зачета.

Введем дополнительные неотрицательные переменные x₃, x₄ . Получим следующую систему ограничений:

Назовем допустимым решением ОЗЛП неотрицательное решение x=(x₁ , x₂ , …, x_n), удовлетворяющее заданным условиям . Множество допустимых решений назовем областью допустимых решений (ОДР). Оптимальным назовем решение x из допустимой области, которое обращает в максимум целевую функцию L.

Среди переменных, соответствующих элементам решения, различают базисные и свободные. Пусть m – число независимых уравнений в системе ограничений, n – число переменных. Тогда количество базисных переменных равно m, остальные переменные являются свободными r=n-m.