Оптимальне планування виробництва методами лінійного програмування

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

УКРАЇНСЬКИЙ ДЕРЖАВНИЙ ХІМІКО-ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ

КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА КІБЕРНЕТИКИ

Пояснювальна записка до дипломної роботи

На тему: ОПТИМАЛЬНЕ ПЛАНУВАННЯ ВИРОБНИЦТВА МЕТОДАМИ ЛІНІЙНОГО ПРОГРАМУВАННЯ

Виконала ст. групи 5 кіб - 77

Кравченко І.М.

Керівник роботи

проф. Кочура Є.В.

Охорона праці

ас. Мітіна Н.Б.

Нормоконтролерас. Сергеєва О.В.

Завідувач кафедри

Огданський М.Ф.

Дніпропетровськ

2008

Реферат

Дипломна робота: 74 с., 7 рис., 18 табл., 2 додатки, 17 джерел.

Об'єкт дослідження - оптимальне планування випуску продукції на ЗАТ „ЕРЛАН”.

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

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

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

Для оптимізації використовуємо стандартний засіб Excel „Пошук рішення”.

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

ОПТИМАЛЬНИЙ ПЛАН ВИПУСКУ, ЛІНІЙНЕ ПРОГРАМУВАННЯ, МЕРЕЖЕВИЙ ГРАФ, ПОШУК РЕЗЕРВУ ЧАСУ, ОПТИМАЛЬНЕ ВИКОРИСТАННЯ РЕСУРСІВ.

Зміст

Вступ

1. Характеристика об'єкта дослідження та аналіз його функціонування

1.1 Історія виникнення фірми

1.2 Матеріально-технічна база підприємства

1.3 Організація управління ЗАТ «Ерлан» ТМ «Біола»

1.4 Кадри підприємства

1.5 Технологія виробництва

1.6 Виробнича потужність підприємства і обсяг виробництва

2. Економіко-математична постановка задачі

2.1 Алгоритм рішення задачі про оптимальне використання ресурсів при внутрішньопідприємницькому плануванні

2.2 Оптимальне використання ресурсів при внутрішньопідприємницькому плануванні

2.3 Алгоритм приведення матричної гри до задачі лінійного програмування

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

2.5 Мережний графік виробництва. Пошук резервів зменшення критичного шляху. Практичне застосування сіткового планування

2.6 Розробка плану-графіку заходів та оцінка ефективності плану

3. Охорона праці

3.1 Оцінка умов роботи економіста планово-економічного відділу підприємства ЗАТ «ЕРЛАН»

3.2 Заходи по створенню безпечних умов праці економіста планово-економічного відділу

3.3 Характеристика об'єкта з пожежонебезпеки та вибухонебезпеки

3.4 Протипожежні заходи

3.5 Засоби і способи гасіння пожеж

Висновок

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

Додаток А

Додаток Б

Вступ

Поступовий перехід України від централізовано-планової системи господарювання до ринкової по-новому ставить питання про методи ведення економіки підприємства. Традиційні структури і уклади змінюються. У цей час керівники підприємств, вивчаючи і формуючи те, що називається цивілізованими формами ринкових відносин, стають своєрідною «архітектурою» розвитку нових господарських зв'язків і методів ведення економіки підприємства.

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Характеристика об'єкта дослідження та аналіз його функціонування

1.1 Історія виникнення фірми

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

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

Перші кроки у виробництві продукції «Ерлан» здійснив в 1997 році. У 1999 і 2003 рр. була проведена реконструкція, і запущені дві сучасних лінії розливу. На сьогоднішній день завод являє собою великий виробничий комплекс, який вражає не тільки своїм розмахом, а і новизною і лаконічністю дизайну. У виробничих цехах це сліпуча чистота і нове обладнання, що вимагає незначну кількість обслуговуючого персоналу. (Більш докладну інформацію читайте в розділі «Виробництво»). На території заводу реконструйовані адміністративні корпуси, створений красивий куток відпочинку.

На підприємстві розробляється і впроваджується система управління якістю ISO 9001. До того ж “Ерлан" має свою акредитовану лабораторію. Піклується про те, щоб продукт відповідав всім вимогам якості, а виробництво було довершеним.

Результатом цього є успіх на різних конкурсах:

· диплом за високу якість, широкий асортимент і оригінальне художнє оформлення представленої продукції «Food & drinks», 1999 р.;

· диплом переможця в конкурсі «Дніпровська якість 2001»;

· диплом лауреата і гран-прі загальнонаціонального конкурсу «Віща проба - 2002» за високу якість і екологічну чистоту мінеральної питної лікувально-столової води «Знаменівська», а також за виробництво високоякісних безалкогольних сильно газованих напоїв з доданням натурального соку під торговою маркою «Біола».

Підприємство «Ерлан», ТМ «Біола» було створено в 1997 році. Створення бази підприємства почалося в м. Підгороднє. Була придбана свердловина мінеральної води «Знаменівська», яка знаходиться в курортній зоні «Солоний Лиман». На початку своєї діяльності підприємство мало одну лінію по розливу безалкогольних напоїв і мінеральної води.

У 1999 році була проведена реконструкція виробництва, придбано і введено в експлуатацію імпортне обладнання фірм:

· “SIDEL", Франція;

· “MELEGARI", Італія;

· “ADUE", Італія;

продуктивністю 5 тисяч пляшок в годину. З цього часу виробництво напоїв здійснюється з використанням цукрового сиропу.

У середині 2001 року введена в дію нова більш могутня лінія розлива безалкогольних напоїв і мінеральної води, укомплектована обладнанням фірм:

· «KHS Maschinenund Anlagenbau AG GmbH», Німеччина;

· “SIDEL", Франція;

· «DOHLER», Німеччина;

· «BERKEFELD Filter Anlagenbau GmbH», Німеччина; продуктивністю 10 тисяч пляшок в час різної місткості. Процес виробництва здійснюється при використанні комп'ютерних систем, що дозволяє виключити помилки персоналу і гарантує суворий контроль за всіма етапами технологічного процесу[17].

1.2 Матеріальна база підприємства

Для того щоб визначити технологічну структуру, треба знати скільки О.Ф рахуються в структурних підрозділах підприємства. Структура підрозділів показана на рисунку 1.1:

Рис.1.1 Структура підрозділів підприємства

Коротка характеристика підрозділів

Адміністративно-Управлінський персонал (АУП) - Щоб управляти організацією, необхідно певним чином зв'язати цілі, людей і види виконуємої ними роботи між собою. Ці функції виконує АУП, де складаються посадові інструкції на всіх членів організації, в яких обмовляються: права, відповідальність і обов'язки кожного.

Цех №1 водопідготовки.

Цех №2 купажування (приготування сиропу).

Цех №3 розливу напоїв.

Цех № 4 виробництво вуглекислоти (СО2).

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

Ремонтні служби - слюсаря, наладники, фахівці по КИПіА, електронщики.

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

Їдальня насамперед обслуговує працівників підприємства і працює по режиму роботи підприємства.

1.3 Організація управління ЗАТ «Ерлан» ТМ «Біола»

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

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

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



Рис.1.2. Організаційна структура управління

1.4 Кадри підприємства

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

Що впливає на кількість і професійний склад персоналу підприємства?

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

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

Адміністративно-управлінський персонал (АУП);

Інженеро-технічні працівники (ІТР);

Службовці;

Робітники;

Обслуговуючий персонал.

У адміністративно-управлінський персонал входять керівники всіх рівнів майстра, начальники цехів, директори і їх заступники. На даному підприємстві це:

Рада директорів складається з двох чоловік генерального директора і президента;

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

Заступники генерального директора і вхідні в їх склад відділи:

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

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

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

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

До ІТР відносяться інженери, конструктори, техніки, тобто всі, що займаються Інженерно-технічними розробками, впровадженням і контролем якості технологічного процесу. На підприємстві це передусім:

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

Виробничий відділ - розробляє і контролює технологічний процес.

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

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

Робітники - це персонал підприємства, зайнятий безпосереднім процесом виробництва товарів і послуг.

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

1.5 Технологія виробництва

На підприємстві випускають 3 види продукції: напій на основі цукру, напій на основі цукорозамінника, сік. Розлив напоїв і соку проводиться на різних видах обладнання.

Лінія по розливу напоїв 30000 од./година.

Лінія по розливу соку 18000 од./година.

Необхідно відмітити, що по рецептурі, дані представлені в таблицях 1 і 2 розраховані на місткість (танк для купажного сиропу)15 м3.

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

Вихід готового напою 90000 л.

Таблиця 1.1 - Вартість компонентів напою на основі цукру

Найменування компонента	Ціна за 1 кг (грн)	Кількість компоненту	Ціна інгредієнту
цукор	1,5	8104	12156
лимонна кислота	4	94,9	379,6
бензонат Na	4	13,44	53,76
ароматизатор	5	42	210
колір	10	16,8	168
компонент (цитрус)	7	151,2	1058,4
вода	0,25	13000	3250

Таблиця 1.2 - Вартість компонентів напою на основі цукорозамінника

Найменування компонента	Ціна за 1 кг (грн)	Кількість компоненту	Ціна інгредієнту
цукорозамінник	100	30	3000
лимонна кислота	4	94,9	379,6
бензонат Na	4	13,44	53,76
ароматизатор	5	42	210
колір	10	16,8	168
компонент (цитрус)	7	151,2	1058,4
вода	0,25	14000	3500

У таблиці 1.3 змішуються інгредієнти для соку.

Вихід готової продукції 15000 л.

Таблиця 1.3 - Вартість компонентів соку

Найменування компонента	Ціна за 1 кг (грн)	Кількість компоненту	Ціна інгредієнту
сіковий концентрат	14	2000	28000
аскорбінова кислота	4	40	160
вода	0,25	13500	3375

1.6 Виробнича потужність підприємства і обсяг виробництва

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

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

(1.1)

де, М - виробнича потужність виражена в натуральних одиницях;

t_Э - максимально можливий річний фонд часу роботи однієї машини.

N - кількість однотипного ведучого обладнання.

Тод - норма часу на виробництво одиниці продукції (трудомісткість виготовлення однієї одиниці продукції).

Розрахунок для обладнання по виробництву напоїв:

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

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

(1.2)

Розрахунок для обладнання по виробництву соку:

2. Економіко-математична постановка задачі

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

Ціллю даної дипломної роботи є :

· Підвищення якості та ефективності роботи, забезпечення конкурентоспроможності організації та виготовляємого нею продукту;

· Створення вимог та практичне, реальне забезпечення економічного зростання, нарощування економічного потенціалу організації;

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

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

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

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

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

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

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

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

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

В даній дипломній роботі для оптимального планування виробництва я використовую:

· Подвійне лінійне програмування;

· Теорія гри;

· Мережеве планування.

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

Підприємство випускає n виробів. Для їх виробництва потрібно m видів ресурсів. Ці ресурси обмежені та складають в плановий період b_1, b_{2, …,}b_m умовних одиниць [9].

Відомо також технологічні коефіцієнти a_ij, які вказують, скільки одиниць і-го ресурсу потрібно для виробництва одиниці виробу j-го виду (і-го=1,2,...,m, j=1,2,…,n).

Хай прибуток, отримує мий при реалізації одиниці виробу j-го виду, дорівнює c_ij.

В плановий період всі показники: a_ij,c_j,b_m мають бути незмінними.

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

Зведемо дані задачі в таблицю.

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

Припустимо, що підприємство буде виготовляти x₁ одиниць виробів виду 1, x₂ одиниць виробів виду 2,..., x_n одиниць виробів виду n.

Потрібно скласти оптимальний план роботи підприємства X=(x₁,x₂,…,x_n), одже знайти таке значення змінних x₁,x₂,…, x_n, щоб забезпечити підприємству отримання максимального прибутку від реалізації всієї продукції та щоб на її виробництво було достатньо ресурсів які маються в розпорядженні.

Якщо сумарний прибуток представити у вигляді цільової функції

F = c₁x₁+c₂x₂+…+c_nx_n

та врахувати, що змінні x₁,x₂,…,x_n не можуть приймати від'ємних значінь, то математично задача зведеться до наступного.

Найти максимум функції

F = c₁x₁+ c₂x₂+…+c_nx_n

при обмеженнях

(2.1)

.

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

Так як змінні x₁,x₂,…,x_n належать до функції F , то в систему обмежень тільки в першій степені, а показники a_ij,c_j,b_m є постійними в плановому періоді, то перед нами задача лінійного програмування.

2.2 Оптимальне використання ресурсів при внутрішньовиробничому плануванні

Для виробництва напоїв та соку ЗАТ “ЕРЛАН” використовує компоненти представлені у таблиці , запаси якого на плановий період обмежені.

В таблиці 2.1 приведені технологічні коефіцієнти, одже витрати кожного виду сировини на виробництво одиниці кожного виробу та прибуток від реалізації одиниці виробу кожного виду[7].

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

Позначимо через x_1, x₂, x₃ кількість одиниць.

F = 1.5x₁+x₂+2.2x₃

При відповідних обмеженнях:

Таблиця 2.1 - Оптимальне використання ресурсів при внутрішньовиробничому плануванні

Кількість	Нап/цукор	Нап/цук.зам.	Сік
	990000	0	0
Най. компоненту	Склад	Використано
Цукор	180000	89100	0,09	0	0
Цукрозамінник	660	0	0	0,00033	0
Бензоат Na	600	138,6	0,00014	0,00014	0
Ароматизатор	1900	455,4	0,00046	0,00046	0
Колір	740	178,2	0,00018	0,00018	0
Компон. “цитрус”	6655	1663,2	0,00168	0,00168	0
Соковий концентрат	44000	0	0	0	0,133
Аскорбінова кислота	880	0	0	0	0,0026
Вода	891000	891000	0,9	1	0,864

Таблиця 2.2 - Отриманий результат

По видам виробів:	1485000 грн.	0 грн	0 грн
Всього:	1485000 грн.

2.3 Алгоритм приведення матричної гри до задачі лінійного програмування

Для побудови алгоритмів розв'язання задач матричних ігор використовується властивість оптимальних змішаних стратегій: оптимальна змішана стратегія першого гравця гарантує йому виграш не менший ціни гри за будь-яких стратегій другого гравця і рівній ціні гри за оптимальної стратегії другого гравця. Використання названої властивості матричних ігор дає можливість привести задачу пошуку оптимальних змішаних стратегій до задачі лінійного програмування. Розглянемо одну з методик побудови відповідного алгоритму[9].

Маємо матричну гру за відомої матриці

H = {h_ij} (I=1,2,…, m; j=1,2,…, n).

Перший гравець має чисті стратегії А_1, А_2,..., А_m, другий - В_1, В₂,...,В_n. Необхідно знайти оптимальні змішані стратегії

S_a⁰ =(p₁⁰,p₂⁰,…, p_m⁰) та S_b⁰ =(g₁⁰, g₂⁰,…, g_m⁰),

де p_i⁰ та g_j⁰ - ймовірності використання відповідних чистих стратегій гравцями.

Використовуючи можливість афінних перетворень матриці, без застережень можна вважати, що h_ij>=0 і V >0.

Якщо перший гравець використовує свою оптимальну змішану стратегію

S_a⁰=(p₁⁰, p₂⁰,…,p_m⁰)

проти будь-якої чистої стратегії B_ij другого гравця, то його очікуваний гарантований виграш, тобто математичне сподівання виграшу

H_j =.

Наголосимо, що значення {p_i⁰} поки що невідомі. За оптимальної стратегії

S_a⁰= (p₁⁰, p₂⁰,…, p_m⁰)

гравця А його середні виграші за будь-якої чистої стратегії супротивника будуть не менше ціни гри V, тому можемо записати і гарантувати виконання системи:

 (2.2)

Кожну з наведених нерівностей помножимо на 1/V і введемо нові зміни:

x₁=p₁⁰/v; x₂=p₂⁰/v;……;x_m=p_m⁰/v.

За нових змінних система запишеться так:

(2.3)

Скориставшись умовою

p₁⁰+p₂⁰+…+p_m⁰ =1

(сума всіх ймовірних дорівнює ймовірності достовірної події) та, маємо:

x₁+x₂+…+x_m =1/v.

Мета першого гравця - максимізувати гарантований виграш, тобто ціну гри V. Але максимізація ціни гри V обумовлює мінімізацію величини 1/V, тому розв'язання задачі пошуку величин x₁,x₂…, x_m можна сформулювати так: знайти величини змінних x_i так, щоб вони задовольняли системі лінійних обмежень за умови досягнення найменшого значення лінійної функції:

Z=x₁+ x₂+…+ x_m.

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

та максимальний гарантований виграш V.

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

другого гравця використовуються умови:

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

2. гравець В прагне мінімізувати свій гарантований програш, тобто досягти максимуму величини 1/V.

За названих умов змінні g₁⁰, g₂⁰,…, g_n⁰ задовольняють нерівностям:

(2.4)

Якщо ввести нові змінні

то система матиме вигляд:

(2.5)

До того ж змінні мають задовольнити умові:

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

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

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

ЗАТ «Біола» випускає три види продукції: напій на основі сиропу з цукром, напій на основі сиропу з цукрозамінником, сік.

У поточному місяці прогнозуються три стани ринку. У таблиці 2.3 представлені ціни на різні види виробів в умовах різних станів ринку.

Таблиця 2.3 - Прогнозовані стани ринку

Види виробів	1	2	3
Напій на основі цукру	1,5	2	1
Напій на основі цукрозамін.	1	0,8	1,7
Сік	2,2	2,5	1,3

За вимогами: першим гравцем є ЗАТ «ЕРЛАН», другим - ринок. Найдемо нижню та верхню ціну гри:

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

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

Позначимо змішану стратегію ЗАТ «ЕРЛАН» вектором U(U₁, U₂, U₃), а ринку - вектором Z(Z₁, Z₂ Z₃). Тут U₁, U₂, U₃ відносні частоти використання 1-м гравцем відповідно 1,2,3 стратегій, а Z₁, Z₂ Z₃ відносно частоти використання 2-м гравцем відповідно 1,2,3 стратегій[16].

Теорема: Для того, щоб число V було ціною гри, a u^* та z^* - оптимальними стратегіями, необхідно та достатньо виконання нерівність

 j= (2.6)

I= (2.7)

Розглянемо нашу задачу визначену матрицею:

А=

Розділимо обидві частини на V отримаємо:

(2.8)

j=

Введемо нове позначення

, I= (2.9).

Тоді

j=, I= (2.10).

Використавши нове позначення, перепишемо умову

у вигляді

(2.11).

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

(2.12);

j= (2.13)

I= (2.14).

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

(2.15)

Складемо задачу обернену першій (система рівнянь для другого гравця) з наступними умовами:

(2.16)

j= (2.17)

 j=.

(2.18)

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

Застосуємо симплекс метод, знайдемо рішення подвійної задачі лінійного програмування.

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

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

БЗ		Y1	Y2	Y3	Y4	Y5	Y6	bi
		1	1	1	0	0	0
Y4	0	1.5	1	2.2	1	0	0	1
Y5	0	2	0.8	2.5	0	1	0	1
Y6	0	1	2.5	1.3	0	0	1	1
	Zi	-1	-1	-1	0	0	0

- коефіцієнт при базисній змінній;

bi - вільні члени системи рівнянь;

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

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

БЗ		Y1	Y2	Y3	Y4	Y5	Y6	bi
		1	1	1	0	0	0
Y4	0	0	0.4	0.33	1	-0.75	0	0.25
Y1	1	1	0.4	1.25	0	0.5	0	0.5
Y6	0	0	1.3	0.05	0	-0.5	1	0.5
	Zi	0	-0.6	0.25	0	0.5	0	0.5

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

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

БЗ		Y1	Y2	Y3	Y4	Y5	Y6	bi
		1	1	1	0	0	0
Y4	1	0	0	0.23	1	-0.6	-0.31	0.1
Y1	1	1	0	1.23	0	0.65	-0.31	0.35
Y2	0	0	1	0.04	0	-0.38	0.77	0.38
	Zi	0	0	0.27	0	0.27	0.46	0.73

Перевіримо індексний рядок на предмет наявності в ній негативних елементів, якщо їх немає, то це показує, що отримане рішення, є оптимальним [1].

На основі даних отриманих в останній таблиці знайдемо рішення прямої і зворотної задачі:

Для визначення стратегій і ціни гри скористаємося рішенням пари подвійних задач:

(2.19)



Оскільки ціна гри попадає в межі вказані раніше, означає задача вирішена вірно.

Перерахуємо оптимальні стратегії підприємства по виразам:

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

Виходячи з того, що , , вірогідності застосування першим гравцем відповідно 1, 2 та 3 стратегії, одже сума повинна бути рівна 1. як ми бачимо це справедливе ствердження.

Враховуючи постановку задачі інтерес представляє стратегію підприємства, одже вектор . Для даного підприємства оптимальною буде наступна змішана стратегія: у даному місяці необхідно виробляти напої в співвідношенні 1:1.5, а виготовлення соку тимчасово зменшити до мінімуму, тому що термін придатності соку менше (напій-6 міс.; сік - 3 міс.) [6].

2.5 Мережний граф виробництва. Пошук резервів зменшення критичного шляху. Практичне застосування сіткового планування

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

Така система є найбільш удалим прикладом для розгляду.

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

Джерелами ефективності розробки й впровадження системи є:

скорочення трудомісткості обробки інформації при прогнозуванні й аналізі;

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

- скорочення часу аналізу альтернативних стратегічних рішень і вибору найбільш раціонального

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

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

Розглянута в даній роботі система призначена для впровадження в структурі муніципальних органів керування житлово-комунальною сферою території, але є універсальною з погляду об'єкта керування й може бути для будь-якої адміністративно-територіальної одиниці (АТО), будь те муніципальний район, місто, регіон, область [15].

Мережна модель і методи її побудови

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

1

i j 3 4

2

(а) (б)

Рис. 2.1 - Приклад графічного зображення операцій

На рисунку а наведений типовий приклад графічного відображення операції i, j з початковою подією i і кінцевою подією j. На рисунку б показаний інший приклад, з якого видно, що для можливості початку операції (3, 4) потрібне завершення операцій (1,3) і (2, 3). Протікання операцій у часі задається порядком нумерації подій, причому номер початкової події завжди менше номера кінцевого. Такий спосіб нумерації особливо зручний у виконанні обчислень на ЭВМ.

Правила побудови мережної моделі.

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

Правило 2. Жодна пара операцій не повинна визначатися однаковими початковою й кінцевою подіями. Можливість неоднозначного визначення операцій через події з'являється у випадку, коли дві або більше числа операції припустимо виконувати одночасно. Приклад цього випадку наведений на рисунку 2.2а, де операції А и В мають однакові початкова й кінцева події. Щоб виключити таку «помилку» між А и кінцевим (початковим) подією або між У и кінцевим (початковим) подією, уводиться фіктивна операція D . На рисунку 2.2б ілюструє різні варіанти введення такої фіктивної операції D. У результаті операції А и В визначаються тепер однозначно парою подій, що відрізняються або номером початкового, або номером кінцевої події. Варто звернути увагу на те, що фіктивні операції не вимагають витрат ні часу, ні ресурсів.

(a) (б)

Рис. 2.2 - Введення фіктивної операції

Фіктивні операції дозволяють також правильно відображати логічні зв'язки, які без їхньої допомоги не можна задати на мережі. Припустимо, що в деякій програмі операції А и В повинні безпосередньо передувати З, а операції Е безпосередньо передує тільки В. На рисунку 3 а ці умови відбиті невірно, тому що, хоча впорядкування між А. В і З показані правильно, із цього фрагмента треба, що операції Е повинні безпосередньо передувати обидві операції А и В. Правильне подання зазначених умов дає фрагмент, зображений на рисунку б у якому використається фіктивна операція D. Оскільки на операцію D не затрачаються ні час, ні ресурси задані відносини впорядкування виконуються.



(а) (б)

Рис. 2.3 - Введення фіктивної операції.

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

а) Які операції необхідно завершити безпосередньо перед початком розглянутої операції?

б) Які операції повинні безпосередньо випливати після завершення даної операції?

в) Які операції можуть виконуватися одночасно з розглянутої?

Це правило не вимагає пояснень. Воно дозволяє перевіряти (і перевіряти ще раз) відносини впорядкування в процесі побудови мережі[10].

Основи розробки й побудови мережного плану

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

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

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

(2.20),

- коефіцієнт напруженості найкоротшого шляху;

- тривалість найкоротшого шляху, ;

- тривалість критичного шляху, .

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

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

Тепер встає проблема, - а як знайти роботи, що належать найкоротшому шляху, щоб мати можливість про складання їхньої тривалості? Вирішити дану проблему, для людини, інтуїтивно або простим перебором варіантів, дуже проблематично, особливо при великий, сильно розгалуженій структурі сіткового графіка. Найчастіше й ЕОМ упоратися із цим завданням не може, у силу того, що її швидкодія обмежена, а число всіх можливих варіантів шляхів сіткового графіка, уже при ста подіях, може досягати мільйонів або навіть сотень мільйонів [15].

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

Сіткове планування

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

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

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

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

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

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

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

- ранні й пізні строки настання подій;

- ранні й пізні строки початку й закінчення робіт;

- резерви часу робіт і подій.

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

1-2 Доставка сировини на підприємство.

1-8 Доставка PET заготівель.

2-3 Підготовка води.

2-4 Підготовка білого сиропу.

3-5 Контроль якості води.

4-5 Контроль білого сиропу.

6-7 Розлив.

7-11 Закупорка пляшок.

9-10 Подача PET пляшок на розлив.

10-7 Підготовка PET пляшок до розливу.

12-13 Нанесення кінцевого терміну реалізації.

13-14 Формування і упаковка пляшок в паки.

15-16Транспортировка готової продукції на склади.

Таблиця 2.7 - Тривалість кожної роботи

№ роботи	тривалість	№ роботи	тривалість
1-2	8	7-11	2
1-8	4	8-9	2
1-11	1	9-10	0,5
2-3	6	10-7	1
2-4	3	11-12	2
2-5	3	12-13	1,5
3-5	1	13-14	5
4-5	1	14-15	3
5-6	4	15-16	2
6-7	3

Проведемо розрахунок основних показників мережного графіка, а саме:

1. Критичного шляху;

Послідовність робіт що лежать на критичному шляху визначає найбільшу тривалість технологічного процесу, що розглядається. Критичним шляхом даного мережевого графіка є шлях L(1,2,3,5,6,7,11,12,13,14,15,16) довжина якого дорівнює 37,5 годин.

2. Ранній термін здійснення події;

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

(2.21) ,

- ранній строк настання розглянутої події, ;

i - номер розглянутої події;

j - номера попередніх подій, з'єднаних з розглянутими роботами;

- ранній строк настання j-ї попередньої події, дн.

- тривалість роботи, що з'єднує j-а попередня подія з розглянутим, дн.

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

Таблиця 2.8 - Ранній термін здійснення події

Подія j	tp(j)	Подія j	tp(j)
1	0	9	6
2	8	10	6,5
3	14	11	24
4	11	12	26
5	15	13	27,5
Подія j	tp(j)	Подія j	tp(j)
6	19	14	32,5
7	22	15	35,5
8	4	16	37,5

3. Пізній строк настання події

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