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

Зміст

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

Перелік використовуваних скорочень

Вступ

. Огляд науково-технічної літератури

.1 Історія розвитку економіко-математичного планування

.2 Необхідність рішення задач лінійного програмування

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

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

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

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

.2 Рішення задачі оптимізації за допомогою засобу "Пошук рішення" в Microsoft Excel

.2.1 Процедура пошуку рішення

.2.2 Параметри засобу "Пошук рішення"

. Задача планування виробництва

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

.2 Математичний опис поставленої задачі планування симплекс-методом

.3 Рішення поставленої задачі планування виробництва

.3.1 Перевірка ознаки допустимості і оптимальності базису

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

.3.3 Перерахунок симплекс-таблиці

. Програма для вирішення задачі ЛП Симплекс методом

.1 Опис

.2 Графічне представлення програми

.3 Робота з програмою

.4 Схема програми

.5 Результат рішення задачі планування виробництва

Висновки

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

Додаток

Перелік використовуваних скорочень

ЛП - Лінійне програмування;

ЗЛП - Завдання лінійного програмування;

ОДР - Область допустимих рішень;Excel - Microsoft Excel;

ОС - Операційна система.

 

Вступ

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

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

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

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

поліпшення фінансових показників;

підвищення рівня виробництва;

нарощування обсягів виробництва.

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

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

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

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

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

Планом випуску продукції визначаються:

Кількісні показники виробництва;

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

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

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

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

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

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

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

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

1. Огляд науково-технічної літератури

1.1 Історія розвитку економіко-математичного планування

У 1938-1939 рр. ленінградського математика (згодом академік, лауреат Ленінської, Державних і Нобелівською премій) Л.В. Канторович в результаті аналізу ряду проблем організації і планування виробництва сформулював новий клас умовно-екстремальних завдань і запропонував методи їх рішення. Так належало початок нової галузі прикладної математики лінійному програмуванню. У пізніших роботах Л.В. Канторович розширив сферу застосування лінійного програмування в соціалістичній економіці, сформулювавши завдання галузевого і народногосподарського оптимального планування. А через два десятиліття після свого виникнення лінійне програмування стало основним інструментом плановоекономічних рішень на усіх рівнях соціалістичного народного господарства.

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

Далі методи планування продовжували удосконалюватися, але тільки розвиток обчислювальної техніки у кінці 50-х рр. дозволив зробити планові багатоваріантні розрахунки досить поширеними. Важливу роль в організації і пропаганді економіко-математичних досліджень в цей період зіграв академік В.С. Немчинов. Саме у ці роки отримують розвиток деякі розділи прикладної математики, пов'язані з рішенням оптимізаційних завдань: лінійне і нелінійне програмування, теорія оптимального управління та ін. У 60-і рр. основна увага дослідників зосереджується на розробці оптимізаційних моделей різних типів і їх практичному застосуванні до рішення завдань планування. Було побудовано велику кількість економіко-математичних моделей, на основі яких проведені розрахунки по складанню реальних оптимальних планів (оптимальні плани перевезень, експлуатації рухливого складу транспорту, використання палива, завантаження устаткування підприємств; оптимальне розміщення окремих галузей промисловості і підприємств галузі; оптимальне планування і розподіл капіталовкладень і т. д.), що дало великий народногосподарський ефект. Разом з розширенням сфери застосування математичних моделей в економіці і плануванні здійснюється процес удосконалення моделей і використання адекватнішого математичного апарату: перехід від статичних моделей до динамічних, від жорстко детермінованих до стохастичних моделей, що враховують випадковість і невизначеність економічних процесів, застосування дискретного програмування, методів статистичного моделювання, створення нових алгоритмів, що дозволяють вирішувати завдання великої розмірності.

1.2 Необхідність рішення задач лінійного програмування

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

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

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

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

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

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

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

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

оптимізації виробничої програми підприємств;

оптимального розміщення і концентрації виробництва;

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

управління виробничими запасами;

і багато інших, що належать сфері оптимального планування.

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

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

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

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

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

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

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

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

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

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

за умов

 при .

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

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

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

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

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

2.1 Алгоритм симплекс-методу

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

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

Таблиця (*)

#№	Базисні стовпці	Bs	Базисне рішення Xs	C1	C2	Cm	Cm+1	Ck	Cn
				A1	A2	Am	Am+1	Ak	An
1	A1	100
2	A2	010
l	Al	000
m	Am	001
			Оцінки

Крок 2. Вичислення характеристичних різниць (оцінок) за формулами і запис оцінок в -й рядок симплекс-таблиці.

Крок 3. Обчислення оцінки , що задовольняє умові, :

Якщо усе , то відповідно до виконання критерію оптимальності вектор - оптимальне рішення, і далі слід перейти до кроку 9, інакше - до кроку 4.

Крок 4. Обчислення нового базисного рішення  з умови:

Крок 5. Обчислення компоненту нового базисного рішення  за формулами:

Крок 6. Обчислення елементів нової симплекс-таблицы для -ої ітерації методу по формулах:

Крок 7. Коригування симплекс-таблицы з урахуванням змін коефіцієнтів цільової функції, відповідних новому базисному рішенню. Формуємо таблицю (**).

Таблиця (**)

##№	Базисні стовпці	Базисне рішення Xs_C1C2Cmm+1CkCn
				A1	A2	Am	Am+1	Ak	An
1	A1	100
2	A2	010
l	Al	000
m	Am	001
			Оцінки

Крок 8. Перехід до кроку 2.

Крок 9. Зупинка, реєстрація оптимального рішення.

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

2.2 Рішення задачі оптимізації за допомогою засобу "Пошук рішення" в Microsoft Excel

Потужним засобом аналізу даних MS Excel є надбудова Solver (Пошук рішення). З її допомогою можна визначити, при яких значеннях вказаних впливаючих осередків формула в цільовому осередку набуває потрібного значення (мінімальне, максимальне або рівне якій-небудь величині). Для процедури пошуку рішення можна задати обмеження, причому не обов'язково, щоб при цьому використовувалися ті ж впливаючі осередки. Для розрахунку заданого значення застосовуються різні математичні методи пошуку. Ви можете встановити режим, в якому набутих значень змінних автоматично заносяться в таблицю. Крім того, результати роботи програми можуть бути оформлені у вигляді звіту. Програма "Пошук рішень" (у оригіналові Excel Solver) - додаткова надбудова табличного процесора MS Excel, яка призначена для вирішення певних систем рівнянь, лінійних і нелінійних завдань оптимізації, використовується з 1991 року. Розмір завдання, яке можна вирішити за допомогою базової версії цієї програми, обмежується такими граничними показниками:

кількість невідомих (decision variable) - 200;

кількість формульных обмежень (explicit constraint) на невідомих - 100;

кількість граничних умов (simple constraint) на невідомих - 400.

Розробник програми Solver, компанія Frontline System, вже давно спеціалізується на розробці потужних і зручних способів оптимізації, вбудованих в середу популярних табличних процесорів різноманітних фірм-виробників (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).

Висока ефективність їх застосування пояснюється інтеграцією програми оптимізації і табличного бізнес-документу. Завдяки світовій популярності табличного процесора MS Excel вбудована в його середовище програма Solver є найбільш поширеним інструментом для пошуку оптимальних рішень у сфері сучасного бізнесу. Засіб пошуку рішення Microsoft Excel використовує алгоритм нелінійної оптимізації Generalized Reduced Gradient (GRG2), розроблений Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) і Аланом Уореном (Allan Waren, Cleveland State University), алгоритми симплексного методу і методу "branch - and - bound" для вирішення лінійних і цілочисельних завдань з обмеженнями розроблені Джоном Уотсоном (John Watson) і Деном Филстра (Dan Fylstra) з Frontline Systems, Inc.

2.2.1 Процедура пошуку рішення

У меню "Сервіс" в розділі "Надбудови" необхідно активізувати функцію "Пошук рішення".

Створіть таблицю з формулами, які встановлюють зв'язки між осередками. (див. Мал. 1)

Виділите цільовий осередок, який повинен набути необхідного значення, і виберіть команду "Пошук рішення". Поле Set Target Cell (Встановити цільовий осередок) діалогового вікна надбудови Solver (Пошук рішення), що відкрилося, міститиме адресу цільового осередку.

Встановите перемикачі Equal To (Рівною), задаючі значення цільового осередку, - Мах (максимальному значенню), Min (мінімальному значенню) або Value of (значенню). У останньому випадку введіть значення в поле справа.

Вкажіть в полі By Changing Cells (Змінюючи осередки), в яких осередках програма повинна змінювати значення у пошуках оптимального результату.

Створіть обмеження в списку Subject to the Constraints (Обмеження). Для цього клацніть на кнопці Add (Додати) і в діалоговому вікні Add Constraint (Додавання обмеження) визначите обмеження.

Мал. 2 Діалогове вікно надбудови "Пошук рішення"

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

Мал. 3 Вікно параметрів надбудови "Пошук рішення"

Клацнувши на кнопці Solver (Виконати), запустите процес пошуку рішення.

Мал. 4 Результати пошуку рішення

2.2.2 Параметри засобу "Пошук рішення"

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

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

Відносна погрішність - визначає точність обчислень. Чим менше значення цього параметра, тим вище точність обчислень.

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

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

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

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

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

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

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

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

Оцінка лінійна - виберіть цей перемикач для роботи з лінійною моделлю.

Оцінка квадратична - виберіть цей перемикач для роботи з нелінійною моделлю.

Різниці прямі - використовується в більшості завдань, де швидкість зміни обмежень відносно невисока. Збільшує швидкість роботи засобу Пошук рішення.

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

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

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

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

3. Задача планування виробництва

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

3.1 Економічна постановка задачі планування виробництва

Сільськогосподарське підприємство ТОВ "ОльвіяЛатІнвест" виробляє 6 типів продукції, такі як: озима пшениця, озимий ячмінь, кукурудза, озиме жито, соняшник, ярий ячмінь. Відомо що запас посівних площ складає 1500 га. У розпорядженні підприємства є 5 складів для зберігання зерна, тік для його просушування, зважування і розподілу, сільськогосподарська техніка у розмірі 10 тракторів МТЗ- 920, автоматизованого трактора САТ- 865, сівалка точного висіву Borault - 8810, 8 автомобілів КАМАЗ, погружчик JCB, 3 автобуси Газель. Також є усі необхідні агрегати для ведення польових робіт. Недоліком є відсутність зернозбиральних комбайнів. Оскільки оренда цієї техніки дуже дорога, фірма може собі дозволити 4 комбайни. Що цілком достатньо для цих площ виробництва.

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

 - витрати на виробництво грн.

 - площа посівів га.

 - врожайність т.

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

Більш детальні дані можна знайти в технологічних картах виробництва. (Додаток 2. таблиці 1-6)

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

.Озима пшениця - 182389.96 грн.

Таблиця 3.1 Витрат на виробництво 100 га озимої пшениці.

Найменування технологічних операцій		Основний обробіток грунту	Посів	Осінній догляд за посівами	Весняний догляд за посівами	Збирання врожаю	Всього разом
Витрати палива	всього, л	2467	650	170	756	1300
	торба, грн.	14803	3900	1020	4706	7800	32229
Заробітна плата персоналу	кіл -ть, чол	12	2	3	17	8
	Оплата з нарахув. вього, грн.	1149	341	1485	2615	25097	30687
Насіння	Ціна за один	0	1550	0	0	0
	Ціна всього	0	34100	0	0	0	34100
Мінеральні добрива	Ціна за один	2540	0	0	1400	0
	Ціна всього	36576	0	0	32600	0	69176
Пестициди	Ціна за один	837	0	454	181	0
	Ціна всього	3683	0	2294	14758	0	20734
Всього, грн.		52530	38341	4799	53823	32897	182390

Ціна 1 т. озимої пшениці = 1600 грн.

Собівартість 1 т.  = 456 грн.

Врожайність га/т  = 4

Днів посіву  = 15

Продуктивність сівалки га  = 39

Днів збирання = 9

Продуктивність комбайна га  = 22.9

. Озимий ячмінь - 144208.87 грн.

Таблиця 3.2 Витрат на виробництво 100 га озимого ячменю.

Найменування технологічних операцій		Основний обробіток грунту	Посів	Осінній догляд за посівами	Весняний догляд за посівами	Збирання врожаю	Всього разом
Витрати палива	всього, л	2646,00	650	0	332	1010
	торба, грн.	15 830,40	3900	0	2467,2	6363	28560,60
Заробітна плата персоналу	кіл -ть, чол	13	2	1	12	8
	Оплата з нарахув.вього, грн.	1 094,70	289,85	214,17	3206,98	25096,88	29902,57
Насіння	Ціна за один	0	1100	0	0	0
	Ціна всього	0	22000	0	0	22000,00
Мінеральні добрива	Ціна за один	2500	0	0	1340	0
	Ціна всього	25000	0	0	13400	0	38400,00
Пестициди	Ціна за один	371	0	8,4	192	0
	Ціна всього	2040,50	0	25,2	23280	0	25345,70
Всього, грн.		43 965,60	26 189	239,37	42 354,18	31 459,88	144 208

Ціна 1 т. озимого ячменю = 1400 грн.

Собівартість 1 т.  = 360.5 грн.

Врожайність га/т  = 4

Днів посіву  = 10

Продуктивність сівалки га  = 39

Днів збирання = 9

Продуктивність комбайна га  = 22.9

. Кукурудза - 241109.04 грн.

Таблиця 3.3 Витрат на виробництво 100 га кукурудзи.

Найменування технологічних операцій		Основний обробіток грунту	Передпосівний комплекс робіт	Посів	Весняний догляд за посівами	Збирання врожаю	Всього разом
Витрати палив	всього, л	1300	600	860	372	2050
	торба, грн.	8190	4797,45	5418	2343,6	12915	33664,05
Заробітна пата соналу	кіл -ть, чол	2	5	2	7	8
	Оплата з нарахув.вього грн.	372,57	260,80	349,97	1816,02	24910,20	27709,57
Насіння	Ціна за один	0	0	617	0	0
	Ціна всього	0	0	61700	0	0	61700,00
Мінеральні добрива	Ціна за один	0	5200	0	0	0
	Ціна всього	0	78000,00	0	0	0	78000,00
Пестициди	Ціна за один	0	0	0	1434	0
	Ціна всього	0	0	0	39762	0	39762,00
Всього, грн.		8 562,57	83 331,67	67 467	43 921,62	37 825,20	241 109

Ціна 1 т. кукурудзи = 1800 грн.

Собівартість 1 т. = 482 грн.

Врожайність га/т  = 5

Днів посіву  = 10

Продуктивність сівалки га  = 32.3

Днів збирання = 20

Продуктивність комбайна га = 12

4. Озиме жито - 245634.39 грн.

Таблиця 3.4 Витрат на виробництво 100 га озимого жита.

Ціна 1 т. озимого жита = 1300 грн.

Собівартість 1 т.  = 614 грн.

Врожайність га/т = 4

Днів посіву  = 15

Продуктивність сівалки га  = 35

Днів збирання = 10

Продуктивність комбайна га  = 16

. Соняшник - 148742.54 грн.

Таблиця 3.5 Витрат на виробництво 100 га соняшнику.

Ціна 1 т. соняшнику = 3500 грн.

Собівартість 1 т.  = 743 грн.

Врожайність га/т  = 2

Днів посіву  = 15

Продуктивність сівалки га  = 22

Днів збирання =10

Продуктивність комбайна га  = 30

6. Ярий ячмінь - 186378 грн.

Таблиця 3.6 Витрат на виробництво 100 га ярового ячменю.

Ціна 1 т. ярового ячменю = 1400 грн.

Собівартість 1 т.  = 934 грн.

Врожайність га/т  = 2

Днів посіву  = 12

Продуктивність сівалки га  = 37.6

Днів збирання =6

Продуктивність комбайна га  = 15.8

Передбачається, що витрати ресурсів ростуть прямо пропорціонально обсягу виробництва. Нехай  - планований обсяг виробництва j -ої продукції,  - кількість гектар засіяних j -ою продукцією. Тоді допустимим є тільки такий набір вироблюваної продукції x=(x1, x2,., xn), при якому сума площ засіяних j -ою продукцією не перевершують її запасу:

 (1)

Крім того, маємо наступне обмеження по техніці:

;(2)

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

; (3)

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

; (4)

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

Обмеження за технологією:

; (5)

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

Вартість набору продукції x виражається величиною:

 (6)

Задача планування виробництва ставиться таким чином:

Знайти оптимальний розмір посівних площ, що задовольняє обмеженням (1), (2), (3), (4), (5), при якому величина (6) набуває найбільшого значення, тобто дає максимальний прибуток.

3.2 Математичний опис поставленої задачі планування симплекс методом

Цільова функція - максимум торгівельного прибутку

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

на посівні площі

,

по техніці на посів

,

по техніці на збирання

,

; ,

за технологією виробництва

Треба спланувати такий набір вироблюваної продукції x=(x1, x2, x4, x5, x6), при якому повинні виконаються наступні нерівності, тобто

;

585;

390;

323;

525;

330;

451;

825;

960;

640;

1200;

380;

300;

і при цьому повинні виконуватися наступні обмеження: x1, x2, x3, x4, x5, x6  0. Спланований набір вироблюваної продукції x=(x1, x2, x3, x4, x5, x6) повинен забезпечити максимум вартості цього набору

{1141x1+1040x2+1318x3+684x4+2757x5+466x6}

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

(x)=1141x1+1040x2+1318x3+684x4+2757x5+466x6

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

;

585;

390;

323;

525;

330;

451;

825;

960;

640;

1200;

380;

300;, x2, x3, x4, x5, x6  0.

3.3 Рішення поставленої задачі планування виробництва

Опис методу рішення задачі.

Процедура рішення ЗЛП починається з приведення її до канонічної форми, тобто до стандартної форми завдання, орієнтованої на розроблений саме для цієї форми метод рішення. Завдання лінійного програмування в канонічній формі має сенс за умови n>m. В цьому випадку повністю описується область допустимих рішень (ОДР) ЗЛП, що геометрично є опуклим многогранником в просторі Евкліда Rn[1]. Опукла фігура, як відомо, характеризується тією властивістю, що, якщо дві точки X1 і X2 належать цій фігурі, то і увесь відрізок X1X2 належить їй. Крім того, доведено, що оптимальне рішення ЗЛП завжди лежить на межі ОДР. Тому справедливий висновок про те, що, принаймні, одна з кутових (опорных) точок опуклого многогранника ОДР є точкою оптимуму. Для того, щоб визначити координати опорної точки, усю безліч змінних X={xj}, j= необхідно розділити на дві підмножини

:

підмножина базисних змінних

,

при цьому число m базисних змінних дорівнює числу рівнянь (обмежується) за умови, що рівняння є не-залежними; підмножина  інших n - m вільних (внебазисных) змінних {xj}, j_Би[1].

Кількість можливих варіантів розподілу змінних на базисних і вільних (число базисів) дорівнює .

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

У основі симплекс-методу лежить підхід, що включає:

вибір опорної точки, що належить ОДР (вибір початкового допустимого базису);

перевірку опорної точки на оптимальність;

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

Приведення початкового завдання до канонічного виду.

Маємо початкову ЗЛП:

(x)=1141x1+1040x2+1318x3+684x4+2757x5+466x6

;

585;

390;

323;

525;

330;

451;

825;

960;

640;

1200;

380;

300;, x2, x3, x4, x5, x6  0

Приведемо ЗЛП до канонічної форми. Приведення системи обмежень, заданих у формі нерівностей, до канонічної форми рівності здійснюється за допомогою відповідного збільшення розмірності вектора X=(x1, x2, x3, x4, x5, x6) з урахуванням обов'язкової позитивності усіх його складових.

Таким чином, ЗЛП в канонічній формі має вигляд:

max{1141x1+1040x2+1318x3+684x4+2757x5+466x6};

 (7

Пошук допустимого базису.

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

ЗЛП в канонічній формі можна записати в матричному виді:

(8)

b=(1500, 585, 390, 323, 525, 330, 451, 825, 960, 640, 1200, 380, 300) T=(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T=(1144,1040,1318,686,2757,466,0,0,0,0,0,0,0,0,0,0,0,0,0)

Пошук допустимого базису починається з аналізу стовпців матриці A=(A1, A2,., A19), використовуваної в записі обмеження (8) канонічної форми ЗЛП. Як базисні слід вибирати такі 13 змінних, яким відповідає набір стовпців, що дозволяють скласти одиничну матрицю P=(Aj1, Aj2, Aj3, Aj4, Aj5, Aj6, Aj7, Aj8, Aj9, Aj10, Aj11, Aj12, Aj13).

Якщо ОДР початкової ЗЛП задана у формі нерівностей типу  (як в нашому випадку), то початковий базис може бути сформований з додаткових змінних x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, обмежень, що вводяться в систему, з метою приведення її до канонічної форми рівності. В цьому випадку матриця P буде одиничною. Таким чином, виберемо як початковий базис XБО=(x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T, оскільки стовпці A7, A8, A9, A10, A11, A12, A13, A14, A15, A16, A17, A18, A19 матриці A утворюють одиничну матрицю. Тепер перейдемо до заповнення симплекс-таблиці. Нехай ЗЛП сформульована в канонічній формі (7). Ми вибрали базисні змінні x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19. Дозволимо систему нерівностей в (7) відносно базисних змінних. Система обмежень у формі Такера набере вигляду:

x7=1500 -();=585 -();=390 -();=323 -();=525 -();=330 -();=451 -();=825 -(); (9)=960 -();=640 -();=1200 -();=380 -();=300 -();

Цільову функцію можна представити у виді:

f(x)=f0 -(- 1141x1-1040x2-1318x3-684x4-2757x5-466x6), де f0=0.

Симплекс-таблиця виглядає таким чином:

Таблиця 3.3.1. Початкова симплекс таблиця поставленого завдання

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

Кожна симплекс-таблиця аналізується по критеріях допустимості і оптимальності базису.

3.3.1 Перевірка ознаки допустимості і оптимальності базису

Ознака допустимості базису :

у опорній точці відповідно до (9) xj=bi, i=7,., 19; j=7,., 19, тому ознака допустимості базису формулюється як умова bi0, i=7,., 19.

Ознака оптимальності базису:

Якщо для  те знайдене рішення оптимальне і єдино.

Якщо для  те знайдене рішення оптимальне, але не єдино.

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

Перейдемо до конкретного випадку. У нашому випадку виконується умова допустимості базису, оскільки b=(1500, 585, 390, 323, 525, 330, 451, 825, 960, 640, 1200, 380, 300) T<0 і bi<0 (i=7,., 19).

Вибраний нами початковий базис XБО=(x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T не є оптимальним, оскільки c1=-1144<0, c2=-1040<0, c3=-1318<0, c4=-686<0, c6=2757<0, c7=466<0. Таким чином, необхідно здійснити перехід до нової опорної точки (новому базису).

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

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

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

Знайдемо

cr=.

У нашому випадку min{c1, c2, c3, c4, c5, c6}=c1=-1144 і xr=x1.

Стовпець, який відповідає змінній xr=x1 в симплекс-таблице, називатимемо таким, що дозволяє.

Вибір змінної xs. Вибір змінної xs проводиться за результатами аналізу коефіцієнтів air i=1,2,3,4,5,6 дозволяючого стовпця.

Якщо , це означає, що ОДР така, що необмежене збільшення вільної змінної xr приводить до необмеженого зростання цільової функції (ОДР не замкнута). Якщо , то відповідні базисні змінні xi (i=6,7,8,9,10,11,12,13,14,15,16,17,18,19) отримують негативні прирости при збільшенні xr=x1. Серед цих змінних xi необхідно відшукати xs, що досягає нуля при мінімальному значенні приросту xr. Треба знайти

Вибір дозволяючого елементу завершує формування нового базису XБ1, що відрізняється від колишнього базису однієї змінної xr=x1, тобто замість змінної x8 в базис XБ1 буде включена змінна x1 : XБ1=(x6, x7, x1, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T.

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

3.3.3 Перерахунок симплекс-таблиці

Правила перерахунку :

Дозволяючий елемент замінюється на 1.

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

Усі елементи отриманої таблиці необхідно розділити на дозволяючий елемент asr :

Таблиця 3.3.6.1. Ітерація №1

Б1=(с) T.

Базис XБ1=(x7, x1, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) T є допустимим, але не оптимальним. Дозволяючий елемент таблиці a103=0,2 визначає необхідність переходу до базису XБ2=(x7, x1, x9, x3, x11, x12, x13, x14, x15, x16, x17, x18, x19) T. Приведемо результат перерахунку симплекс-таблиці для базису XБ2.

Таблиця 3.3.6.2 Ітерація №2

Базис XБ2=(x7, x1, x9, x3, x11, x12, x13, x14, x15, x16, x17, x18, x19) T є допустимим, але не оптимальним. Дозволяючий елемент таблиці a195=0,5 визначає необхідність переходу до базису XБ3=( x7, x1, x9, x3, x11, x12, x13, x14, x15, x16, x17, x18, x5) T. Приведемо результат перерахунку симплекс-таблиці для базису XБ3.

Таблиця 3.3.6.3 Ітерація №3

Базис XБ3=(x7, x1, x9, x3, x11, x12, x13, x14, x15, x16, x17, x18, x5) T є допустимим, але не оптимальним. Дозволяючий елемент таблиці a142=0,25 визначає необхідність переходу до базису XБ4=(x7, x1, x9, x3, x11, x12, x2, x14, x15, x16, x17, x18, x5) T. Приведемо результат перерахунку симплекс-таблиці для базису XБ4.

Таблиця 3.3.6.4 Ітерація №4

Базис XБ3=(x7, x1, x9, x3, x11, x12, x2, x14, x15, x16, x17, x18, x5) T є допустимим, але не оптимальним. Дозволяючий елемент таблиці a74=0,25 визначає необхідність переходу до базису XБ4=(x4, x1, x9, x3, x11, x12, x2, x14, x15, x16, x17, x18, x5) T. Приведемо результат перерахунку симплекс-таблиці для базису XБ4.

Таблиця 3.3.6.5 Інтерация №5

Аналіз таблиці 6 дозволяє зробити висновок про допустимість і оптимальність базису XБ4=(x4, x1, x9, x3, x11, x12, x2, x14, x15, x16, x17, x18, x5) T.

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

4.1 Опис

В процесі виконання дипломної роботи був реалізований і відлагоджений програмний інтерфейс під ОС Windows XP (також протестований під Windows Vista), вирішальний завдання ЛП симплекс-методом (зокрема поставлене завдання планування виробництва).

Програма здійснює: рішення завдань ЛП симплекс методом; збереження і завантаження початкових даних у файл/з файлу; виведення рішення по кроках; експорт рішення в документ MS Excel; системний код програми написаний в середовищі об'єктно-орієнтованого програмування С++.

4.2 Графічне представлення програми

Головне вікно програми "Початкові дані":

Мал. 5 Головне вікно програми Simplex : 1 - Число змінних, в нашому випадку кількість вироблюваної продукції. 2 - Число обмежень. 3 - Цільова функція, в нашому випадку максимізація. 4 - Кнопки для вирішення завдання . 5 - експорт таблиць в Excel. 6 - Система обмежень у формі Такера.

 

4.3 Робота з програмою

Приступаємо до введення початкових даних: 1 - поля для введення обмежень ; 2 - поля для введення набору вироблюваної продукції. 3 - поля для введення коефіцієнтів цільової функції (у нашому випадку це прибуток від одиниці продукції ); 4 - натискаємо кнопку "Вирішити". (див. Мал. 6)

Заповнивши усі поля, приступаємо до рішення задачі:

Мал. 6 Робота з програмою

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

У 5 і 6 - можна побачити дозволяючий елемент кожної таблиці, 5 - початкові дані, 6 - кількість ітерацій, 7 - оптимальний набір вироблюваної продукції, 8 - Відповідь, в нашому випадку максимум цільової функції (максимальний прибуток) (див. Мал. 7).

Мал. 7 Робота з програмою

4.4 Схема програми

Логічна структура програми вирішального завдання ЛП симплекс методом приведена на Мал. 8, Мал. 9, Мал. 10.

Мал. 8 Симплекс-метод

Мал. 9 Пошук r -стовпчика

Мал. 10 Пошук s -строки

4.5 Результат рішення задачі планування виробництва

В результаті рішення поставленої задачі симплекс-методом отримали набір вироблюваної продукції x(2340, 960, 1615, 208, 600, 0), який задовольняє усім накладеним обмеженням і забезпечує максимальну вартість цього набору (максимум цільової функції f(x) = 1141x1+1040x2+1318x3+684x4+2757x5+ 466x6 = 7600818 грн.). Таким чином, можна оптимально спланувати обсяг виробництва продукції :

Озимої пшениці треба випустити 2340 тонн

Озимого ячменю - 960 тонн

Кукурудзи - 1615 тонн

Озимого жита - 208 тонн

Соняшнику - 600 тонн

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

По посівних площедям:

Озимої пшениці треба засіяти 585 га.

Озимого ячменю - 240 га.

Кукурудзи - 323 га.

Озимого жита - 52 га.

Соняшнику - 300 га.

Ярового ячменю - 0 га.

Підприємством ТОВ "ОльвіяЛатІнвест " в 2010 році було засіяно:

Озимої пшениці - 400 га.

Озимого ячменю - 400 га.

Кукурудзи - 250 га.

Озимому житу - 0 га.

Соняшнику - 350 га.

Ярового ячменю - 100 га.

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

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

Висновки

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

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

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

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

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

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

Виконана чисельна реалізація на прикладі сільськогосподарського підприємства ТОВ "ОльвіяЛатІнвест". Отриманий оптимальний план виробництва для цього підприємства. Оптимізація виробництва показала що підприємство може заробляти на 435818 грн. більше, при цьому раціонально використовувати земельні ресурси.

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

1. Абрамов Л.М., Капустин В.Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. - 184 с.

. Акулич И.Л., "Математическое программирование в примерах и задачах", Москва "Высшая школа" 1993г.

. Ашманов С.А. Линейное программирование, Учебное пособие. - М.:Наука, 1981.- 311 с.

. Баканов М.И., Шеремет А.Д. Теория экономического анализа: Учебник. -4-е изд., доп. и перераб. - М.: Финансы и статистика, 2000. - 416 с.

. Банди Б. Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. -176 с.

. Вентцель Е.С. Исследование операций: задачи, принципы, методологии. М.: Изд-во "Наука", 1980.

. Давыдов Э.Т. Исследование операций.- М.:Высш.шк., 1990. - 130с.

. Джерод Холлингворс, Дэн Баттерфилд, Боб Свот C++ Builder 5. Руководство разработчика = C++ Builder 5 Developer's Guide. - М.: "Диалектика", 2001. - С. 884. - ISBN 0-672-31972-1

. Джаррод Холингворт, Боб Сворт, Марк Кэшмэн, Поль Густавсон Borland C++ Builder 6. Руководство разработчика = Borland C++ Builder 6 Developer's Guide. - М.: "Вильямс", 2004. - С. 976. - ISBN 0-672-32480-

. Габасов Р., Кириллова Ф.М. Методы оптимизации. --- Минск: Издательство БГУ им. В.И. Ленина, 1981. - 352 с.

. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч.2. Транспортные задачи, Минск, Изд-во БГУ им. В.И. Ленина, 1977. - 240 с.

. Гасс С.Линейное программирование. - М.: Физматгиз, 1961. - 214с.

. Гермейер Ю.Б. Введение в теорию исследования операций. - М.: Наука, 1971. - 403с.

. Гольштейн Е.Г., Юдин Д.Б. Линейное программирование, теория, методы и приложения. - М.: Наука, 1969. - 236с.

. Ершов А.Т., Карандаев И.С., Шананин Н.А. Планирование производства и линейное программирование. МИУ, М., 1981.

. Зайченко Ю.П. Исследование операций.- Киев: Вища школа, 1975. - 278с.

. Интрилигатор М. Математические методы оптимизации и экономическая теория.- М.:Прогресс, 1975. - 396с.

. Карманов В.Г. Математическое программирование. --- Москва: Наука, Главная редакция физико-математической литературы, 1986. - 215с.

. Леоненков А.В. Решение задач оптимизации в среде MS Excel BHV-Санкт-Петербург ISBN: 5941575033 2005 г.

. Ляшенко И.Н. Линейное и нелинейное программирование. - Киев: Вища школа, 1975. - 372 с.

. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.- 488 с.

. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, Главная редакция физико-математической литературы, 1986. - 328с.

. Схрейвер А. Теория линейного программирования: в 2-х т. Т.2: Пер с англ. - М.: Мир, 1991. - 342с., ил. Раздел линейное программирование

. Тынкевич М.А. Экономико-математические методы (исследование операций). Изд. 2, испр. и доп. - Кемерово, 2000. - 177 с.

. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: "Вильямс", 2006. - С. 1296. - ISBN 0-07-013151-1

. Юдин Д.Б., Гольштейн Е.Г. Линейное программирование (Теория, методы и приложения). -- М.: Наука, Главная редакция физико-математической литературы, 1969. -424 с.

. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. - 7-е изд. - М.: "Вильямс", 2007. - С. 95-141. - ISBN 0-13-032374-8

Додаток

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

// // Цей файл визначає клас симплекс методу

##include <vcl.h>

##include <list>

##include "CD.cpp"

##ifndef CSM2_H

##define CSM2_HSM

{

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

{:( int n, int m );SetBaz( int * baz );SetT( CD ** T );Show();GetWord();GetTacker();Get_Rap();operator<<=( CSM * csm );get_CF();** get_ogr(){ return T; }* get_baz(){ return baz; }get_rez(){ return rez; }get_nm( int* nIn, int* mIn ){ *nIn = n; *mIn = m; }get_ij( int* i, int* j ){ *i = a_i; *j = a_j; }

~CSM( );:int iter; // Число ітераційoptim(); // перевірка рішення (0 - оптимальне, 1 - не існує, 2 - не оптимальне)n; // Число зміннихm; // Число обмеженьa_i;a_j; // Координати дозволяючого елементу* baz; // Масив базисних змінних** T; // Симплекс таблицяrez;

};CSM::iter = 0; // Число ітерацій::CSM( int nIn, int mIn )

{= nIn;= mIn;= new int [m];= new CD * [m + 1]; // m + 1 оскільки ще рядок цільової функції( int i = 0; i < m + 1; i++ )[i] = new CD [n + 1]; // n + 1 оскільки ще вільний член+= 1;= 2;

}::~CSM( )

{baz;( int i = 0; i < m + 1; i++ )T[i];T;-= 1;

}CSM::SetBaz( int * bazIn )

{( int i = 0; i < m; i++ )[i] = bazIn[i];

}CSM::SetT( CD ** TIn ) // Копіювання таблиці, що входить, і перевірка рішення з пошуком дозволяючого елементу

{( int i = 0; i < m + 1; i++ )( int j = 0; j < n + 1; j++ )[i][j] = TIn[i][j];optim();

}CSM::optim()

{_i = a_j = 0; // Ініціалізація координат дозволяючого елементу

// // Перевірка на отрицательность серед вільних членів( int i = 1; i < m; i++ ) // перевірка вільного члена( T[i][0].get_d() < T[a_i][0].get_d() ) // Шукаємо мінімальний_i = i;( T[a_i][0].get_d() < 0 ) // Якщо мінімальний елемент негативний (подвійний СМ)

{( int j = 1; j < n + 1; j++ ) // перевірка на наявність негативних эл-тов в рядку( T[a_i][j].get_d() < 0 ) // є негативні елементи

{_j = j; // Перший негативний елемент; // Вихід з циклу пошуку

}( a_j == 0 ) return rez = 1; // Немає оптимального рішення // вихід( int j = a_j + 1; j < n + 1; j++ ) // Прохідний по рядку ще раз для знаходження мінімального відношення( T[a_i][j].get_d() < 0 ) // Негативний( fabs( (T[m][j]/T[a_i][j]).get_d() )< fabs( (T[m][a_j]/T[a_i][a_j]).get_d() )) // Найменше відношення_j = j;rez = 2; // продовження виконань ітерацій // вихід

}

// // Перевірка на отрицательность серед елементів цільової функції_j = 1;_i = m;( int j = 2; j < n + 1; j++ ) // Прохідний по рядку цільової функції( T[m][j].get_d() < T[m][a_j].get_d() ) // Шукаємо мінімальний_j = j;( T[m][a_j].get_d() < 0 ) // Є негативний елемент в цільовій функції

{( int i = 0; i < m; i++ ) // Прохідний по стовпцю( T[i][a_j].get_d() > 0 )

{_i = i; // Перший позитивний елемент; // Вихід з циклу пошуку

}( a_i == m ) return rez = 1; // Немає оптимального рішення // вихід( int i = a_i + 1; i < m; i++ ) // Прохідний по стовпцю ще раз для знаходження мінімального відношення( T[i][a_j].get_d() > 0 ) // Позитивний( fabs( (T[i][0]/T[i][a_j]).get_d() )< fabs( (T[a_i][0]/T[a_i][a_j]).get_d() )) // Найменше відношення_i = i;rez = 2; // продовження виконань ітерацій // вихід

}rez = 0; // оптимальне рішення // вихід

}CSM::operator<<=( CSM * csmIn ) // Тут з попередньої таблиці виходить нова

{_i = csmIn ->a_i;_j = csmIn ->a_j;

// // Ділимо на дозволяючий елемент дозволяючий рядок і міняємо базисну змінну( int j = 0; j < n + 1; j++ )[a_i][j] = csmIn ->T[a_i][j] / csmIn ->T[a_i][a_j];

// // Домножаем дозволяючий рядок на эл-т в дозволяючому стовпці, соотв-щий цьому рядку, і складаємо з цим рядком( int i = 0; i < m + 1; i++)

{( i == a_i) continue;( int j = 0; j < n + 1; j++ )[i][j] = csmIn ->T[i][j] - T[a_i][j] * csmIn ->T[i][a_j];

}

// // Вводимо нову змінну в базис( int i = 0; i < m; i++ )[i] = csmIn ->baz[i];[a_i] = a_j;optim();

}CSM::get_CF()

{T[m][0];

}CSM::Show( )

{tab;= "БП\tСЧ";( int j = 0; j < n; j++)// шапка= tab + "\tX" + AnsiString( j + 1 );( int i = 0; i < m + 1; i++ )

{( i == m ) tab = tab + "\nY";tab = tab + "\n" + baz[i];( int j = 0; j < n + 1; j++)= tab + "\t" + T[i][j].get_a();

}

// // ShowMessage(tab);

}CSM::GetWord()

{

// // Таблицяtab;= "\n<table border=3 cellpadding=5 ><tr bgcolor=\"#aaaaaa\">";+= "<td align=\"center\">БП</td><td>СЧ</td>";( int j = 0; j < n; j++)// шапка

{+= "<td align=\"center\">";= tab + "X_{" + (j+1) + "}";+= "</td>";

}+= "</tr>";( int i = 0; i < m + 1; i++ )

{+= "<tr>";+= "<td bgcolor=\"#aaaaaa\" align=\"center\">";( i == m ) tab += "F'";tab = tab + "X_{" + baz[i] + "}";+= "</td>";( int j = 0; j < n + 1; j++)

{( i == a_i && j == a_j && rez == 2 ) tab += "<td bgcolor=\"#cccccc\">";tab += "<td align=\"center\">";+= T[i][j].get_a();+= "</td>";

}+= "</tr>";

}+= "</table>";tab;

/*tab;= "БП;СЧ;";( int j = 0; j < n; j++)// шапка( j == n - 1 ) tab = tab + "X" + AnsiString( j + 1 );tab = tab + "X" + AnsiString( j + 1 ) + ";";( int i = 0; i < m + 1; i++ )

{( i == m ) tab = tab + "\nF';";tab = tab + "\nX" + baz[i] + ";";( int j = 0; j < n + 1; j++)( j == n ) tab = tab + T[i][j].get_a();tab = tab + T[i][j].get_a() + ";";

}tab;

*/

}CSM::GetTacker()

{tab;( int i = 0; i < m; i++ )

{+= AnsiString("X") + baz[i] + " = ";+= T[i][0].get_a() + " - ( " + T[i][1].get_a() + "*X1";( int j = 2; j < n + 1; j++)

{is_b = false;( int d = 0; d < m; d++ )( j == baz[d] )

{_b = true;;

}( !is_b )+= T[i][j].get_s() + "*X" + AnsiString( j );

}+= " )\n";

}+= "\nЦелевая функція :";+= "\nF' = " + T[m][0].get_a() + " - ( " + T[m][1].get_a() + "*X1";( int j = 2; j < n + 1; j++)

{is_b = false;( int d = 0; d < m; d++ )( j == baz[d] )

{_b = true;;

}( !is_b )+= T[m][j].get_s() + "*X" + AnsiString( j );

}+= " )\n";tab;

}CSM::Get_Rap()

{Rap;( rez == 0 )

{( T[m][0] == 0 )= "Рішення оптимальне. Штучний базис отриманий. Далі підставляємо нові бвазисные пременные в цільову функцію".;Rap = "Рішення оптимальне, але цільова функція не дорівнює 0. штучного базису немає".;

}if( rez == 1 )

{( a_j == 0 ) Rap = AnsiString( "Рішення не існує. Цільова функція необмежена, оскільки вільний член при X" ) + baz[a_i] + " негативний, а інші елементи рядки не негативні".;if( a_i == m ) Rap = AnsiString( "Рішення не існує. Цільова функція необмежена, оскільки елемент в рядку цільової функції при X" ) + a_j + " негативний, а інші елементи стовпця не позитивні".;

}if( rez == 2 )

{= AnsiString( "Рішення триває. З базису виводиться X") + baz[a_i] + " і вводиться X" + a_j + "".;

}Rap;

}

}

##endif // CSM_H

// // Цей файл визначає клас дробу

##include <vcl.h>

##include <math.h>

##ifndef CD_H

##define CD_H

##define PR_COUNT 5000mas[PR_COUNT] = {0};Generate_Prost();CD // Клас дріб

{:::CD( int = 0, int = 1 );Set( int hi, int lo );Set( double d );Set( AnsiString d );SetInv( AnsiString d );hi(){ return m_hi; }; // чисельникlo(){ return m_lo; }; // знаменникget_d(); // повертає десяткове значенняget_a(); // повертає рядок звичайного дробуget_s(); // повертає рядок звичайного дробуget_dr();get_cel();get_abs();operator*(CD d);operator*(int num);operator/(CD d);operator/(int num);operator+(CD d);operator+(int num);operator -(CD d);operator -(int num);operator=(CD d);operator=(int num);operator==(CD d);operator==(int num);operator!=(CD d);operator!=(int num);:m_hi; // чисельникm_lo; // знаменникm_d;overflow;optim();bool gen;

};CD::gen = false;::CD( int hi, int lo )

{( !gen )

{_Prost();= true;

}= false;( hi, lo );

}CD::Set( int hi, int lo )

{= false;( lo == 0 )

{_hi = 0;_lo = 1;false;

}_hi = hi;( m_hi == 0 ) m_lo = 1;

{_lo = lo;();

}true;

}CD::Set( double d )

{= true;_d = d;true;

}CD::Set( AnsiString d )

{pos = 0;( pos = d.LastDelimiter("/"))

{_hi = StrToIntDef( d.SubString( 1, pos - 1 ), 0 );_lo = StrToIntDef( d.SubString( pos + 1, d.Length() ), 1 );( m_hi, m_lo );

}if( pos = d.LastDelimiter(".))

{( StrToFloat( d ));

}

{_hi = StrToIntDef( d, 0 );( m_hi, 1 );

}();

// // ShowMessage( "m_hi = " + AnsiString(m_hi) + "\nm_lo = " + m_lo );true;

}CD::SetInv( AnsiString d )

{pos = 0;( pos = d.LastDelimiter("/"))

{_hi = - StrToIntDef( d.SubString( 1, pos - 1 ), 0 );_lo = StrToIntDef( d.SubString( pos + 1, d.Length() ), 1 );( m_hi, m_lo );

}if( pos = d.LastDelimiter(".))

{( - StrToFloat( d ));

}

{_hi = - StrToIntDef( d, 0 );( m_hi, 1 );

}

// // ShowMessage( "m_hi = " + AnsiString(m_hi) + "\nm_lo = " + m_lo );true;

}CD::get_d() // повертає десяткове значення

{( overflow ) return m_d;( m_hi ) return float(m_hi)/m_lo;return 0;

}CD::get_a()

{( overflow ) return FloatToStrF( m_d, ffGeneral, 7, 0 );( m_lo == 1 ) return AnsiString(m_hi);return AnsiString(m_hi) + "/" + AnsiString(m_lo);

}CD::get_s()

{( overflow )

{( m_d >= 0 ) return AnsiString( " + " ) + FloatToStrF( m_d, ffGeneral, 7, 0 );return AnsiString( " - " ) + FloatToStrF( - m_d, ffGeneral, 7, 0 );

}( m_lo == 1 ) return (m_hi < 0)?AnsiString(" - ") + abs(m_hi) :" + " + AnsiString(m_hi);return ((m_hi < 0)?AnsiString(" - ") + abs(m_hi) :" + " + AnsiString(m_hi)) + "/" + AnsiString(m_lo);

}CD::get_dr()

{cd;( overflow )

{.Set( m_d - floor(m_d));cd;

}_t r;= ldiv( m_hi, m_lo );( r.rem >= 0 )

{.Set( r.rem, m_lo );

}

{.Set( m_lo + r.rem, m_lo );

}cd;

}CD::get_cel()

{cd;( overflow )

{= floor( m_d );cd;

}( m_hi >= 0 )= ldiv( m_hi, m_lo ).quot;= ldiv( m_hi, m_lo ).quot - 1;cd;

}CD::get_abs()

{cd;( overflow )

{( m_d >= 0 ) cd.Set( m_d );cd.Set( - m_d );cd;

}( m_hi < 0 ) cd.Set( - m_hi, m_lo );cd.Set( m_hi, m_lo );cd;

}CD::operator+(CD d)

{cd;( overflow || d.overflow )

{.Set( get_d() + d.get_d() );cd;

}.Set( m_hi*d.m_lo + d.m_hi*m_lo, m_lo*d.m_lo );cd;

}CD::operator+(int num)

{cd;( overflow )

{.Set( get_d() + num );cd;

}.Set( m_hi + num*m_lo, m_lo );cd;

}CD::operator -(CD d)

{cd;( overflow || d.overflow )

{.Set( get_d() - d.get_d() );cd;

}.Set(m_hi*d.m_lo - d.m_hi*m_lo, m_lo*d.m_lo );cd;

}CD::operator -(int num)

{cd;( overflow )

{.Set( get_d() - num );cd;

}.Set( m_hi - num*m_lo, m_lo );cd;

}CD::operator*(CD d)

{cd;( overflow || d.overflow )

{.Set( get_d() * d.get_d() );cd;

}.Set( m_hi*d.m_hi, m_lo*d.m_lo );cd;

}CD::operator*(int num)

{cd;( overflow )

{.Set( get_d() * num );cd;

}.Set( m_hi*num, m_lo );cd;

}CD::operator/(CD d)

{cd;( overflow || d.overflow )

{.Set( get_d() / d.get_d() );cd;

}.Set( m_hi*d.m_lo, m_lo*d.m_hi );cd;

}CD::operator/(int num)

{cd;( overflow )

{.Set( get_d() / num );cd;

}.Set( m_hi, m_lo*num );cd;

}CD::operator=(CD d)

{( d.overflow)

{( d.get_d() );*this;

}( d.m_hi, d.m_lo );*this;

}CD::operator=(int num)

{( num, 1 );*this;

}CD::operator==(CD d)

{( overflow || d.overflow )

{get_d() == d.get_d();

}( m_hi == d.m_hi )( m_lo == d.m_lo )true;false;

}CD::operator==(int num)

{( overflow )

{get_d() == num;

}( m_hi == num )( m_lo == 1 )true;false;

}CD::operator!=(CD d)

{( overflow || d.overflow )

{get_d() != d.get_d();

}( m_hi == d.m_hi )( m_lo == d.m_lo )false;true;

}CD::operator!=(int num)

{( overflow )

{get_d() != num;

}( m_hi == num )( m_lo == 1 )false;true;

}CD::optim()

{( overflow ) return;_hi *= m_lo/abs(m_lo); // для знаку_lo = abs(m_lo);( m_hi ) // далі скорочення дробу

{i = 0;(1)

{( ldiv( m_hi, mas[i] ).rem == 0 && ldiv( m_lo, mas[i] ).rem == 0 )

{_hi /= mas[i];_lo /= mas[i];

}( (mas[i + 1] > abs(m_hi) && mas[i + 1] > m_lo) || i + 1 > PR_COUNT - 1 ) break;++;

}( abs(m_hi)> mas[PR_COUNT - 1] || m_lo > mas[PR_COUNT - 1] )

{= true;_d = double(m_hi)/m_lo;;

}

}

}Generate_Prost()

{is_prost;per;kol = 1;[0] = 2;i = 3;(1)

{_prost = true;( int j = 0; j < kol; j++ )( ldiv( i, mas[j] ).rem == 0 )

{_prost = false;;

}( is_prost )

{[kol] = i;++;

}( kol >= PR_COUNT ) return;++;

}

/*p;( int i = 0; i < kol; i++ )= p + mas[i] + " ";

// // ShowMessage( p );

//*/

}

##endif // CD_H