Розв’язок одноіндексних задач лінійного програмування

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

Анотація

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

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



Зміст

1.1 Опис предметної області

1.2 Лінійне програмування. Графічний метод

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

1.4.Транспортна задача

1.5. Двоїстість в лінійному програмуванні

2. Модель задачі лінійного програмування

2.1. Постановка задачі: проблеми, проблематики

2.2. Математична модель задачі лінійного програмування

2.3. Стандартна форма задачі лінійного програмування

2.4. Канонічна форма задачі лінійного програмування

3. Вибір оптимального варіанту математичної моделі задачі лінійного програмування

Висновок

Додаток А: текст програми

Додаток В: результат програми



Вступ

Сучасна економіка як наука про раціональне ведення господарства повинна давати відповіді на такі основні питання: що робити? де виробляти?яка ціна продукції? як порівняти справжні і майбутні витрати?

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

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

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

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

Мета даної курсової роботи: придбання навичок побудови математичних моделей одноіндексних завдань і вирішення їх симплексним методом.

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

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

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

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

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

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

Алгоритм симплекс-методу добре реалізується алгоритмічними мовами такими як Паскаль чи С++. В курсовій роботі, для реалізації симплекс-методу використано мову програмування С++.



1. Опис предметної області

1.1 Лінійне програмування

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

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

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

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

Коло завдань, що вирішуються за допомогою методів лінійного програмування досить широке. Це, наприклад:

ь завдання про оптимальне використання ресурсів при виробничому плануванні;

ь задача про суміші (планування складу продукції);

ь завдання про знаходження оптимальної комбінації різних видів продукції для зберігання на складах (управління товарно-матеріальними запасами);

ь транспортні задачі (аналіз розміщення підприємства, переміщення вантажів).

Лінійне програмування - найбільш розроблений і широко застосовуваний розділ математичного програмування (крім того, сюди відносять: цілочислене, динамічне, нелінійне, параметричне програмування). Це пояснюється наступним:

ь математичні моделі великого числа економічних завдань лінійні щодо шуканих змінних;

ь даний тип завдань в даний час найбільш вивчений. Для нього розроблені спеціальні методи, за допомогою яких ці завдання вирішуються, і відповідні програми для ЕОМ;

ь багато завдань лінійного програмування, будучи вирішеними, знайшли широке застосування;

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

Потрібно визначити максимум лінійної цільової функції (лінійної форми).

при умові

Іноді на також накладається деякий набір обмежень у вигляді рівностей, але

від них можна позбутися, послідовно висловлюючи одну змінну через інші і підставляючи її в усіх інших рівності і нерівності (а також у функції f).

Таке завдання називають «основний» або «стандартної» в лінійному програмуванні.

Загальний вид задачі лінійного програмування.

Обмеження:

1. Праві частини всіх обмежень повинні бути невід'ємними. Якщо який-небудь з коефіцієнтів , то необхідно коефіцієнти обмеження ліворуч і праворуч домножити на "-1" і змінити знак даного обмеження на протилежний;

2. Всі обмеження мають бути представлені у вигляді рівності, тому при переході від нерівності до рівності використовують апарат додаткових змінних.

Якщо вихідні обмеження визначають витрата деякого ресурсу (знак ""), то

змінні слід інтерпретувати як залишок, чи невикористану частину ресурсу. У цьому випадку - залишкова змінна і вводиться в рівняння із знаком "+".

Якщо вихідні обмеження визначають надлишок деякого ресурсу (знак ""), то вводиться надлишкова мінлива знаком "-".

Змінні:

Всі змінні повинні бути негативними, тобто .

Якщо змінна не має обмеження в знаку, то її потрібно пред-вить як різниця двох невід'ємних змінних:, де. Таку підстановку варто використовувати у всіх обмеженнях, що містять цю змінну, а також у вираженні для цільової функції.

Якщо така мінлива потрапляє в оптимальне рішення, то

1.2 Графічний метод

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

Алгоритм графічного методу розв'язування задачі лінійного програмування складається з таких кроків:

1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі (2.18) знаків нерівностей на знаки рівностей.

2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.

3. Знаходимо багатокутник розв'язків задачі лінійного програмування.

4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі.

5. Будуємо пряму с1х1 + с2х2 = const, перпендикулярну до вектора .

6. Рухаючи пряму с1х1 + с2х2 = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набирає екстремального значення.

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

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

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

Симплексний метод на відміну від геометричного універсальний. З його допомогою можна вирішити будь-яке завдання лінійного програмування.

В основу симплексного методу покладена ідея послідовного поліпшення одержуваного рішення.

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

Таким чином, маючи систему обмежень, приведену до канонічної формі (всі функціональні обмеження мають вигляд рівностей), знаходять будь базисне рішення цієї системи, піклуючись тільки про те, щоб знайти його якомога простіше. Якщо перше ж знайдене базисне рішення виявилося припустимим, то перевіряють його на оптимальність. Якщо воно не оптимально, то здійснюється перехід до іншого, обов'язково допустимому базисному рішенню. Симплексний метод гарантує, що при цьому новому рішенні цільова функція, якщо і не досягне оптимуму, то наблизиться до нього (чи, принаймні, не віддалиться від нього). З новим допустимим базисним рішенням поводяться так само, поки не знайдеться рішення, яке є оптимальним.

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

1) спосіб визначення будь-якого початкового допустимого базисного розв'язку задачі;

2) правило переходу на краще (точніше, не гіршого) рішенням;

3) критерій перевірки оптимальності знайденого рішення.

Алгоритм розв'язку симплекс методу:

1. Поставлена ??описова завдання переводиться в математичну форму (цільова функція та обмеження).

2. Отримане математичний опис призводять до канонічної форми.

3. Канонічну форму призводять до матричному увазі.

4. Шукають перший допустиме рішення. Для цього матриця повинна бути правильною. Матриця в ЗЛП називається правильною, якщо вона містить мінімум m правильних (базисних) стовпців, де m - число рядків в матриці. Стовпець у канонічній ЗЛП називається правильним (базисним), якщо всі його елементи дорівнюють нулю, крім єдиного рівного одиниці.

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

6. Будують послідовність матриць. Потрібно визначити провідний стовпець, провідну рядок і ведучий елемент. Елемент, відповідний провідною рядку, видаляється з базису, а на його місце ставлять елемент, відповідний ведучому стовпцю. Складають рівняння перерахунку матриці, виконують перерахунок, а потім перевіряють його результати на оптимальність. Якщо рішення не оптимально, то заново обмежують провідний елемент, провідну рядок і ведучий стовпець.

1.4 Транспортна задача

Транспортна задача -- задача про оптимальний план перевезення продукту (-тів) із пунктів відправлення до пунктів споживання. Розробка і використання оптимальних схем вантажних потоків дозволяють знизити витрати на перевезення. ТЗ по теорії складності обчислень є NP-складною або входить в клас складності NP. Коли сумарний обсяг пропозицій (вантажів, наявних в пунктах відправки) не дорівнює загальному обсягу попиту на товари (вантажі), які потрібні пунктам споживання, то транспортна задача називається незбалансованою.

Метод північно-західного кута

Виконання починається з верхньої лівої клітини (Північно-західного кута) транспортної таблиці, тобто зі змінної

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

Крок 2. Викреслюється рядок (або стовпець) з повністю реалізованою пропозицією (з задоволеним попитом). Це означає, що в викресленою рядку (стовпці) ми не будемо присвоювати значення іншим змінним (крім змінної, визначеної на першому етапі). Якщо одночасно задовольняються попит і пропозиці викреслюється лише рядок або тільки стовпець.

Крок 3. Якщо не викреслено тільки один рядок або тільки один стовпець, процес зупиняється. В іншому випадку переходимо до клітини праворуч, якщо викреслять стовпець, або до клітини знизу, якщо викреслена рядок. Потім повертаємось до першого етапу.

Метод найменшої вартості.

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

1.5 Двоїстість в лінійному програмуванні

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

Зв'язок між прямою і двоїстою задачами встановлюється двома теоремами.

1. "Теорема двоїстості". Якщо обидві задачі мають допустимі рішення, то вони мають і оптимальні рішення, причому значення цільових функцій у них буде однаково:

(позначення див ст. "Лінійне програмування"). Якщо ж хоча б одне із завдань не має допустимого рішення, то жодна з них не має оптимального рішення.

2. "Ознака оптимальності". Щоб допустиме рішення x прямої задачі було оптимальним, необхідно і достатньо, щоб знайшлося таке рішення двоїстої завдання v, що

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



2. Модель задачі лінійного програмування. Постановка задачі: проблеми, проблематики

Меблевий комбінат випускає книжкові полиці А з натурального дерева зі склом, полиці B₁ з полірованої ДСП (деревино-стружечної плити) без скла і полиці B₂ з полірованої ДСП зі склом. Габарити полиць А, B₁ і В₂ наступні: довжина 1230 (d) мм, ширина 260 (w) мм, висота 240 (h) мм (рисунок 1). Розмір листа ДСП 2*3 м.

Рисунок 1 - Габарити полиць, що випускаються меблевим комбінатом

При виготовленні полиць А виконуються наступні роботи: столярні, покриття лаком, сушка, різання скла, упаковка. Всі операції, що виконуються в ході столярних робіт і упаковки, виконуються уручну. Полиці B₁ і В₂ поставляються в торгову мережу в розібраному вигляді. За винятком операції упаковки, решта всіх операцій (виробництво того, що комплектує полиці, різка скла) при виготовленні полиць B₁ і В₂, виконуються на спеціалізованих автоматах.

Трудомісткість столярних робіт по випуску однієї полиці А складає 2,8 (Тр₁) год. Продуктивність автомата, що покриває полиці А лаком, - 4 (Пр₁) полиць в годину, автомата, що ріже скло, - 190 (Пp₂) сколів в годину. Змінний фонд часу автомата для покриття лаком - 7,6 (ФВ₁) год., автомата для різки скла - 7,3 (ФВ₂) год. Сушка полиць, покритих лаком, відбувається протягом доби в спеціальних сушарках, що вміщають 45 (V₁) полиць.На упаковку полиці А потрібно7 (Тр₂) хвилини. У виробництві полиць зайнято 9 (Р₁) столярів і 13 (Р₂) пакувальників.

Продуктивність автомата, що проводить комплектування полиць B₁ і В₂, рівна 9(Пр₃) полиці в годину, а її змінний фонд часу рівний 7,5 (ФВ₃) години, трудомісткість пакувальних робіт складає 10 (Тр₃) хвилини для полиці В₁ і 11 (Тр₄) хвилини для полиці В₂.

Від постачальників комбінат отримує в місяць 405 (Z₁) листів полірованої ДСП, 195 (Z₂) листів ДВП (деревино - волокнистої плити), а також 230 (Z₃) листів скла. З кожного листа ДВП можна викроїти 7 (К₁) задніх стінок полиць B₁ і В₂, а з кожного листа скла - 14 (К₂) стекол для полиць А і В₂ .

Склад готової продукції може розмістити не більше 380 (V₂) полиць і комплектів полиць,причому щодня в торгову мережу вивозиться в середньому 44 (N) полиць і комплектів. На початок поточного місяця на складі залишилося 70 (Ост) полиць, виготовлених раніше. Собівартість полиці А рівна 170 (C₁) грн., полиці В без скла - 125 (C₂) грн., зі склом - 148 (С₃) грн.

Маркетингові дослідження показали, що частка продажів полиць обох видів зі склом складає не меншого 12% (Д) в загальному об'ємі продажів, а місткість ринку полиць вироблюваного типу складає близько 2500 (V₃) штук в місяць. Меблевий комбінат уклав договір на постачання замовникові 60 (З) полиць типу В₂ в поточному місяці.

Складіть план виробництва полиць на поточний місяць . Відомі ціни реалізації полиць: полиця А - 198 (Ц₁) грн., полиця В без скла - 175 (Ц₂) грн., полиця В зі склом - 180 (Ц₃) грн.

2.1 Математична модель задачі лінійного програмування

I етап побудови моделі полягає у визначенні (описі,завданні, ідентифікації) змінних. У даній задачі шуканими невідомими величинами є кількість полиць кожного виду, які будуть вироблені в поточному місяці. Таким чином, x_А - кількість полиць А (шт./міс.); x_B1 - кількість полиць В₁ (шт./міс.); x_B2 - кількість полиць В₂ (шт./міс.).

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

задачі прибуток може бути визначений як різниця між ціною ( Ц₁, Ц₂, Ц₃) і

собівартістю (С₁, С₂, С₃), то ЦФ має вигляд:

III етап побудови моделі полягає в завданні обмежень, що моделюють умови задачі. Всі обмеження даної задачі можна розділити на декілька типів.

1. Обмеження по фонду часу (з використанням трудомісткості робіт)

Ліва частина обмежень по фонду часу є часом, що витрачається на виробництво полиць протягом місяця в кількості x_А, x_B1, x_B2 штук. Права частина обмеження - це фонд робочого часу виконавця роботи (робочого або автомата) за зміну. Нерівність



описує обмеження по фонду часу на виконання столярних робіт. Коефіцієнт 2,8 год./шт. (Тр₁) - це час, що витрачається на столярні роботи при виробництві однієї полиці типу А (трудомісткість); 9 чол. (Р₁) - це кількість столярів, що беруть участь у виробництві; 8 год. (чол. Зм.) - кількість годин роботи однієї людини протягомзміни; 1 зм./день - кількість змін в одному робочому дні; 22 дня/міс. - кількість робочих днів в місяці (таблиця 3).

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

Аналогічно записується обмеження по фонду часу на пакувальні роботи, в якому 13 чол. (Р₂) - це кількість пакувальників:

2. Обмеження по фонду часу (з використанням продуктивності робіт)

3.

Нерівність описує обмеження по фонду часу на покриття лаком полиць типу А. Відмінність обмежень, що враховують дані про продуктивність робіт, від обмежень, що враховують дані про трудомісткість робіт, полягає в тому, що продуктивність необхідно перетворити в трудомісткість. Трудомісткість є величиною, зворотною продуктивності. Коефіцієнт 1/4 (1/Пр₁) при x_A - це кількість годин, що приходиться на покриття лаком однієї полиці типу А. При записі правої частини обмеження враховуємо, що автомат, що виконує покриття лаком, працює не повну зміну (8 год.), а протягом змінного фонду часу 7,6 год. (ФВ₁). Це пов'язано з необхідністю підготовки автомата до роботи і обслуговуванням його після закінчення роботи.

Нерівність описує обмеження по фонду часу на різку скла для полиць типу А і В₂.

Нерівність описує обмеження по фонду часу на виробництво комплектувальних для полиць типу В₁ і В₂.

4. Обмеження по запасу матеріалів, що витрачаються у виробництві (по запасу використовуваних для виробництва полиць деталей)

Нерівність описує обмеження по запасу листів ДСП, що поставляються на комбінат щомісячно. При цьому слід врахувати, що з листа ДСП треба викроювати комплекти (верхня і нижня сторони полиць, 2 бічні сторони) для виробництва полиць. Тому при завданні обмеження має сенс орієнтуватися не на кількість листів ДСП, а на кількість комплектів для полиць, які можна отримати з наявного запасу ДСП. Але оскільки листи ДСП можна розкроювати різними способами і отримувати при цьому різну кількість деталей і комплектів, то позначимо місячний запас комплектів в правій частині як Y_компл. і розглянемо спосіб його чисельного визначення пізніше. В лівій частині обмеження задається кількість комплектів (по одному на полицю), яка необхідна на виготовлення полиць протягом місяця в об'ємі x_B1, x_B2.

Аналогічно обмеженню по ДСП ця нерівність - це обмеження по запасу задніх стінок з ДВП для полиць В₁ і В₂, а нерівність

- обмеження по запасу стекол для полиць А і В₂. На відміну від ДСП листи ДВП і листи скла крояться стандартним способом, і з кожного листа ДВП виходить 7 (К₁) задніх стінок полиць, а з кожного листа скла виходить 14 (К₂) стекол. Щомісячний запас листів ДВП і стекла складає відповідно 195 (Z₂) і 230 (Z₃). При складанні лівих частин обмежень слід врахувати, що на кожну полицю В₁ і В₂ доводиться по одній задній стінці, а на кожну полицю А і В₂ - по 2 скла.

5. Обмеження по місткості допоміжних приміщень і ринку

Ця нерівність є обмеженням по кількості полиць А, які може вміщати сушарка. У правій частині представлена кількість полиць, які можуть бути просушені протягом місяця (у день може бути просушені 45 (V₁) полиць).

Дана нерівність описує обмеження по кількості полиць всіх видів, які може вміщати склад готової продукції. При цьому права частина враховує, що загальна місткість складу зменшена на 70 (Ост) полиць, які залишилися невивезеними з минулого місяця. Крім того, протягом місяця щодня звільнятиметься по 44 (N) місць для полиць.

Дана нерівність описує обмеження по приблизній ємності ринку, рівній 2500 (V3) полицям всіх видів.

6. Обмеження по гарантованому замовленню

Нерівність показує, що необхідно виготовити як мінімум 60 (З) замовлених полиць В₂, а можливо, і більша кількість, але вже для вільного продажу.

6. Обмеження по співвідношенню об'ємів продажів різних товарів

Нерівність показує, що частка полиць А і В₂ в загальному об'ємі полиць, що виробляються для вільного продажу, повинна складати не меншого 12% (Д). До такого висновку приводять результати маркетингових досліджень. Оскільки зі всіх полиць В₂ у вільний продаж поступить лише (x_B2 - 12).

7. Визначення кількості комплектів для полиць В₁ і В₂

Розглянемо детально питання визначення максимально можливої кількості комплектів для полиць В₁ і В₂, яке можна провести з щомісячного запасу ДСП. Залежно від розмірів листів ДСП (2000*3000 мм) і габаритів полиць (1230*260*240 мм) деталі полиць В1 і В2можна викроїти різними способами. Розглянемо три можливі варіанти такого розкрою, представлених на рисунку 2 (затемнені ділянки - це невикористана площа ДСП).

Рисунок 2 - Можливі варіанти розкрою листів ДСП

Згідно 1-му варіанту з одного листа ДСП для полиць В₁ і В₂ можна викроїти 19 деталей верхньої або нижньої стінок, а також 9 деталей бічних стінок. По 2-му варіанту розкрою отримуємо 12 деталей верхньої або нижньої стінок і 36 деталей бічних стінок. По 3-му варіанту розкрою отримуємо 16 деталей верхньої або нижньої стінок і 18 деталей бічних стінок. Позначимо кількість листів ДСП, що розкроєні протягом місяця: по 1-му варіанту через y₁ (лист./міс.); по 2-му варіанту - y₂ (лист./міс.); по 3-му варіанту - y₃(лист./міс.). При виготовленні полиць нам вигідно прагнути до такого розкрою листів ДСП, при якому з отриманих деталей можна укомплектувати максимальну кількість полиць. Кількість комплектів, отриманих з розкроєних деталей, ми раніше позначили через Y_компл. Таким чином, наша мета описується цільовою функцією

L(y) = Y_компл > max (компл./міс.)

Кількість всіх розкроєних листів ДСП не повинна перевищувати 405 (Z₁), тобто запас кожного місяця їх на складі:

y₁ + y₂ + y₃ ? 405(лист./міс.)

При цьому, оскільки в кожен комплект входить одна верхня і одна нижня стінки, кількість нижніх і верхніх стінок, що отримуються при розкрої всіх листів ДСП, повинна бути не менше ніж 2Y_компл:

19у₁ + 12у₂ + 16у₃ ? 2Y_компл

Аналогічний сенс має обмеження, яке задає нижню межу кількості бічних стінок полиць:

9у₁ + 36у₂ + 18у₃ ? 2Y_компл

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

Таким чином, при розв'язанні задачі симплекс - методом ) змінна Y_компл безпосередньо визначає значення ЦФ, а змінні у₁, у₂ і у₃ впливають на зміну значення ЦФ побічно, через обмеження. Вирішивши задачу для варіанту 6, ми отримаємо Y=405компл., після чого зможемо вирішити початкову задачу, модель якої має вигляд:



3. Вибір оптимального варіанту математичної моделі задача лінійного програмування

Визначення оптимального рішення задачі виконано з використанням ПК. Алгоритм пошуку оптимального рішення симплекс-методом було реалізовано засобами мови програмування С++. Текст програми та результати розрахунків наведено в додатках А, В.

Отриманий оптимальний план дає максимальний прибуток в розмірі 28520 гривен і передбачає випуск продукції у такому складі:

*виріб типу А - 0 одиниць;

* виріб типу В1 -1218 одиниць;

*виріб типу В2 - 60 одиниць.

симплекс метод лінійний програмування



Додаток 1

Код програми:

#include <iostream>

using namespace std;

bool ogr(int x1,int x2,int x3)

{

int tp1=28,tp2=7,tp3=10,tp4=11;

int y1=405,y2=0,y3=0;

int p1=9,p2=13;

int pr1=5,pr2=190,pr3=9;

int fv1=7.6,fv2=7.3,fv3=7.5;

int z1=405,z2=195,z3=230;

int k1=7,k2=14;

int v1=45,v2=390,v3=2500;

int n=44;

int ost=70;

if(x1+x2+x3>v2-ost+n*22)

{return 0;}

if(x1+x2+x3>v3)

{return 0;}

if (tp1*x1>1*8*22*p1)

{return 0;}

if ((tp2/60)*x1+(tp3/60)*x2+(tp4/60)*x3>1*8*22*p2)

{return 0;}

if((1/pr1)*x1>1*22*fv1)

{return 0;}

if(2/pr2*x1+2/pr2*x3>1*22*fv2)

{return 0;}

if((1/pr3)*x2+(1/pr3)*x3>fv3*1*22)

{return 0;}

if(x1+(x2-60)<0.12*(x3-60))

{return 0;}

return 1;

}

void main()

{

int s1=205,s2=142,s3=160;

int c1=295,c2=182,c3=220;

long max = 0;

for(int Xa=0;Xa<991;Xa++)

{

for(int Xb1=0;Xb1<500;Xb1++)

{

for(int Xb2=60;Xb2<406-Xb1;Xb2++)

{

if (ogr(Xa,Xb1,Xb2))

{

if(max<(c1-s1)*Xa+(c2-s2)*Xb1+(c3-s3)*Xb2)

{max=(c1-s1)*Xa+(c2-s2)*Xb1+(c3-s3)*Xb2;

cout<<max<<"| Xa="<<Xa<<" Xb1="<<Xb1<<" Xb2="<<Xb2<<endl;

}

}

}

}

}

cout<<"Result = "<<max<<endl;

}



Додаток Б

Цільова функція дорівнює



Висновок

Аналізуючи результати розрахунків приходимо до наступних висновків:

1. Доцільно планувати випуск продукції виду В1 та В2 у кількостях 1218 та 60 одиниць відповідно. Полиці першого виду виробляти не доцільно;

2. Прибуток при такому плані складе 62820 гривен;

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

Дана нерівність описує обмеження по кількості полиць всіх видів, які може вміщати склад готової продукції. При цьому права частина враховує, що загальна місткість складу зменшена на 70 (Ост.) полиць, які залишилися невивезеними з минулого місяця;

4. Так як виріб виду А не планується то вивільняються ресурси часу на виконання робіт по його обробленню. Це обмеження виду:

Нерівність описує обмеження по фонду часу на покриття лаком полиць типу А.

5. Із витрат часу на порізку скла для виробів А та В2також вивільняються години на виконання цих робіт для виробу типу А:

Нерівність описує обмеження по фонду часу на різку скла для полиць типу А і В₂.

6. Аналогічно залишається ресурс ДВП в обсязі 754 од виміру, який би пішов на виготовлення полиць типу А

7. Залишається ресурс - скло, яке також використовується для полиць виду А

Основним питанням підвищення прибутку на підприємстві є вирішення питання складських приміщень. І як показує аналіз, що саме вивезення зі складу полиць типу А і надасть можливість отримати більший прибуток від виробництва і реалізації продукції. Тому що інші ресурси використанні не повністю. Вивільнені кошти від закупівлі матеріалів на полиці типу А необхідно направити на збільшення ресурсу часу на виготовлення комплектуючих для полиць В1 та В2, бо саме цей ресурс використовується на 85 відсотків.

Виходи наступні:

· відмова від випуску полиць типу А та направлення коштів на збільшення ресурсів на виготовлення комплектуючих для В1 та В2;

· розширення складських приміщень;

· пошук споживачів полиць А.

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