4. Задача о раскрое

Постановка задачи

На строительный объект поступает партия в 1000 листов стекла размером 1,5×1,3 м. Для остекления здания необходимы стекла размером в 1×0,5 м, 1×0,8 м, 1,5×0,5 м в отношении 2:3:5:8 (условие комплектности).

Составить план раскроя партии стекол, при котором будет получено максимальное количество комплектов.

1. Составим математическую модель задачи линейного программирования.

Рассмотрим последовательность рассуждений, которая приводит к составлению математической модели.

Для того чтобы определить понятие – план раскроя, составим все возможные способы раскроя одного листа. Способы представлены на рис. 7. Выход стекол нужного формата при различных способах раскроя сведем в табл. 9.

Таблица № 9

Количество форматных стекол, получаемых при возможных способах раскроя одного листа

Форматы стекол	Количество стекол при возможных способах раскроя
	а	б	в	г	д	е	ж
1×0,5	3	1	1	0	0	1	0
1×0,8	0	1	0	1	0	0	0
1,5×0,8	0	0	1	0	0	0	1
1,5×0,5	0	0	0	1	2	1	1

 

Рис. 7. Возможные способы раскроя одного листа партии заготовок

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

                                                                                       (3)

Тот факт, что раскроено должно быть ровно 1000 лиcтов, запишем в виде ограничения:

                                                             (4)

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

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

                                                                      (5)

Целевая функция (3) и система ограничений (5) совместно с ограничением (4) составляет математическую модель задачи.

5.Формирование задачи линейного программирования(лп)

Под словом "программирование" здесь и в дальнейшем будем по­нимать не написание программы, а составление алгоритма, планиро­вание. Основные идеи ЛП возникли во время войны в связи с поиском оптимальных стратегий при ведении военных операций. С той поры они начали широко использоваться в различных сферах человеческой деятельности, в том числе и в связи. Этими методами можно решить многие (хотя и не все) задачи, связанные с эффективным использованием ограниченных ресурсов.

В общем виде задача ЛП состоит в мак­симизации (или минимизации) линейной функции

F=c₁x₁+c₂x₂+…+c_nx_n

при условии, что переменные x_i имеют линейные ограничения вида

a₁₁x₁+a₁₂x₂+…+a_1nx_n ≤ (=, ≥) b₁

a₂₁x₁+a₂₂x₂+…+a_2nx_n ≤ (=, ≥) b₂

………………………………….

a_m1x₁+a_m2x₂+…+a_mnx_n ≤ (=, ≥) b_m

и x_i ≥0.

Значения b_i, c_j, a_ij предполагаются известными.

Существуют и другие формы записи задачи ЛП. Очень часто некоторые или все ограничения записываются в форме неравенств. Однако независимо от формы записи задача ЛП состоит из двух составных частей: формиро­вания линейной целевой функции и записи ограничений, записанных в виде линейных равенств или неравенств.

Задача ЛП может решаться с помощью ряда методов, носящих явно выраженный алгоритмический характер, что позволяет решать ее с помощью ЭВМ. Задачи меньшего объема мож­но решать теми же методами вручную с применением калькуляторов.

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

Существует несколько методов решения задач ЛП. Одним из них является графический.

Графический метод

Графический метод решения задач ЛП является наиболее простым и наглядным. Проиллюстрируем этот метод на примере.

Имеется 14 каналов радиорелейной связи и 10 каналов тропо­сферной. По ним необходимо передать информацию трех видов: А, Б и В. Причем информация А=300 условных единиц, Б=3000, В=5000 (под информацией можно понимать и число телефонных разговоров, передачу ' данных и пр.). Возможности каналов следующие:

	А	Б	В
Тропосферная связь	90	--	300
РРС	30	1000	1200

Затраты на обслуживание одного канала РРС - 1,5 тыс. рублей, а тропосферной связи - 2,5 тыс. рублей.

Требуется отыскать задействованное количество каналов обоих видов, необходимое для передачи требуемой информации, чтобы стои­мость эксплуатации была минимальной.

Решение.

Обозначим через x₁ количество каналов тропосферной связи, а через x₂ - количество каналов радиорелейной связи. Тогда функцию цели можно записать

F=2.5x₁+1.5x₂

Ограничения можно записать в следующем виде:

90x₁+30x₂≤300

x₁≥0,

1000x₂ ≤3000,

X₂≥0,

300x₁+1200x₂ ≤5000,

x₁≤10, x₂≤14

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

x₁=10, x₂=14

90x₁+30x₂=300

1000x₂ =3000,

300x₁+1200x₂ =5000,

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

Построим теперь на этом же рисунке целевую функцию. Для это­го произвольно предположим, что расходы на эксплуатацию состави­ли 4,5 тыс. руб. (эта произвольная цифра нужна для того, чтобы по­строить по двум точкам прямую). Как видно из рис. 2.1, прямая эта не пересекла область допустимых значений. Это говорит о том, что в данной задаче невозможно добиться таких расходов. Теперь предполо­жим, что расходы составили 6 тыс. руб. Новая прямая прошла парал­лельно первой и несколько приблизилась к области допустимых значе­ний (ОДЗ), по-прежнему не пересекая ее. Значит, расходы будут еще выше. Перенесем параллельно двум построенным прямым прямую до касания с первой точкой ОДЗ. Эта точка и будет оптимальной. Т.е. для того чтобы передать с наименьшими затратами требующуюся инфор­мацию, необходимо взять 2 канала первого типа и 4 канала второго типа. Стоимость в этом случае будет равна

2,5*2 + 1,5*4 = 11 тыс. руб.

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