Задание № 10 на контрольную работу по дисциплине «Моделирование и прогнозирование» (стр. 1 )

Федеральное агентство по образованию

Юргинский технологический институт

Томского политехнического университета

Кафедра информационных систем

Задание № 10

на контрольную работу по дисциплине

«Моделирование и прогнозирование»

I. 1. Оптимальный раскрой материалов.

Исходные данные: имеется N вариантов раскроя листового материала заданных размеров. Из таких листов необходимо получить Bi заготовок i-го типа. Aij – количество заготовок i-го типа, получаемых из одного листа, раскроенного по j-му варианту. Сj –отходы материала от одного листа при j-м варианте раскроя.

Требуется: определить количество листов Xj, подлежащих раскрою по j-му варианту, чтобы суммарные отходы материала были минимальными. Результат должен быть целочисленным.

Построить соответствующую экономико-математическую модель.

РЕШЕНИЕ:

Хj – количество листов подлежащее j-му варианту раскройки

Сj – отходы при j-м варианте раскроя

Тогда суммарные отходы будут:

В условии опущено какое число типов заготовок надо произвести. (поэтому предполагаем что всего надо M типов заготовок (i=1..m))

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

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

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

L = -x1+2x2 ® max при условиях:

ì х1- 8х2£ 10,

í х1+ х2 ³ 1,

ï х1- 5х2 ³ -5, Составить двойственную к данной

î 3x1 +10x2 £ 30, задачу.

x1, х2 ³ 0.

РЕШЕНИЕ:

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

X1<=0 X1>=0

Х2>=0 Х2>=0

X1<=0 X1>=0

Х2<=0 Х2<=0

Отображаем на плоскости прямые соответствующие границам неравенств:

Графически отображаем прямые, отвечающие границам неравенств:

Полностью заштрихуем ту область, где неравенства выполняются. Это и будет нашей допустимой областью АВСD (область допустимых значений)

Проведем через начало координат прямую, соответствующую прямой функции цели:

L = -x1+2x2 =0

Х2=х1/2

(0; 0) (4;; -2)

Параллельно переносим прямую L(x1,x2) до последнего пересечения с областью ABCD,

Как видно из графика если переносить прямую влево, то точка последнего пересечения будет т. А(0; 1)

Если переносить вправо то т С(10;0)

Рассмотрим значения целевой функции в этих точках:

L(A)=L(0;1)=-0+2*1=2

L(C)=L(10;0)=-10

Так как по условию задачи требовалось найти максимальное значение функции, то Lmax= L(A)=2

Двойственная задача к прямой:

Прямая:

Преобразуем прямую задачу:

Тогда двойственная к ней будет:

3. Найти решение транспортной задачи, исходные данные которой определяются таблицей:

Пункты	Пункты назначения
отправления	В1	В2	В3	В4	В5	Запасы
А1	5	8	7	2	1	220
А2	6	3	5	4	6	140
А3	7	4	2	3	2	160
Потребности	80	140	90	130	80	520

Первоначальный опорный план составить по методу северо-западного угла.

РЕШЕНИЕ:

Так как суммарные запасы и потребности совпадают, то задача закрытого типа.

Находим допустимый план методом «Северо-западного угла»:

Пункты	Пункты назначения
отправления	В1	В2	В3	В4	В5	Запасы
А1	5 80	8 140	7 ---	2 ---	1 ---	220
А2	6 ---	3 0	5 90	4 50	6 ---	140
А3	7 ---	4 ---	2 ---	3 80	2 80	160
Потребности	80	140	90	130	80	520

Х11=min{80; 220}=80

X12=min{140; 220-80}=140

X23=min{90; 140}=90

X24=min{130; 140-90}=50

X34=min{130-50; 160}=80

X35=min{80; 160-80}=80

Весь груз перевезен.

Транспортная работа:

F= 5*80+8*140+5*90+4*50+3*80+2*80=2570 т*км

Проверим найденный план на оптимальность методом потенциалов.

Для проверки необходимо что бы было заполнено не менее (n+m)-1 = 3+5-1=7 ячеек. Так как заполнено только 6, то план является вырожденным и его надо доопределить. Поэтому в одну из пустых ячеек помещаем 0 перевозку и считаем эту ячейку заполненной.

Условная перевозка в ячейку (2;2)

Для данного плана рассчитаем условия потенциальности, для этого заполним таблицу:

Занятые ячейки	Свободные ячейки
U1+V1=5 U1+V2=8 U2+V2=3 U2+V3=5 U2+V4=4 U3+V4=3 U3+V5=2	Δ1,3 = c1,3 - (u1 + v3) Δ 1,4 = c1,4 - (u1 + v4) Δ 1,5 = c1,5 - (u1 + v5) Δ 2,1 = c2,1 - (u2 + v1) Δ 2,5= c2,5 - (u2 + v5) Δ 3,1 = c3,1 - (u3 + v1) Δ 3,2= c3,2 - (u3 + v2) Δ 3,3 = c3,3 - (u3 + v3)

Найдем чему равны потенциалы. Предполагаем U1 =0

Занятые ячейки	Свободные ячейки
U1=0 V1=5 V2=8 U2=3-8=-5 V3 =5+5=10 V4=4+5=9 U3 =3-9=-6 V5 =2+6=8	Δ1,3 = 7- (0 + 10)= -3 <0 Δ 1,4 = 2 - (0 + 9)= -7 <0 Δ1,5 = 1 - (0 +8)= -7 <0 Δ 2,1 = 6 - (-5 + 10)= 1 >0 Δ 2,5 = 6 - (-5 + 8)= 3 >0 Δ 3,1 = 7 - (-6 + 10)= 3 >0 Δ 3,2= 4- (-6 + 8)= 2 >0 Δ 3,3 = 2 - (-6 + 10)= -2 <0

Происходит нарушение потенциальности в четырех ячейках, поэтому план не оптимальный. Необходимо перераспределить груз через ячейку (1;4), так как в ней происходит большее нарушение