РГР_тпр
.docМинистерство Образования Российской Федерации
Омский Государственный Технический университет
Кафедра автоматизированные системы обработки
информации и управления
Отчет по расчетно-графической работе по теме:
«Оптимальное распределение бумажных ресурсов»
Выполнил:
студент группы ИВТ-334
Сачков А.С.
Проверила:
Зыкина А.В.
Омск 2007
Содержание.
Задание…………………………………………………………………………….3
Математическая модель………………………………………….……………….4
Приведение к канонической форме……………………………………………...5
Решение……………………………………………………………………………6
Проверка…………………………………………………………………………...8
Задание.
Имеются три сорта бумаги в количествах а1, а2, а3, которую можно использовать на издание четырех книг тиражом b1, b2, b3, b4 экземпляров. Расход бумаги на одну книгу составляет с1, с2, с3, с4, а себестоимость печатания книги К при использовании i-го сорта бумаги задается матрицей ||Сik|| . Определить оптимальное распределение бумажных ресурсов.
Математическая модель.
Xij – количество книг j-го типа, сделанных с помощью i-го сорта бумаги.
i – сорт бумаги.
j – тип книги.
ai – количество i-го сорта бумаги.
bj – тираж j-й книги.
cj – расход на книгу j-го типа.
dij – себестоимость j-й книги, при использовании i-го сорта бумаги.
Ограничение по бумаге: Σ Хij*cj ≤ ai;
Ограничение по тиражу: Σ Xij ≥ bj;
Целевая функция: Σ dij*Xij min.
Пусть: а1=10; а2=12; а3=24.
b1=4; b2=1; b3=4; b4=6.
c1=6; c2=4; c3=2; c4=1.
d1=4; d2=5; d3=2; d4=3; d5=5; d6=1; d7=3; d8=6; d9=4; d10=2; d11=3;
d12=4.
Приведение к канонической форме.
Сделаем замену Xij = zi.
6z1+4z2+2z3+z4≤10;
6z5+4z6+2z7+z8≤12;
6z9+4z10+2z11+z12≤24;
z1+z2+z3≥4;
z4+z5+z6≥1;
z7+z8+z9≥4;
z10+z11+z12≥6;
4z1+5z2+2z3+3z4+5z5+z6+3z7+6z8+4z9+2z10+3z11+4z12 min.
0 – (-4z1-5z2-2z3-3z4-5z5-z6-3z7-6z8-4z9-2z10-3z11-4z12);
6z1+4z2+2z3+z4+y1=10;
6z5+4z6+2z7+z8+y2=12;
6z9+4z10+2z11+z12+y3=24;
z1+z2+z3-y4=4;
z4+z5+z6-y5=1;
z7+z8+z9-y6=4;
z10+z11+z12-y7=6.
0 – (-4z1-5z2-2z3-3z4-5z5-z6-3z7-6z8-4z9-2z10-3z11-4z12);
y1=10-(6z1+4z2+2z3+z4);
y2=12-(6z5+4z6+2z7+z8);
y3=24-(6z9+4z10+2z11+z12);
y4=-4-(-z1-z2-z3);
y5=-1-(-z4-z5-z6);
y6=-4-(-z7-z8-z9);
y7=-6-(-z10-z11-z12).
Так как целевая функция min и в столбце z0 имеются отрицательные числа, то для решения удобно воспользоваться двойственным симплекс-методом. Симплекс таблица будет оптимальной, если в столбце z0 будут неотрицательные числа. Ведущая строка выбирается максимальной по модулю, ведущий столбец – по минимальному отношению i-строки с целевой функцией.
Решение.
Шаг0:
|
B |
z0 |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
z10 |
z11 |
z12 |
|
y1 |
10 |
6 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y2 |
12 |
0 |
0 |
0 |
0 |
6 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
|
y3 |
24 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
4 |
2 |
1 |
|
y4 |
-4 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y5 |
-1 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y6 |
-4 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
y7 |
-6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
|
f |
0 |
-4 |
-5 |
-2 |
-3 |
-5 |
-1 |
-3 |
-6 |
-4 |
-2 |
-3 |
-4 |
Шаг1:
|
B |
z0 |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
y6 |
z8 |
z9 |
y7 |
z11 |
z12 |
|
y1 |
10 |
6 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y2 |
12 |
0 |
0 |
0 |
0 |
6 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
|
y3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
4 |
-2 |
-3 |
|
y4 |
-4 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y5 |
-1 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y6 |
-4 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
z10 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
|
f |
12 |
-4 |
-5 |
-2 |
-3 |
-5 |
-1 |
-3 |
-6 |
-4 |
-2 |
-1 |
-2 |
Шаг2:
|
B |
z0 |
z1 |
z2 |
z3 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
y7 |
z11 |
z12 |
|
y1 |
10 |
6 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y2 |
4 |
0 |
0 |
0 |
0 |
6 |
4 |
2 |
-1 |
-2 |
0 |
0 |
0 |
|
y3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
4 |
2 |
1 |
|
y4 |
-4 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y5 |
-1 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
z7 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
0 |
0 |
0 |
|
z10 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
|
f |
24 |
-4 |
-5 |
-2 |
-3 |
-5 |
-1 |
-3 |
-3 |
-1 |
-2 |
-3 |
-4 |
Шаг3:
|
B |
z0 |
z1 |
z2 |
y4 |
z4 |
z5 |
z6 |
z7 |
z8 |
z9 |
y7 |
z11 |
z12 |
|
y1 |
8 |
4 |
2 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y2 |
4 |
0 |
0 |
0 |
0 |
6 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
|
y3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
4 |
-2 |
-3 |
|
z3 |
4 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y5 |
-1 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
z7 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
z10 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
|
f |
32 |
-2 |
-3 |
-2 |
-3 |
-5 |
-1 |
-3 |
-6 |
-4 |
-2 |
-1 |
-2 |
Шаг4:
|
B |
z0 |
z1 |
z2 |
y4 |
z4 |
z5 |
y5 |
z7 |
z8 |
z9 |
y7 |
z11 |
z12 |
|
y1 |
8 |
4 |
2 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
y2 |
0 |
0 |
0 |
0 |
-4 |
2 |
4 |
2 |
1 |
0 |
0 |
0 |
0 |
|
y3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
4 |
-2 |
-3 |
|
z3 |
4 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
z6 |
1 |
0 |
0 |
0 |
1 |
1 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
z7 |
4 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
-1 |
-1 |
0 |
0 |
0 |
|
z10 |
6 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
-1 |
1 |
1 |
|
f |
33 |
-2 |
-3 |
-2 |
-2 |
-4 |
-1 |
-3 |
-6 |
-4 |
-2 |
-1 |
-2 |
Ответ: Z* = (0,0,4,0,0,1,4,0,0,6,0,0).
F* = 33.
Проверка.
0+0+8+0≤10;
0+4+8+0≤12;
0+24+0+0≤24;
0+0+4≥4;
0+0+1≥1;
4+0+0≥4;
6+0+0≥6;
ЦФ: 0+0+8+0+0+1+12+0+0+12+0+0=33.