Учебная работа. Формування виробничого плану випуску продукції
Формування виробничого плану випуску продукції
Міністерство освіти і науки України
Київський національний університет будівництва і архітектури
Кафедра інформаційних технологій
КУРСОВА робота
з дисципліни
«Математичні методи дослідження операцій»
на тему:
«Формування виробничого плану випуску продукції«
Виконала студентка групи ПНК-41 Леонченко А.О.
Керівник роботи: Бабич В.І.
Київ 2010 р.
Зміст
Вступ
1. Постановка задачі
2. Розробка математичної моделі
3. Вибір та обґрунтування методів рішення задачі
4. Алгоритм двоїстого симплекс-методу рішення задачі та опис програми
5. Ітерації програмного рішення задачі
6. алгоритм методу симплекс-таблиць рішення задачі
7. Висновок та дослідження на чутливість моделі
8. Дослідження розробленої програми для великих розмірностей
Список використаної літератури
Вступ
Дослідження операцій — це наука про моделі і методи оптимального управління, а також про систему прийняття рішень з допомогою оптимального управління. [1,7]
В даному курсовому проекті використовується метод лінійного програмування двоїстий симплекс.
Лінійне програмування — розвязує задачі подані лінійними моделями, тобто ті, які мають лінійну цільову функцію (ЦФ) та лінійну область допустимих рішень (ОДР.).
1. Постановка задачі
У районі лісового масиву діють лісопильний завод і фабрика, на якій виготовлюють фанеру. Щоб одержати 2,5 м3 комплектів пиломатеріалів, треба витратити l1 м3 ялинових і r1 м3 пихтових лісоматеріалів. Для готування 100 м2 фанери потрібно l2 м3 ялинових і r2 м3 пихтових лісоматеріалів. Лісовий масив містить E м3 ялинових і Р м3 пихтових лісоматеріалів. Протягом планованого періоду необхідно зробити принаймні Q1 м3 пиломатеріалів і Q2 м3 фанери. 1 м3 пиломатеріалів дає D1 грн., а 100 м2 фанери — D2 грн. прибутку
Яка кількість пиломатеріалів і фанери потрібно зробити, щоб прибуток був максимальним?
Номер варіантаL1ρ1l2ρ2ЕPQ1Q2D1D232,67,55,18,590200910002050
2. Розробка математичної моделі
— пиломатеріали (м3)
— фанера (м2)
3. Вибір та обґрунтування методів рішення задачі
Дану задачу можна вирішувати наступними методами:
·Двоїстий симплекс-метод (програмую)
Є ряд задач лінійного програмування, які можуть бути розвязані тільки двоїстим симплекс-методом, наприклад деякі задачі мінімізації. Для кожної моделі існує поняття двоїстої задачі, тобто запис задачі іншими змінними для розвязання потім іншим методом, який потрібний для перевірки правильності симплекс-методу та інших методів ЛП.
Метод базується на постійному поліпшенні умови недопустимості розвязку. На його основі створена програма double. exe. Якщо в прямому симплекс-методі алгоритм базується на постійному покращенні значенні цільової функції, тобто значення симплекс-таблиці, то в ДСМ алгоритм — на постійному вилученні розвязку, тобто всі базисні змінні в кінці xn є Bx, xn<=0, стануть позитивними.
·Симплекс-метод
Даний метод базується на табличних перетвореннях Джордана-Гауса моделі, поданої в канонічному вигляді. метод симплекс-таблиць або метод переміщення по кутах (по симплексах) має в основі ітераційний розрахунок з максимально можливою кількістю ітерацій:
С=m! /n! (m-n!)
де C — максимально можлива кількість ітерацій (умова перевірки на зацикленість);
n — кількість рівнянь;
m — кількість змінних у канонічному вигляді.
Симплекс-метод базується на постійних перетвореннях таблиці:
виробничий план симплекс двоїстий
Симплекс-метод
1 2 3 . nCx Bx A0 A1. Am 0 1. m
де: Bx — базисні змінні;
Cx — коефіцієнти цільової функції при базисних змінних;
симплекс різниця;
A1. Am — коефіцієнти в обмеженнях;
A0 — права частина.
Кожна ітерація полягає в заміні (перерахунку) базисної змінної.
4. алгоритм двоїстого симплекс-методу рішення задачі та опис програми
1. Зведення ЦФ до максимуму, а обмежень до рівностей (канонічний вигляд).
. Запис двоїстої задачі
. Побудова незалежних векторів на підставі рядків ДЗ.
. Вибір спряженого базису:
üДовільний вибір m рівнянь;
üРозвязання цієї системи m з рівнянь;
üПідстановка розвязку в кожне із залишених обмежень та перевірка: чи задовольняє спряжений базис;
üЯкщо спряжений базис задовольняє, то формування псевдолану (розрахунок симплекс-таблиці);
üЯкщо спряжений базис не задовольняє, то треба обрати новий. Якщо на генерації нових сполучень не буде знайдено спряжений базис, то немає розвязку.
Спряжений базис (А1А4А5А6)
. Заповнення симплекс-таблиці.
. Всі інші симплекс-перетворення в ДСМ аналогічні прямому СМ.
Рис. 1 алгоритм двоїстого симплекс-методу
5. Ітерації програмного рішення задачі
(C*) Leonchenko Anna. PNK-41
Условие считывается из файла
Вывод выполняется в файл
Размерность задачи 4×6:
(20×1+0.50×2+0x3+0x4+0x5+0x6)
{1} 1×1+0.05×2+1.04×3+0x4+0x5+0x6=86.53
{2} 0x1-0.06×2-3.12×3+1×4+0x5+0x6=-59.60
{3} 0x1+0.05×2+1.04×3+0x4+1×5+0x6=77.59
{4} 0x1-1×2+0x3+0x4+0x5+1×6=-1000
Опис процедур програми:value — «,» міняє на». ;
Procedure prov — Обрізання пробілів на початку та в кінці рядку;
Procedure error — недопустимий символ;
Function ReadData — зчитування з файлу;
Function Druk — перетворює real в integer, знаходить дробову частину, перетворює число в рядок;
Procedure WriteUmovu — вивід даних зчитаних з вхідного файлу;
Procedure vivod — вивід ітерацій;
Procedure RozDelta — розрахунок дельта та запис в симплекс-таблицю;
Function napr_str — визначення спрямовуючого рядка;
Function napr_st — визначення спрямовуючого стовпчика;
Procedure pererah — перерахунок симплекс-таблиці за формулою прямокутника;
Function simpl — перевірка.
. алгоритм методу симплекс-таблиць рішення задачі
1. Визначення спрямовуючого стовпчика j*
Якщо відсутнє, то розвязок знайдено: базисні змінні дорівнюють, а небазисні — 0
. Визначення спрямовуючого рядка і*
Якщо і* відсутнє, тобто в стовпчику знаходиться значення не більше 0, то розвязок відсутній (ОДР не обмежена зверху), інакше фіксуємо спрямовуючий елемент: (2 1) =1
. Перерахунок таблиці (власне заміна базисних змінних):
·ділення значень спрямовуючого рядка на спрямовуючий елемент:
·обнулення спрямовуючого стовпця, крім спрямовуючого елемента:
·перерахунок решти значень за формулою прямокутників:
4. Перевірка ітерації:
·цільова функція має не зменшуватися;
·номер ітерації має не перевищувати їхню максимальну кількість:
·базисні змінні мають мати одиничний вектор;
·розрахунок має співпадати як за формулою спрямовуючого стовпчика, так і за формулою «прямокутника».
Розвязок знайдено, тому що всі 0. Після розрахунку потрібно виконати наступну перевірку:
·чи всі М-змінні дорівнюють 0 якщо ні, то розвязок відсутній або ж вибрано занадто малий коефіцієнт m.
·Значення Z має дорівнювати значенню Ci Xi
Рис. 2 алгоритм симплекс-методу
Канонічна форма, розмірність 4*8
Ітерації рішення задачі вручну.
Размерность задачи НЛП — 4 х 8
(20X1 +0.5X2-200X6-200X8)
{1} 1.04X1 + 0.051X2 + 1X3 = 90
{2} 3X1 + 0.085X2 + 1X4 = 200
{3} 1X1 + — 1X5 + 1X6 = 9
{4} 1X2 + — 1X7 + 1X8 = 1000
7. Висновок та дослідження на чутливість моделі
Модифікація вхідних значеньПошукові xіЦільова функція ZПримітка1Лісовий масив складається з Е=100м3 Р=250м3L1=2,6 L2=5,1 P1=7,5 P2=8,5 E=100 P=250 Q1=9 Q2=1000 D1=20 D2=0,51520Зі збільшенням площі лісового масиву сумарний прибуток заводу збільшуються. 2Прибуток приносять: Пиломатеріали D1=30грн Фанера D2=2грнL1=2,6 L2=5,1 P1=7,5 P2=8,5 E=100 P=250 Q1=9 Q2=1000 D1=30 D2=33125,90Сумарний прибуток збільшуються. 3 Якщо використовувати менше ялинових лісоматеріалів 1=2,5м3L1=2,5 L2=5,1 P1=7,5 P2=8,5 E=100 P=250 Q1=9 Q2=1000 D1=20 D2=0,51830,60Сумарний прибуток збільшуються, так як матеріал використовується менше.
Рішення інших задач
Приклад №1
Вхідний файл:
6
0.5 0 0 0 0
0.049 1.04 0 0 0 = 100
— 0.062 — 3.12 1 0 0 = — 40
0.049 1.04 0 1 0 = 77.59
— 1 0 0 0 1 = — 1000
Вихідний файл:
(c) Leonchenko Anna. PNK-41dlja zchityvannja
(20×1+0.50×2+0x3+0x4+0x5+0x6)
{1} 1×1+0.05×2+1.04×3+0x4+0x5+0x6=100
{3} 0x1+0.05×2+1.04×3+0x4+1×5+0x6=77.59
{4} 0x1-1×2+0x3+0x4+0x5+1×6=-1000
Приклад №2
Вхідний файл:
6
2 0 0 0 0
0.049 1.04 0 0 0 = 86.53
— 0.062 — 3.12 1 0 0 = — 59.6
0.049 1.04 0 1 0 = 77.59
— 1 0 0 0 1 = — 1000
Вихідний файл:
(c) Leonchenko Anna. PNK-41dlja zchityvannja
(30×1+2×2+0x3+0x4+0x5+0x6)
{1} 1×1+0.05×2+1.04×3+0x4+0x5+0x6=86.53
{2} 0x1-0.06×2-3.12×3+1×4+0x5+0x6=-59.60
{3} 0x1+0.05×2+1.04×3+0x4+1×5+0x6=77.59
{4} 0x1-1×2+0x3+0x4+0x5+1×6=-1000
Приклад №3
Вхідний файл:
6
0.5 0 0 0 0
0.02 1.04 0 0 0 = 86.53
— 0.062 — 3.12 1 0 0 = — 59.6
0.049 1.04 0 1 0 = 77.59
— 1 0 0 0 1 = — 1000
Вихідний файл:
(c) Leonchenko Anna. PNK-41dlja zchityvannja
(20×1+0.50×2+0x3+0x4+0x5+0x6)
{1} 1×1+0.02×2+1.04×3+0x4+0x5+0x6=86.53
{2} 0x1-0.06×2-3.12×3+1×4+0x5+0x6=-59.60
{3} 0x1+0.05×2+1.04×3+0x4+1×5+0x6=77.59
{4} 0x1-1×2+0x3+0x4+0x5+1×6=-1000
8. Дослідження розробленої програми для великих розмірностей
(c) Leonchenko Anna. PNK-41dlja zchityvannja
(-17×1-20×2-22×3-25×4-28×5-30×6+0x7+0x8+0x9+0x10+0x11)
{1} — 33×1+0x2-43×3+0x4-60×5+0x6+1×7+0x8+0x9+0x10+0x11=-1050
{2} 0x1-28×2+0x3-40×4+0x5-50×6+0x7+1×8+0x9+0x10+0x11=-600
{3} 1×1+1×2+0x3+0x4+0x5+0x6+0x7+0x8+1×9+0x10+0x11=5
{4} 0x1+0x2+1×3+1×4+0x5+0x6+0x7+0x8+0x9+1×10+0x11=15
{5} 0x1+0x2+0x3+0x4+1×5+1×6+0x7+0x8+0x9+0x10+1×11=15
Найбільша розмірність, яка може бути вирішена даним програмним продуктом складає матрицю розміром 50*50.
список використаної літератури
1. Бабич В.І. Конспект лекцій з дисципліни «Математичні методи дослідження операцій»
. Культин Н.Б. Программирование в Turbo Pascal 7.0 — Спб.: БХВ — Санкт-Петербург, 1999 — 240 с.
Додаток
Лістинг програми
program simplex;crt;=50;=50;, file_input, file_output, iter, zn_max: string;, res,fl: boolean;, k, n, m, j0, i0, i, j,nom_it: integer;: array [1. mmax] of real;: array [1. nmax,0. mmax] of real;: array [1. nmax] of byte;: array [0. mmax] of real;: array [1. nmax] of char;: char;
{ x: array [1. mmax] of real; }value (var s: string): string;: string;: integer;: =»;s [1] =’,’ then v: =v+’. ‘ else v: =v+s [1];(s,1,1);(s [1] =’ ‘) or (s=»);: =v;;prov (var s: string);s [1] =’ ‘ then(s,1,1);s [1] <>‘ ‘;s [length (s)] =’ ‘ then(s,length (s),1);s [length (s)] <>‘ ‘;;error (sub: string);(‘Недопустимий символ ‘);i: =1 to length (sub) dosub [i] of
‘A’. ‘Z’,’a’. ‘z’: write (‘буква ‘);
‘0’. ‘9’,’,’,’. ‘:;write (‘спеціальний символ ‘);;;;ReadData: boolean;: string;, i, j: integer;: =true;(input,file_input);(input);ioresult<>0 then(‘файл‘<+file_input+'>не найдено’);;;(s);(s);: =value (s);(sub, n, code);code<>0 then(‘Помилка: рядок 1-й число 1-ше ‘);: =false;(sub);;(s);: =value (s);(sub, m, code);code<>0 then(‘ Помилка: рядок 1-й число 2-ге ‘);: =false;(sub);;(n>nmax) or (m>mmax) then begin(‘Указана розмірність задачі не підходить обмеженням задачі’);: =false;;(s);(s);j: =1 to m do: =value (s);(sub, c [j], code);code<>0 then(Помилка: рядок 2-й’, j, ‘число);: =false;(sub);;(s);;_max: =value (s);i: =1 to n do(s);(s);j: =1 to m do: =value (s);(sub,a [i,j],code);code<>0 then(‘Помилка: рядок’, i+2,’-число ‘,j,’);: =false;(sub);;(s);;[i]: =s [1];(s,1,1);(znak [1] <>‘>’) and (znak [1] <>‘<') and (znak [1] <>activeXthen begin(‘Ошибка: рядок ‘, i+2,’ — й: не вірно вказаний знак‘);: =false;;(s);: =value (s);(sub,a [i,0], code);code<>0 then(‘Ошибка: рядок ‘, i+2,’ — й’,m+1,’оє: ‘);: =false;(sub);;;;kanon;: real;: =1;i: =1 to m domax ‘<': znak [i]: ='>‘;;;if (a [i,0] =0) and (znak [i] =’<') thenj: =1 to m do[i,j]: =-a [i,j];[i]: ='>‘;: =false;;znak [i] of ‘>’: begin(m);[m]: =0;[i,m]: =-1;j: =1 to n doi<>j then[j,m]: =0;; ‘<': begin(m);[m]: =0;[i,m]: =1;j: =1 to n doi<>j then[j,m]: =0;; ‘=’: begin(m);[m]: =0;[i,m]: =1;j: =1 to n doi<>j then[j,m]: =0;;;: =true;[iactiveXres=true);;druk (b: real; im: boolean): string;, s1: string;, i, j: integer;: =»;: =trunc (b);: =1;b<0 then(i);: =abs (cel);;cel div 10 >0 do: =cel div 10;(i);;frac (b) <>0 then: =i+3;(b: 4: 2,s);str (trunc (b), s);im then: =8-i;: =»;j: =1 to i do: =s1+’ ‘;: =s1+s;;: =s;;vivod;i,j: integer;(‘Iteracija #’,nom_it: 4);(‘———————————————————————‘);(‘———————————————————————‘);(‘Cil. funk ‘);i: =1 to m do(druk (c [i],true));(»);(‘——————————————————————‘);(»);(‘ Bx ‘);j: =0 to m do(‘ A’,j,’ ‘);(»);i: =1 to n do(druk (c [b [i]],true));(‘ X’,b [i]);(druk (a [i,0],true));j: =1 to m do(druk (a [i,j],true));(‘ ‘);;(‘——————————————————————‘);(‘R ‘);i: =0 to m do(druk (d [i],trueactiveXit: =nom_it+1;;WriteUmovu;, j: integer;;(‘ (c) Leonchenko Anna. PNK-41’);;(‘File dlja zchityvannja <'+file_input+'>‘);file_output=’con’ then(‘Vivid vukon na ekran’)writeln (‘Vivid vukon v file <'+file_output+'>‘);(‘Rozmirnist zadachi ‘, n, ‘x’, m, ‘: ‘);;(‘max (‘);j: =1 to m do(c [j+1] >=0) and (j<>m) then write (druk (c [j],false),’x’, jactiveXwrite (druk (c [j],false),’x’,j);(‘) ‘);i: =1 to n do(‘{‘, i,’} ‘);j: =1 to m do(druk (a [i,j],false),’x’,j);(a [i,j+1] >=0) and (j<>m) then write (‘+’);;(‘=’,druk (a [i,0],false));;file_output=’con’ then: =readkeykey=#13;;RozDelta; {rozraxynok delta}, j, k: integer;: boolean;i: =1 to n do {zapisyemo ne 0 elementu}j: =1 to m doa [i,j] =1 then: =false;k: =1 to n do(i<>k) then(a [k,j] =0) then pr: =truebegin pr: =false; break; end;pr thenb [i]: =j; break; end;;j: =0 to m do {podchet delta}j=0 then d [j]: =0 else d [j]: =-c [j];i: =1 to n do[j]: =d [j] +a [i,j] *c [b [i]];;;napr_str (var i0: integer): boolean; {vuznachennja napr-j stroku}: real;: integer;_str: =false;: =0;: =0;i: =1 to n do(a [i,0] {file_input: =’in. txt’;_output: =’out. txt’;: =true; }_input: =paramstr (1);_output: =paramstr (2);: =paramstr (3);;(file_input=») or (file_output=») then(‘Vvedit pravilno dani’);(‘DUOSIMPL. exe inputfile outputfile/con [Y/y] ‘);;;(iter=’Y’) or (iter=’y’) then it: =true;file_output<>‘con’ then(output,file_output);(output);;: =true;not ReadData then halt; {Kanon; };;;;_it: =1;;not simpl then {nema rishennja}(‘Rishen nemaje’);;(‘Rishennja znajdeno!!! Param-pam-pam’);(‘Z=’,druk (d [0],true));(‘X = (‘);i: =1 to m do: =false;j: =1 to m dob [j] =i then begin write (druk (a [j,0],false),’ ‘); fl: =true; end;fl=false then write (‘0 ‘);;(‘) ‘);.
Учебная работа. Формування виробничого плану випуску продукції