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

Міністерство освіти і науки України Київський національний університет будівництва і архітектури Кафедра інформаційних технологій КУРСОВА РОБОТА з дисципліни

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

на тему:

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

Виконала студентка групи ПНК-41 Леонченко А.О.

Керівник роботи: Бабич В.І.

Київ 2010 р.

Зміст

• Вступ
• 1. Постановка задачі
• 2. Розробка математичної моделі
• 3. Вибір та обґрунтування методів рішення задачі
• 4. Алгоритм двоїстого симплекс-методу рішення задачі та опис програми
• 5. Ітерації програмного рішення задачі
• 6. Алгоритм методу симплекс-таблиць рішення задачі
• 7. Висновок та дослідження на чутливість моделі
• 8. Дослідження розробленої програми для великих розмірностей
• Список використаної літератури

Вступ

Дослідження операцій — це наука про моделі і методи оптимального управління, а також про систему прийняття рішень з допомогою оптимального управління. [1,7]

В даному курсовому проекті використовується метод лінійного програмування двоїстий симплекс.

Лінійне програмування — розв’язує задачі подані лінійними моделями, тобто ті, які мають лінійну цільову функцію (ЦФ) та лінійну область допустимих рішень (ОДР.).

1. Постановка задачі

У районі лісового масиву діють лісопильний завод і фабрика, на якій виготовлюють фанеру. Щоб одержати 2,5 м³ комплектів пиломатеріалів, треба витратити l₁ м³ ялинових і ₁ м³ пихтових лісоматеріалів. Для готування 100 м² фанери потрібно l₂ м³ ялинових і ₂ м³ пихтових лісоматеріалів. Лісовий масив містить E м³ ялинових і Р м³ пихтових лісоматеріалів. Протягом планованого періоду необхідно зробити принаймні Q₁ м³ пиломатеріалів і Q₂ м³ фанери. 1 м³ пиломатеріалів дає D₁ грн., а 100 м² фанери — D₂ грн. прибутку

Яка кількість пиломатеріалів і фанери потрібно зробити, щоб прибуток був максимальним?

2. Розробка математичної моделі

— пиломатеріали (м³)

— фанера (м²)

3. Вибір та обґрунтування методів рішення задачі

Дану задачу можна вирішувати наступними методами:

· Двоїстий симплекс-метод (програмую)

Є ряд задач лінійного програмування, які можуть бути розв’язані тільки двоїстим симплекс-методом, наприклад деякі задачі мінімізації. Для кожної моделі існує поняття двоїстої задачі, тобто запис задачі іншими змінними для розв’язання потім іншим методом, який потрібний для перевірки правильності симплекс-методу та інших методів ЛП.

Метод базується на постійному поліпшенні умови недопустимості розв’язку. На його основі створена програма double. exe. Якщо в прямому симплекс-методі алгоритм базується на постійному покращенні значенні цільової функції, тобто значення симплекс-таблиці, то в ДСМ алгоритм — на постійному вилученні розв’язку, тобто всі базисні змінні в кінці xn є Bx, xn<=0, стануть позитивними.

· Симплекс-метод

Даний метод базується на табличних перетвореннях Джордана-Гауса моделі, поданої в канонічному вигляді. Метод симплекс-таблиць або метод переміщення по кутах (по симплексах) має в основі ітераційний розрахунок з максимально можливою кількістю ітерацій:

С=m! /n! (m-n!)

де C — максимально можлива кількість ітерацій (умова перевірки на зацикленість);

n — кількість рівнянь;

m - кількість змінних у канонічному вигляді.

Симплекс-метод базується на постійних перетвореннях таблиці:

виробничий план симплекс двоїстий

Симплекс-метод

де: B_{x -} базисні змінні;

C_x — коефіцієнти цільової функції при базисних змінних;

симплекс різниця;

A_1. A_m — коефіцієнти в обмеженнях;

A_{0 -} права частина.

Кожна ітерація полягає в заміні (перерахунку) базисної змінної.

4. Алгоритм двоїстого симплекс-методу рішення задачі та опис програми

1. Зведення ЦФ до максимуму, а обмежень до рівностей (канонічний вигляд).

2. Запис двоїстої задачі

3. Побудова незалежних векторів на підставі рядків ДЗ.

4. Вибір спряженого базису:

ь Довільний вибір m рівнянь;

ь Розв’язання цієї системи m з рівнянь;

ь Підстановка розв’язку в кожне із залишених обмежень та перевірка: чи задовольняє спряжений базис;

ь Якщо спряжений базис задовольняє, то формування псевдолану (розрахунок симплекс-таблиці);

ь Якщо спряжений базис не задовольняє, то треба обрати новий. Якщо на генерації нових сполучень не буде знайдено спряжений базис, то немає розв’язку.

Спряжений базис (А1А4А5А6)

5. Заповнення симплекс-таблиці.

6. Вибір направляючого елементу.

7. Всі інші симплекс-перетворення в ДСМ аналогічні прямому СМ.

Рис. 1 Алгоритм двоїстого симплекс-методу

5. Ітерації програмного рішення задачі

(C*) Leonchenko Anna. PNK-41

Условие считывается из файла

Вывод выполняется в файл

Размерность задачи 4×6:

max (20×1+0.50×2+0×3+0×4+0×5+0×6)

{1} 1×1+0.05×2+1.04×3+0×4+0×5+0×6=86.53

{2} 0×1−0.06×2−3.12×3+1×4+0×5+0×6=-59.60

{3} 0×1+0.05×2+1.04×3+0×4+1×5+0×6=77.59

{4} 0×1−1×2+0×3+0×4+0×5+1×6=-1000

Опис процедур програми:

Function 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 — перевірка.

6. Алгоритм методу симплекс-таблиць рішення задачі

1. Визначення спрямовуючого стовпчика j^*

Якщо відсутнє, то розв’язок знайдено: базисні змінні дорівнюють, а небазисні - 0

2. Визначення спрямовуючого рядка і^*

Якщо і^* відсутнє, тобто в стовпчику знаходиться значення не більше 0, то розв’язок відсутній (ОДР не обмежена зверху), інакше фіксуємо спрямовуючий елемент: (2 1) =1

3. Перерахунок таблиці (власне заміна базисних змінних):

· ділення значень спрямовуючого рядка на спрямовуючий елемент:

· обнулення спрямовуючого стовпця, крім спрямовуючого елемента:

· перерахунок решти значень за формулою прямокутників:

4. Перевірка ітерації:

· цільова функція має не зменшуватися;

· номер ітерації має не перевищувати їхню максимальну кількість:

· базисні змінні мають мати одиничний вектор;

· розрахунок має співпадати як за формулою спрямовуючого стовпчика, так і за формулою «прямокутника» .

Розв’язок знайдено, тому що всі 0. Після розрахунку потрібно виконати наступну перевірку:

· чи всі М-змінні дорівнюють 0 якщо ні, то розв’язок відсутній або ж вибрано занадто малий коефіцієнт m.

· Значення Z має дорівнювати значенню C_i X_i

Рис. 2 Алгоритм симплекс-методу

Канонічна форма, розмірність 4*8

Ітерації рішення задачі вручну.

Размерность задачи НЛП — 4 х 8

max (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. Висновок та дослідження на чутливість моделі

Рішення інших задач

Приклад № 1

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

4 6

20 0.5 0 0 0 0

1 0.049 1.04 0 0 0 = 100

0 — 0.062 — 3.12 1 0 0 = - 40

0 0.049 1.04 0 1 0 = 77.59

0 — 1 0 0 0 1 = - 1000

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

© Leonchenko Anna. PNK-41

File dlja zchityvannja

Vivid vukon v file

Rozmirnist zadachi 4×6:

max (20×1+0.50×2+0×3+0×4+0×5+0×6)

{1} 1×1+0.05×2+1.04×3+0×4+0×5+0×6=100

{2} 0×1−0.06×2−3.12×3+1×4+0×5+0×6=-40

{3} 0×1+0.05×2+1.04×3+0×4+1×5+0×6=77.59

{4} 0×1−1×2+0×3+0×4+0×5+1×6=-1000

Приклад № 2

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

4 6

30 2 0 0 0 0

1 0.049 1.04 0 0 0 = 86.53

0 — 0.062 — 3.12 1 0 0 = - 59.6

0 0.049 1.04 0 1 0 = 77.59

0 — 1 0 0 0 1 = - 1000

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

© Leonchenko Anna. PNK-41

File dlja zchityvannja

Vivid vukon v file

Rozmirnist zadachi 4×6:

max (30×1+2×2+0×3+0×4+0×5+0×6)

{1} 1×1+0.05×2+1.04×3+0×4+0×5+0×6=86.53

{2} 0×1−0.06×2−3.12×3+1×4+0×5+0×6=-59.60

{3} 0×1+0.05×2+1.04×3+0×4+1×5+0×6=77.59

{4} 0×1−1×2+0×3+0×4+0×5+1×6=-1000

Приклад № 3

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

4 6

20 0.5 0 0 0 0

1 0.02 1.04 0 0 0 = 86.53

0 — 0.062 — 3.12 1 0 0 = - 59.6

0 0.049 1.04 0 1 0 = 77.59

0 — 1 0 0 0 1 = - 1000

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

© Leonchenko Anna. PNK-41

File dlja zchityvannja

Vivid vukon v file

Rozmirnist zadachi 4×6:

max (20×1+0.50×2+0×3+0×4+0×5+0×6)

{1} 1×1+0.02×2+1.04×3+0×4+0×5+0×6=86.53

{2} 0×1−0.06×2−3.12×3+1×4+0×5+0×6=-59.60

{3} 0×1+0.05×2+1.04×3+0×4+1×5+0×6=77.59

{4} 0×1−1×2+0×3+0×4+0×5+1×6=-1000

8. Дослідження розробленої програми для великих розмірностей

(c) Leonchenko Anna. PNK-41

File dlja zchityvannja

Vivid vukon v file

Rozmirnist zadachi 5×11:

max (-17×1−20×2−22×3−25×4−28×5−30×6+0×7+0×8+0×9+0×10+0×11)

{1} - 33×1+0×2−43×3+0×4−60×5+0×6+1×7+0×8+0×9+0×10+0×11=-1050

{2} 0×1−28×2+0×3−40×4+0×5−50×6+0×7+1×8+0×9+0×10+0×11=-600

{3} 1×1+1×2+0×3+0×4+0×5+0×6+0×7+0×8+1×9+0×10+0×11=5

{4} 0×1+0×2+1×3+1×4+0×5+0×6+0×7+0×8+0×9+1×10+0×11=15

{5} 0×1+0×2+0×3+0×4+1×5+1×6+0×7+0×8+0×9+0×10+1×11=15

Найбільша розмірність, яка може бути вирішена даним програмним продуктом складає матрицю розміром 50*50.

Список використаної літератури

1. Бабич В.І. Конспект лекцій з дисципліни «Математичні методи дослідження операцій»

2. Культин Н. Б. Программирование в Turbo Pascal 7.0 — Спб.: БХВ — Санкт-Петербург, 1999 — 240 с.

Додаток

Лістинг програми

program simplex;

uses crt;

const

nmax=50;

mmax=50;

var

sub, file_input, file_output, iter, zn_max: string;

it, res, fl: boolean;

ind, k, n, m, j0, i0, i, j, nom_it: integer;

c: array [1. mmax] of real;

a: array [1. nmax, 0. mmax] of real;

b: array [1. nmax] of byte;

d: array [0. mmax] of real;

znak: array [1. nmax] of char;

key: char;

{ x: array [1. mmax] of real; }

function value (var s: string): string;

var

v: string;

i: integer;

begin

v: ='';

repeat

if s =',' then v: =v+'. ' else v: =v+s [1];

delete (s, 1,1);

until (s =' ') or (s='');

value: =v;

end;

procedure prov (var s: string);

begin

if s =' ' then

repeat

delete (s, 1,1);

until s <>' ';

if s [length (s)] =' ' then

repeat

delete (s, length (s), 1);

until s [length (s)] <>' ';

end;

procedure error (sub: string);

begin

write ('Недопустимий символ ');

for i: =1 to length (sub) do

case sub [i] of

'A'. 'Z','a'. 'z': write ('Буква ');

'0'. '9',',','. ':;

else write ('спеціальний символ ');

end;

writeln;

end;

function ReadData: boolean;

var

s: string;

code, i, j: integer;

begin

readdata: =true;

assign (input, file_input);

reset (input);

if ioresult<>0 then

begin

writeln ('Файл'<+file_input+'>не найдено');

halt;

end;

readln (s);

prov (s);

sub: =value (s);

val (sub, n, code);

if code<>0 then

begin

writeln ('Помилка: рядок 1-й число 1-ше ');

readdata: =false;

error (sub);

end;

prov (s);

sub: =value (s);

val (sub, m, code);

if code<>0 then

begin

writeln (' Помилка: рядок 1-й число 2-ге ');

readdata: =false;

error (sub);

end;

if (n>nmax) or (m>mmax) then begin

writeln ('Указана розмірність задачі не підходить обмеженням задачі');

readdata: =false;

end;

readln (s);

prov (s);

for j: =1 to m do

begin

sub: =value (s);

val (sub, c [j], code);

if code<>0 then

begin

writeln (Помилка: рядок 2-й', j, 'число);

readdata: =false;

error (sub);

end;

prov (s);

end;

zn_max: =value (s);

for i: =1 to n do

begin

readln (s);

prov (s);

for j: =1 to m do

begin

sub: =value (s);

val (sub, a [i, j], code);

if code<>0 then

begin

writeln ('Помилка: рядок', i+2,'-число ', j,');

readdata: =false;

error (sub);

end;

prov (s);

end;

znak [i]: =s [1];

delete (s, 1,1);

if (znak <>'>') and (znak <>'<') and (znak <>'=') then begin

writeln ('Ошибка: рядок ', i+2,' - й: не вірно вказаний знак');

readdata: =false;

end;

prov (s);

sub: =value (s);

val (sub, a [i, 0], code);

if code<>0 then

begin

writeln ('Ошибка: рядок ', i+2,' - й', m+1,'оє: ');

readdata: =false;

error (sub);

end;

end;

end;

procedure kanon;

var

max: real;

begin

max: =1;

for i: =1 to m do

if max

max: =10*max;

if (length (zn_max) =3) and ((zn_max ='I') or (zn_max ='i')) and ((zn_max ='N') or (zn_max ='n')) then

for i: =1 to m do

c [i]: =-c [i];

repeat

for i: =1 to n do

if a [i, 0] <0 then

begin

for j: =0 to m do

a [i, j]: =-a [i, j];

res: =false;

case znak [i] of

'>': znak [i]: ='<';

'<': znak [i]: ='>';

end;

break;

end

else if (a [i, 0] =0) and (znak [i] ='<') then

begin

for j: =1 to m do

a [i, j]: =-a [i, j];

znak [i]: ='>';

res: =false;

break;

end

else

begin

case znak [i] of

'>': begin

inc (m);

c [m]: =0;

a [i, m]: =-1;

for j: =1 to n do

if i<>j then

a [j, m]: =0;

end;

'<': begin

inc (m);

c [m]: =0;

a [i, m]: =1;

for j: =1 to n do

if i<>j then

a [j, m]: =0;

end;

'=': begin

inc (m);

c [m]: =0;

a [i, m]: =1;

for j: =1 to n do

if i<>j then

a [j, m]: =0;

end;

end;

res: =true;

znak [i]: ='^';

end;

until (res=true);

end;

function druk (b: real; im: boolean): string;

var

s, s1: string;

cel, i, j: integer;

begin

s: ='';

cel: =trunc (b);

i: =1;

if b<0 then

begin

inc (i);

cel: =abs (cel);

end;

while cel div 10 >0 do

begin

cel: =cel div 10;

inc (i);

end;

if frac (b) <>0 then

begin

i: =i+3;

str (b: 4: 2, s);

end

else str (trunc (b), s);

if im then

begin

i: =8-i;

s1: ='';

for j: =1 to i do

s1: =s1+' ';

s: =s1+s;

end;

druk: =s;

end;

procedure vivod;

var i, j: integer;

begin

writeln ('Iteracija #', nom_it: 4);

writeln ('——————————————————————————————————');

writeln ('——————————————————————————————————');

write ('Cil. funk ');

for i: =1 to m do

write (druk (c [i], true));

writeln ('');

write ('—————————————————————————————————');

writeln ('');

write (' Bx ');

for j: =0 to m do

write (' A', j,' ');

writeln ('');

for i: =1 to n do

begin

write (druk (c [b [i]], true));

write (' X', b [i]);

write (druk (a [i, 0], true));

for j: =1 to m do

write (druk (a [i, j], true));

writeln (' ');

end;

writeln ('—————————————————————————————————');

write ('R ');

for i: =0 to m do

write (druk (d [i], true));

writeln (' ');

writeln ('—————————————————————————————————-');

writeln ('');

nom_it: =nom_it+1;

end;

procedure WriteUmovu;

var

i, j: integer;

begin

clrscr;

writeln (' © Leonchenko Anna. PNK-41');

writeln;

writeln ('File dlja zchityvannja <'+file_input+'>');

if file_output='con' then

writeln ('Vivid vukon na ekran')

else writeln ('Vivid vukon v file <'+file_output+'>');

Writeln ('Rozmirnist zadachi ', n, 'x', m, ': ');

writeln;

write ('max (');

for j: =1 to m do

if (c [j+1] >=0) and (j<>m) then write (druk (c [j], false),'x', j,'+')

else write (druk (c [j], false),'x', j);

writeln (') ');

for i: =1 to n do

begin

write ('{', i,'} ');

for j: =1 to m do

begin

write (druk (a [i, j], false),'x', j);

if (a [i, j+1] >=0) and (j<>m) then write ('+');

end;

writeln ('=', druk (a [i, 0], false));

end;

if file_output='con' then

repeat

key: =readkey

until key=#13;

end;

procedure RozDelta; {rozraxynok delta}

var

i, j, k: integer;

pr: boolean;

begin

for i: =1 to n do {zapisyemo ne 0 elementu}

for j: =1 to m do

if a [i, j] =1 then

begin

pr: =false;

for k: =1 to n do

if (i<>k) then

if (a [k, j] =0) then pr: =true

else begin pr: =false; break; end;

if pr then

begin b [i]: =j; break; end;

end;

for j: =0 to m do {podchet delta}

begin

if j=0 then d [j]: =0 else d [j]: =-c [j];

for i: =1 to n do

d [j]: =d [j] +a [i, j] *c [b [i]];

end;

end;

function napr_str (var i0: integer): boolean; {vuznachennja napr-j stroku}

var

value1: real;

i: integer;

begin

napr_str: =false;

value1: =0;

i0: =0;

for i: =1 to n do

if (a [i, 0]

begin

value1: =a [i, 0];

i0: =i; {nomer napr-j stroku}

napr_str: =true;

end;

end;

function napr_st (i0: integer; var j0: integer): boolean; {viznachennja napr-go stovbchika}

var

value1: real;

j: integer;

begin

napr_st: =false;

value1: =0;

j0: =0;

for j: =1 to m do

if (a [i0,j] <0) and (abs (d [j] /a [i0,j]) >value1) then

begin

value1: =abs (d [j] / (a [i0,j]));

j0: =j; {zapusyemo nomer stovbchika}

napr_st: =true;

end;

end;

procedure pererah; {pererahovyemo matrucy}

var

i, j: integer;

begin

for j: =0 to m do

if j<>j0 then

begin

for i: =1 to n do

if i<>i0 then

a [i, j]: =a [i, j] - (a [i0,j] *a [i, j0] /a [i0,j0]);

d [j]: =d [j] - (a [i0,j] *d [j0] /a [i0,j0]);

end;

for j: =0 to m do

if j<>j0 then a [i0,j]: =a [i0,j] /a [i0,j0]; {rozrahynok napr. stoku}

for i: =1 to n do

if i<>i0 then a [i, j0]: =0; {rozrahynok napr. stovb. }

d [j0]: =0;

a [i0,j0]: =1;

b [i0]: =j0; {zapis nomera stovb. }

end;

function simpl: boolean; {}

begin

simpl: =true;

while napr_str (i0) do

if napr_st (i0,j0) then

begin

Pererah;

vivod;

end

else

begin

simpl: =false;

break;

end;

end;

BEGIN

{file_input: ='in. txt';

file_output: ='out. txt';

it: =true; }

file_input: =paramstr (1);

file_output: =paramstr (2);

iter: =paramstr (3);

readkey;

if (file_input='') or (file_output='') then

begin

writeln ('Vvedit pravilno dani');

writeln ('DUOSIMPL. exe inputfile outputfile/con [Y/y] ');

exit;

end;

if (iter='Y') or (iter='y') then it: =true;

if file_output<>'con' then

begin

assign (output, file_output);

rewrite (output);

end;

res: =true;

if not ReadData then halt;

{Kanon; }

writeln;

WriteUmovu;

writeln;

RozDelta;

nom_it: =1;

vivod;

if not simpl then {nema rishennja}

begin

writeln ('Rishen nemaje');

halt;

end

else

begin

writeln ('Rishennja znajdeno!!! Param-pam-pam');

writeln ('Z=', druk (d [0], true));

write ('X = (');

for i: =1 to m do

begin

fl: =false;

for j: =1 to m do

if b [j] =i then begin write (druk (a [j, 0], false),' '); fl: =true; end;

if fl=false then write ('0 ');

end;

writeln (') ');

end

END.