Менеджмент

Учебная работа. Формування виробничого плану випуску продукції

Формування виробничого плану випуску продукції

Міністерство освіти і науки України

Київський національний університет будівництва і архітектури

Кафедра інформаційних технологій

КУРСОВА робота

з дисципліни

«Математичні методи дослідження операцій»

на тему:

«Формування виробничого плану випуску продукції«

Виконала студентка групи ПНК-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

Вхідний файл:

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

Вихідний файл:

(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

Вхідний файл:

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

Вихідний файл:

(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

Вхідний файл:

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

Вихідний файл:

(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. Дослідження розробленої програми для великих розмірностей

(-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] <&gtactiveXthen 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]: =’<';

‘<': 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] value1) then: =abs (d [j] / (a [i0,j]));: =j; {zapusyemo nomer stovbchika}_st: =true;;;pererah; {pererahovyemo matrucy}, j: integer;j: =0 to m doj<>j0 theni: =1 to n doi<>i0 then[i,j]: =a [i,j] — (a [i0,j] *a [i,j0] /a [i0,j0]);[j]: =d [j] — (a [i0,j] *d [j0] /a [i0,j0]);;j: =0 to m doj<>j0 then a [i0,j]: =a [i0,j] /a [i0,j0]; {rozrahynok napr. stoku}i: =1 to n doi<>i0 then a [i,j0]: =0; {rozrahynok napr. stovb. }[j0]: =0;[i0,j0]: =1;[i0]: =j0; {zapis nomera stovb. };simpl: boolean; {}: =true;napr_str (i0) donapr_st (i0,j0) then;;: =false;;;;

{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 ‘);;(‘) ‘);.