Максимізація прибутку кондитерської фабрики

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

ЗМІСТ

ВСТУП

РОЗДІЛ 1.ТЕОРЕТИЧНА ЧАСТИНА

1.1 Актуальність проблеми

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

1.3 Математична модель задачі

1.4 Формулювання алгоритму методу

РОЗДІЛ 2.ПРАКТИЧНА ЧАСТИНА

2.1Розвязок задачі сиплекс-методом

2.2 Аналіз результатів

ВИСНОВКИ

ПЕРЕЛІК ЛІТЕРАТУРНИХ ДЖЕРЕЛ

ВСТУП

Необхідність ухвалення найкращих рішень так само стара, як само людство. Споконвіку люди, приступаючи до здійснення своїх заходів, роздумували над їх можливими наслідками і приймали рішення, вибираючи тим або іншим чином залежні від них параметри - способи організації заходів. Але до пори, до часу рішення міг прийматися без спеціального математичного аналізу, просто на основі досвіду і здорового глузду.

Оптимізація як розділ математики існує досить давно. Оптимізація - це вибір, тобто те, чим постійно доводиться займатися в повсякденному житті. Терміном "оптимізація" у літературі позначають процес або послідовність операцій, що дозволяють отримати уточнене рішення. Хоча кінцевою метою оптимізації є відшукання найкращого або "оптимального" рішення, зазвичай доводиться задовольнятися поліпшенням відомих рішень, а не доведенням їх до досконалості. Тому під оптимізацією розуміють швидше прагнення до досконалості, яка, можливо, і не буде досягнуто.

Вперше методи оптимізації, як спосіб математичного розв'язання певного класу задач, були тією чи іншою мірою застосовані в ще в XVII ст. Але ця область математичного дослідження ще довго буде складовою частиною великої кількості різних наук заснованих на математиці. В процесі розвитку науки формуються основні принципи цієї дисципліни, розробляються її власні методи підходу до розв'язування задач. Через своє поширення, задачи оптимізації знаходять широке застосування в різних областях, де використовуються математичні методи для аналізу процесів що там відбуваються. Надзвичайно велике значення задачи оптимізації мають в техніці, економіці, управлінні тощо.

РОЗДІЛ 1.ТЕОРЕТИЧНА ЧАСТИНА

1.1 Актуальність проблеми

Необхідність розв'язання задач оптимізації призводить до того, що дана дисципліна стає важливим елементом вивчення спеціалістів, які б могли використовувати ці методи при розв'язанні задач, пов'язаних з її використанням. Через своє поширення в багатьох галузях науки, техніки, економіки технологія розв'язання задач предмету «методів оптимізації та дослідження операцій» повинна стати однією з найважливіших складових частин сучасної математичної освіти. Адже актуальність використання методів оптимізації стає очевидною при розв'язанні задач, основною метою яких є, наприклад, максимізація прибутку від продажу того чи іншого продукту.

Симплекс-метод один з основних методів розв'язання задач оптимізації. Цей метод є універсальний, ним можна розв'язати будь-яку задачу лінійного програмування. Він досить часто застосовується при роботі з оптимізаційними задачами. Крім того на основі цього методу будуються і інші підходи методів оптимізації, такі як: модифікований симплекс-метод, двоїстий симплекс метод, та інші. Вивчення цього методу є однією з основних задач.

В даному курсовому проекті розв'язання та перевірка симплекс-методу буде розглянута на прикладі задачи максимізації виробництва продукції. Задачі такого типу є досить поширеними і застосовуються на різних сферах діяльності суспільства. Тому використання такого прикладу для вивчення методу є раціональним, а проблема актуальною.

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

Кондитерська фабрика для виробництва семи видів карамелі використовує три види основної сировини: цукровий пісок, патоку та фруктове пюре. Норми затрат сировини кожного виду на виробництво 1т карамелі даного виду наведені в таблиці.

В ній також вказано загальну кількість сировини кожного виду, яка може бути використана фабрикою, а також наведений прибуток від реалізації 1т карамелі даного виду.

1.3 Математична модель задачі

Максимізувати прибуток кондитерської фабрики

Вид сировини	Норми витрат сировини (т) на 1 т карамелі	Загальна кількість сировини (т)
	А	В	С	D	E	F	G
Цукровий пісок Патока Фруктове пюре	0,6 0,4	0,5 0,4 0,1	0,6 0,3 0,1	0,7 0,3 -	0,4 0,4 0,2	0,5 0,3 0,2	0,3 0,4 0,3	800 600 120
Прибуток від реалізації 1 т продукції (грн.)	108	112	126	110	120	115	125

x1 - кількість виду карамелі А в (т.)

x2 - кількість виду карамелі B в (т.)

x3 - кількість виду карамелі C в (т.)

x4 - кількість виду карамелі D в (т.)

x5 - кількість виду карамелі E в (т.)

x6 - кількість виду карамелі F в (т.)

x7 - кількість виду карамелі G в (т.)

Визначимо максимальне значення цільової функції

F(X) = 108x1+112x2+126x3+110x4+120x5+115x6+125x7

за наступних умов-обмежень.

0.6x1+0.5x2+0.6x3+0.7x4+0.4x5+0.5x6+0.3x7?800

0.4x1+0.4x2+0.3x3+0.3x4+0.4x5+0.3x6+0.4x7?600

0.1x2+0.1x3+0.2x5+0.2x6+0.3x7?120

Оскільки об'єми сумішей не можуть приймати негативні значення, то з'являються обмеження позитивності :

x1 0 , x2 0 , x3 0 , x4 0, x5 0, x6 0, x7 0

1.4 Формулювання алгоритму методу

Симплекс-метод розв'язання задачі лінійного програмування заснований на переході від одного опорного плану до іншого, при якому значення цільової функції зростає. Вказаний перехід можливий, якщо відомий який-небудь початковий опорний план. Розглянемо завдання, для якого цей план можна безпосередньо записати.

Хай потрібно знайти максимальне значення функції:

F=c1x1+c2x2+…+cnxn,

за умов:

x1+a1m+1xm+1+…+a1nxn=b1,

x2+a2m+1xm+1+…+a2nxn=b2,

…………………………..

xm+amm+1xm+1+…+amnxn=bm,

xj 0 (j=),

де aij , bi і cj (i=; j=) - задані постійні числа.

Векторна форма даного завдання має наступний вигляд: знайти максимум функції:

(1.1)

за умов

x1P1 + x2P2 +…+ xmPm +…+ xnPn = Po. (1.2)

xj 0 (j=), (1.3)

де

Оскільки

b1P1 + b2P2 +…+ xmPm = Po,

то за визначенням опорного плану X=(b1;b2; …;bm; 0; …;0) є опорним планом даного завдання (останні компонент вектора Х рівні нулю). Цей план визначається системою одиничних векторів P1,P2,…,Pm які утворюють базис m-мірного простору. Тому кожен з векторів P1,P2,…,Pm , а також вектор Po можуть бути представлені у вигляді лінійної комбінації векторів даного базису. Нехай

Покладемо

Так як вектори P1,P2,…,Pm - одиничні, то xij=aij і , а

Теорема 1(ознака оптимальності опорного плану). Опорний план X*=(х*1;х*2; …;х*m; 0; …;0) завдання (1.1) - (1.3) є оптимальним, якщо для будь-якого j .

Теорема 6. Якщо для деякого j=k і серед чисел немає позитивних, то цільова функція (1.1) завдання (1.1) - (1.3) не обмежена на безлічі її планів.

Теорема 7. Якщо опорний план Х завдання (1.1) - (1.3) невироджений і, але серед чисел є позитивні (не всі ), то існує опорний план X' такий, що F(X')>F(X) .

Сформульовані теореми дозволяють перевірити, чи є знайдений опорний план оптимальним, і виявити доцільність переходу до нового опорного плану.

Дослідження опорного плану на оптимальність, а також подальший обчислювальний процес зручніше вести, якщо умови завдання і первинні дані, отримані після визначення початкового опорного плану, записати так, як показано в таблиці 1.2.

Таблиця 1.2 - Симплекс-таблиця

Після заповнення таблиці 3 початковий опорний план перевіряють на оптимальність. Для цього проглядають елементи (m+1)-го рядка таблиці. В результаті може мати місце один з наступних трьох випадків:

1) для j=m+1,m+2,..,n (при ). Тому в даному випадку числа для всіх j від 1 до n;

2) для деякого j, і всі відповідні цьому індексу величини

3) для деяких індексів j, і для кожного такого j, принаймні, одне з чисел aij позитивно.

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

Для визначення вектора, який буде виключенню з базису, знаходять для всіх . Нехай цей мінімум досягається при i=r.

Тоді з базису виключають вектор Pr, а число ark називають розв'язальним елементом.

Стовпець і рядок, на перетині яких знаходиться розв'язальний елемент, називають напрямними.

Отже, перехід від одного опорного плану до іншого зводиться до переходу від однієї симплекс-таблиці до іншої.

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

Елементи векторів Po і Pj в рядку нової симплекс-таблиці, в якій записаний вектор, що вводиться в базис, отримують з елементів цього ж рядка початкової таблиці діленням їх на величину розв'язального елементу. У стовпці Cб в рядку вектора, що вводиться, проставляють величину ck, де до k- індекс вектора, що вводиться.

Решту елементів стовпців вектора Po і Pj нової симплекс-таблиці обчислюють за правилом трикутника. Для обчислення якого-небудь з цих елементів знаходять три числа:

1) число, що стоїть в початковій симплекс-таблиці на місці шуканого елементу нової симплекс-таблиці;

2) число, що стоїть в початковій симплекс-таблиці на перетині рядка, в якому знаходиться шуканий елемент нової симплекс-таблиці, і стовпця, відповідного вектору, що вводиться в базис;

3) число, що стоїть в новій симплекс-таблиці на перетині стовпця, в якому коштує шуканий елемент, і рядки вектора, що знов вводиться в базис (як зазначено вище, цей рядок виходить з рядка початковою симплекс-таблиці діленням її елементів на розв'язальний елемент).

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

Після заповнення нової симплекс-таблиці проглядають елементи (m+1)-го рядка. Якщо всі вони додатні, то новий опорний план є оптимальним. Якщо ж серед вказаних чисел є негативні, то, використовуючи описану вище послідовність дій, знаходять новий опорний план. Цей процес продовжують до тих пір, поки або не отримують оптимальний план завдання, або не встановлюють її нерозв'язність.

Для розв'язку використаємо симплекс-метод, оскільки у правій частині всі значення додатні, є базисні змінні.

РОЗДІЛ 2. ПРАКТИЧНА ЧАСТИНА

2.1 Розвязок задачі сиплекс-методом

F(X) = 108x1+112x2+126x3+110x4+120x5+115x6+125x7

0.6x1+0.5x2+0.6x3+0.7x4+0.4x5+0.5x6+0.3x7?800

0.4x1+0.4x2+0.3x3+0.3x4+0.4x5+0.3x6+0.4x7?600

0.1x2+0.1x3+0.2x5+0.2x6+0.3x7?120

x1 0 , x2 0 , x3 0 , x4 0, x5 0, x6 0, x7 0

Зводимо систему до канонічного вигляду, для цього додаємо нові змінні

0.6x1 + 0.5x2 + 0.6x3 + 0.7x4 + 0.4x5 + 0.5x6 + 0.3x7 + 1x8 + 0x9 + 0x10 = 800

0.4x1 + 0.4x2 + 0.3x3 + 0.3x4 + 0.4x5 + 0.3x6 + 0.4x7 + 0x8 + 1x9 + 0x10 = 600

0x1 + 0.1x2 + 0.1x3 + 0x4 + 0.2x5 + 0.2x6 + 0.3x7 + 0x8 + 0x9 + 1x10 = 120

Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:

0.6	0.5	0.6	0.7	0.4	0.5	0.3	1	0	0
0.4	0.4	0.3	0.3	0.4	0.3	0.4	0	1	0
0	0.1	0.1	0	0.2	0.2	0.3	0	0	1

Вирішимо систему рівнянь щодо базисних змінних:

x8, x9, x10,

Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:

X1 = (0,0,0,0,0,0,0,800,600,120)

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x8	800	0.6	0.5	0.6	0.7	0.4	0.5	0.3	1	0	0
x9	600	0.4	0.4	0.3	0.3	0.4	0.3	0.4	0	1	0
x10	120	0	0.1	0.1	0	0.2	0.2	0.3	0	0	1
F(X0)	0	-108	-112	-126	-110	-120	-115	-125	0	0	0

Переходимо до основного алгоритму симплекс-методу.

Ітерація № 0.

Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться від'ємні коефіцієнти.

В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x3, так як це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai3

і з них виберемо найменше:

Отже, 3-а рядок є провідною.

Розрахунковий елемент дорівнює (0.1) і знаходиться на перетині ведучого стовпця і ведучого рядка.

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x8	800	0.6	0.5	0.6	0.7	0.4	0.5	0.3	1	0	0	1333.33
x9	600	0.4	0.4	0.3	0.3	0.4	0.3	0.4	0	1	0	2000
x10	120	0	0.1	0.1	0	0.2	0.2	0.3	0	0	1	1200
F(X1)	0	-108	-112	-126	-110	-120	-115	-125	0	0	0	0

Після перетворень отримуємо нову таблицю:

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x8	80	0.6	-0.1	0	0.7	-0.8	-0.7	-1.5	1	0	-6
x9	240	0.4	0.1	0	0.3	-0.2	-0.3	-0.5	0	1	-3
x3	1200	0	1	1	0	2	2	3	0	0	10
F(X1)	151200	-108	14	0	-110	132	137	253	0	0	1260

Ітерація № 1.

Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться від'ємні коефіцієнти.

В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x4, так як це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai4

і з них виберемо найменше:

Отже, 1-ша рядок є провідною.

Дозволяє елемент дорівнює (0.7) і знаходиться на перетині ведучого стовпця і ведучого рядка.

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x8	80	0.6	-0.1	0	0.7	-0.8	-0.7	-1.5	1	0	-6	114.29
x9	240	0.4	0.1	0	0.3	-0.2	-0.3	-0.5	0	1	-3	800
x3	1200	0	1	1	0	2	2	3	0	0	10	-
F(X2)	151200	-108	14	0	-110	132	137	253	0	0	1260	0

Після перетворень отримуємо нову таблицю:

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x4	114.29	0.86	-0.14	0	1	-1.14	-1	-2.14	1.43	0	-8.57
x9	205.71	0.14	0.14	0	0	0.14	0	0.14	-0.43	1	-0.43
x3	1200	0	1	1	0	2	2	3	0	0	10
F(X2)	163771.43	-13.71	-1.71	0	0	6.29	27	17.29	157.14	0	317.14

Ітерація № 2.

Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться від'ємні коефіцієнти.

В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x1, так як це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai1

і з них виберемо найменше:

Отже, 1-ша рядок є провідною.

Дозволяє елемент дорівнює (0.86) і знаходиться на перетині ведучого стовпця і ведучого рядка.

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x4	114.29	0.86	-0.14	0	1	-1.14	-1	-2.14	1.43	0	-8.57	133.33
x9	205.71	0.14	0.14	0	0	0.14	0	0.14	-0.43	1	-0.43	1440
x3	1200	0	1	1	0	2	2	3	0	0	10	-
F(X3)	163771.43	-13.71	-1.71	0	0	6.29	27	17.29	157.14	0	317.14	0

Після перетворень отримуємо нову таблицю:

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	133.33	1	-0.17	0	1.17	-1.33	-1.17	-2.5	1.67	0	-10
x9	186.67	0	0.17	0	-0.17	0.33	0.17	0.5	-0.67	1	1
x3	1200	0	1	1	0	2	2	3	0	0	10
F(X3)	165600	0	-4	0	16	-12	11	-17	180	0	180

Ітерація № 3.

Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться від'ємні коефіцієнти.

В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x7, так як це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai7

і з них виберемо найменше:

Отже, 2-а рядок є провідною.

Дозволяє елемент дорівнює (0.5) і знаходиться на перетині ведучого стовпця і ведучого рядка.



Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x1	133.33	1	-0.17	0	1.17	-1.33	-1.17	-2.5	1.67	0	-10	-
x9	186.67	0	0.17	0	-0.17	0.33	0.17	0.5	-0.67	1	1	373.33
x3	1200	0	1	1	0	2	2	3	0	0	10	400
F(X4)	165600	-0	-4	0	16	-12	11	-17	180	0	180	0

Після перетворень отримуємо нову таблицю:

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	1066.67	1	0.67	0	0.33	0.33	-0.33	0	-1.67	5	-5
x7	373.33	0	0.33	0	-0.33	0.67	0.33	1	-1.33	2	2
x3	80	0	0	1	1	0	1	0	4	-6	4
F(X4)	171946.67	0	1.67	0	10.33	-0.67	16.67	0	157.33	34	214

Ітерація № 4.

Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться від'ємні коефіцієнти.

В індексному рядку F (x) вибираємо максимальний по модулю елемент. В якості ведучого виберемо стовпець, відповідний змінної x5, так як це найбільший коефіцієнт за модулем.

Обчислимо значення Di по рядках як частка від ділення: bi / ai5

і з них виберемо найменше:

Отже, 2-а рядок є провідною.

Дозволяє елемент дорівнює (0.67) і знаходиться на перетині ведучого стовпця і ведучого рядка.

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	min
x1	1066.67	1	0.67	0	0.33	0.33	-0.33	-0	-1.67	5	-5	3200
x7	373.33	0	0.33	0	-0.33	0.67	0.33	1	-1.33	2	2	560
x3	80	-0	0	1	1	0	1	0	4	-6	4	-
F(X5)	171946.67	0	1.67	0	10.33	-0.67	16.67	-0	157.33	34	214	0

Після перетворень отримуємо нову таблицю:

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	880	1	0.5	0	0.5	0	-0.5	-0.5	-1	4	-6
x5	560	0	0.5	0	-0.5	1	0.5	1.5	-2	3	3
x3	80	0	0	1	1	0	1	0	4	-6	4
F(X5)	172320	0	2	0	10	0	17	1	156	36	216

Кінець ітерацій: індексний рядок не містить негативних елементів - знайдений оптимальний план

Остаточний варіант симплекс-таблиці:

Базис	В	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10
x1	880	1	0.5	0	0.5	0	-0.5	-0.5	-1	4	-6
x5	560	0	0.5	0	-0.5	1	0.5	1.5	-2	3	3
x3	80	0	0	1	1	0	1	0	4	-6	4
F(X6)	172320	0	2	0	10	0	17	1	156	36	216

Оптимальний план можна записати так:

x1 = 880

x5 = 560

x3 = 80

F(X) = 108*880 + 126*80 + 120*560 = 172320

програмний максимізація прибуток симплекс

2.5 Аналіз результатів

Для перевірки отриманих даних, ми роз'язали дану задачу в MS Excel, за допомогою надбудови Поиск решения. В результаті реалізації даного прикладу ми отримали точно такі дані, як і в практичній частині. Це в свою чергу підтверджує правильність функціонування програми.

Для більш точної перевірки було проведено обрахунки задачі без допомоги різних програмних засобів, в результаті чого результати збігаються з варіантом в Excel.

ВИСНОВКИ

В даний час новітні досягнення математики і сучасної обчислювальної техніки знаходять все більш широке застосування як в економічних дослідженнях і плануванні, так і в інших завданнях. Цьому сприяє розвиток таких розділів математики як математичне програмування, методи оптимізація, а також бурхливий розвиток швидкодіючої електронно-обчислювальної техніки. Особливо успішно розвиваються методи оптимального управління. Економіка і виробництво розвивається швидко там, де широко використовуються математичні методи.

В результаті роботи над створення програми для реалізації оптимізації виробництва, хоча й для певного прикладу, було поглиблено знання з дисципліни «Методи оптимізації та дослідження операцій». Було реалізовано програмний продукт для розв'язання економічної задачи пов'язаної з максимізацією прибутку деякого підприємства. Метод, описаний в програмі, може застосовуватися на державних і приватних підприємствах для поліпшення ефективності виробництва.

Размещено на Allbest.ru