Рішення задач лінійного програмування 2

Введення
Лінійне програмування - область математичного програмування, присвячена теорії та методів розв'язання екстремальних задач, що характеризуються лінійною залежністю між змінними.
Програмування в управлінні можна представити як процес розподілу ресурсів. Існує ряд різних методів, заснованих на ідеях математичного програмування, проте, найбільш широке застосування знайшов метод лінійного програмування.
Застосування методів лінійного програмування актуально в сьогоднішній час, так як використання математичних моделей є важливим напрямком удосконалення планування та аналізу діяльності компанії. Представлення даних у вигляді математичної моделі дозволяє конкретизувати інформацію, створювати та моделювати варіанти, вибирати оптимальні рішення.
Актуальність лінійного програмування і зумовила вибір теми даної курсової роботи. Значимість обраного питання визначається також тим, що використання методу лінійного програмування являє собою важливість і цінність - оптимальний варіант вибирається з досить значної кількості альтернативних варіантів. Також всі економічні завдання, які вирішуються із застосуванням лінійного програмування, відрізняються альтернативністю рішення і певними обмежуючими умовами
Мета курсової роботи - на практичному прикладі продемонструвати використання методів лінійного програмування.
Завдання роботи обумовлені її метою:
По-перше, розкрити теоретичний зміст даної теми.
По-друге, сформулювати і знайти оптимальне рішення задач за допомогою засобів MS Excel.
1. Завдання лінійного програмування
1. За допомогою засобів Excel знайти рішення задачі лінійного програмування
L (Х) = 14х

-9х _{2-х 4} +6,4 х ₅ -> min;

0,9 х

+ 10х _{2-28х 4} +5 х ₅

245,
0,8 х

+ 1,7 х ₂ -0,2 х ₃ -0,5 х ₄ = 9,
6 х

+ 4х ₃ - 7х ₄ + 6,3 х ₅

54,
8 х

+6,2 Х ₂ -4,8 х ₄ +2,9 х ₅

17,
x

0, (j =

).
2. Меблевий комбінат випускає книжкові полиці А з натурального дерева зі склом, полиці В1 з полірованої ДСП (деревно-стружкової плити) без скла і полки В2 з полірованої ДСП зі склом. Габарити полиць А, В1 і В2 наступні: довжина 1100 (d) мм, ширина 250 (w) мм, висота 300 (h) мм / Розмір аркуша ДСП 2x3 м.

h
w
d
Габарити полиць, що випускаються меблевим комбінатом
При виготовленні полиць А виконуються наступні роботи: столярні, покриття лаком, сушка, різання скла, упаковка. Всі операції, вироблені в ході столярних робіт та упаковки, виконуються вручну. Полиці В1 і В2 поставляються у торговельну мережу в розібраному вигляді. За винятком операції пакування, всі інші операції (виробництво комплектуючих полки, різання скла) при виготовленні полиць В1 і В2, виконуються на спеціалізованих автоматах.
Трудомісткість столярних робіт з випуску однієї полиці А становить 3,2 (Тр1) ч. Продуктивність автомата, що покриває полиці А лаком - 2 (Пр1) полиць на годину, автомата, ріжучого скло - 180 (Пр2) стекол на годину. Змінний фонд часу автомата для покриття лаком - 7,4 (ФВ1) ч, автомата для різання скла - 7,1 (ФВ2) ч. Сушіння полиць, покритих лаком, відбувається протягом доби у спеціальних сушарках, що вміщають 55 (VI) полиць. На упаковку полиці А потрібно 6 (Тр2) хвилини. У виробництві полиць зайняті 27 (Р1) столярів і 7 (Р2) пакувальників.
Продуктивність автомата, що виробляє комплектуючі полиць В, і В2, дорівнює 7 (ПРЗ) полиці на годину, а його змінний фонд часу дорівнює 7,8 (ФВ3) ч, трудомісткість пакувальних робіт складає 9 (ТР3) хв для полиці В1 і 10 (ТР4 ) хв для полиці В2.
Від постачальників комбінат отримує на місяць 415 (Z1) листів полірованої ДСП, 215 (Z2) листів ДВП (деревно-волокнистої плити), а також 240 (Z3) листів скла. З кожного листа ДВП можна викроїти 6 (К1) задніх стінок полиць В1 і В2, а з кожного листа скла - 13 (К2) стекол для полиць А і В2.
Склад готової продукції може розмістити не більше 370 (V2) полиць і комплектів полиць, причому щодня в торговельну мережу вивозиться в середньому 72 (N) полиць і комплектів. На початок поточного місяця на складі залишилося 80 (Ост) полиць, проведених раніше. Собівартість полиці А дорівнює 150 (С1) руб., Полиці В без скла - 120 (С2) руб., Зі склом - 134 (Сз) руб.
Маркетингові дослідження показали, що частка продажів полиць обох видів зі склом становить не менше 43% (Д) у загальному обсязі продажів, а місткість ринку полиць виробленого типу становить близько 1100 (Vз) штук на місяць. Меблевий комбінат уклав договір на постачання замовнику 50 (З) полиць типу В2 в поточному місяці.
Складіть план виробництва полиць на поточний місяць. Відомі ціни реалізації полиць: полиця А - 192 (Ц1) руб., Полку В без скла - 154 (Ц2) руб., Полку У зі склом - 147 (Ц3) руб.

D	W	H	Тр1	Тр2	ТР3	ТР4	Р1	Р2	Пр1	Пр2	Пр3	ФВ1	ФВ2	ФВ3	Z1	Z2	Z3
1180	270	260	3,2	6	9	10	27	7	2	180	7	7,4	7,1	7,8	415	215	240

K1	K2	V1	V2	V3	N	ост	Д	З	С1	С2	С3	Ц1	Ц2	Ц3
6	13	55	370	1100	72	80	43 (A, B1)	5A, 12B2	150	120	134	192	154	147

3 варіанти розкрою ДСП, 8 год у зміні; робота в 1 зміну; 22 робочих дні на місяць.
3. На складах зберігається борошно, яку потрібно завезти в хлібопекарні. Номери складів і номери хлібопекарень дані в таблиці 1. Поточні тарифи перевезення борошна [руб. / Т], щомісячні запаси борошна [т / міс] на складах і потреби хлібопекарень в борошні [т / міс] вказані в табл. 2.
При цьому необхідно враховувати, що з-за ремонтних робіт тимчасово немає можливості перевозити борошно з деяких складів до деяких хлібопекарні. У табл. 1ето показано в графі "Заборона перевезення" у форматі № складу х № хлібопекарні. Наприклад, «2x3» позначає, що не можна перевозити борошно зі складу № 2 у хлібопекарню № 3.
Крім того, необхідно врахувати, що деякі хлібопекарні мають договори на гарантовану поставку борошна з певних складів. У табл. 1 це показано в графі "Гарантована поставка" у форматі № складу х № хлібопекарні = обсяг поставки. Наприклад, «1x4 = 40» позначає, що між складом № 1 і магазином № 4 укладено договір на обов'язкову поставку 40 т борошна.
Необхідно організувати постачання найкращим чином, враховуючи, що борошно зберігається і транспортується в мішках вагою по 50 кг .

Таблиця 1
Номер складу, хлібопекарні, заборонені або гарантовані поставки

№ Варіанта	№ Складів	№ хлібопекарень	Заборона перевезення	Гарантоване постачання, т / міс.
4	1,2, 3,4	3, 4, 5	3x3, 4x5	3x5 = 40

Таблиця 2
Запаси, потреби і тарифи перевезень

Склади	Хлібопекарні
Склади	1	2	3	4	5	Запас, т / міс.
1	400	600	800	200	200	80
2	300	100	500	600	500	70
3	500	200	100	600	300	60
4	300	700	200	400	900	55
5	200	500	800	200	400	65
Попит, т / міс.	77,86	56,78	58.88	62,44	73,92

2. Теоретична основа лінійного програмування
2.1.Постановка завдання
Постановка практичної задачі ЛП включає наступні основні етапи:
· Визначення показника ефективності, змінних задачі,
· Завдання лінійної цільової функції S (x), що підлягає мінімізації або максимізації,
· Завдання обмежень.
Наведемо зараз загальну математичну формулювання основного завдання лінійного програмування.
Дана система лінійних рівнянь з n невідомими:
a11 x1 + a11 x2 + ... ... + a11 xn

b1,
a21 x1 + a22 x2 + ... ... + a2n xn

b2,
am1 x1 + am2 x2 + ... ... + amn xn

bm,
і лінійна функція
f = c1 x1 + c2 x2 + ... ... ... + cn xn (1.2)
Потрібно знайти таке невід'ємне рішення системи
x1 ≥ 0, x2 ≥ 0, ... ..., xn ≥ 0 (1.3)
при якому функція f приймає найменше значення.
Рівняння (1.1) називають системою обмежень даного завдання; функцію f - цільовою функцією (або лінійною формою).
2.2.Методи рішення задач лінійного програмування
2.2.1. Симплекс - метод
Симплекс метод - метод лінійного програмування, який реалізує раціональний перебір базисних допустимих рішень, у вигляді кінцевого ітеративного процесу, необхідно покращувати значення цільової функції на кожному кроці.
Застосування симплекс-методу для задачі лінійного програмування передбачає попереднє приведення її формальної постановки до канонічної форми з n невід'ємними змінними: (X1, ..., Xn), де потрібно мінімізація лінійної цільової функції при m лінійних обмеженнях типу рівностей. Серед змінних завдання вибирається початковий базис з m змінних, для визначеності (X1, ..., Xm), які повинні мати невід'ємні значення, коли решта (nm) вільні змінні рівні 0. Цільова функція та обмеження рівності перетворяться до діагональної формі щодо базисних змінних, змінних, де кожна базисна змінна входить лише в одне рівняння з коефіцієнтом 1:

X ₀ + A _{0, m +1} * X _{m +1} + ... + A _{0, n} * X _n = A _0,0

X ₁ + A _{1, m +1} * X _{m +1} + ... + A _{1, n} * X _n = A _1,0

. . . . . . . . . . . . . . . .

X _i + A _{i, m +1} * X _{m +1} + ... + A _{i, n} * X _n = A _{i, 0}

. . . . . . . . . . . . . . . .

X _m + A _{m, m +1} * X _{m +1} + ... + A _{m, n} * X _n = A _{m, 0}

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

	1	X ₁	X ₂	...	X _m	X _{m +1}	...	X _n
X ₀	A _0,0	0	0	...	0	A _{0, m +1}	...	A _{0, n}
X ₁	A _1,0	1	0	...	0	A _{1, m +1}	...	A _{1, n}
X ₂	A _2,0	0	1	...	0	A _{2, m +1}	...	A _{2, n}
...	...	...	...	...	...	...	...	...
X _m	A _{m, 0}	0	0	...	1	A _{m, m +1}	...	A _{m, n}

Верхній рядок симплекс-таблиці представляє цільову функцію завдання. Кожен рядок симплекс-таблиці, крім першої, відповідає певному обмеженню-рівності завдання. Вільні члени обмежень складають крайній лівий стовпець таблиці. Зліва від таблиці записані поточні базисні змінні (X1, ..., Xm). Зверху від таблиці наведено набір всіх змінних задачі, де Xm +1, ..., Xn - вільні змінні завдання.
Перетворення таблиці треба виробляти до тих пір, поки не буде отримана симплекс-таблиця, яка одночасно є прямо і двояко допустимої.
Даний метод отримав широке розповсюдження і велику популярність у порівнянні з іншими підходами, оскільки украй рідко на практиці зустрічаються завдання важкі для симплекс-методу.
2.2.2. Геометричний метод
Застосовується дя завдань з двома змінними. Метод рішення полягає в наступному:

На площині Ох1х2 будуються прямі, які задають відповідні обмеження:
a11 x1 + a11 x2 + ... ... + a11 xn = b1,
a21 x1 + a22 x2 + ... ... + a2n xn = b2,
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
am1 x1 + am2 x2 + ... ... + amn xn = bm.
Знаходимо безліч усіх точок х1, х2, що задовольняє всім нерівностям. Така безліч називається областю допустимих рішень. Будуємо вектор

і переміщаємо лінію рівня, який задається рівнянням: с1х1 + с2х2 = const в напрямку вектора

до останньої точки перетину з ОДР. Ця точка і дає рішення задачі Lmax = значенням L в цієї точки
2 .3. Двоїста задача.
Загальна схема побудови двоїстої задачі.
Якщо задана спільне завдання ЛП:

де D визначається системою рівнянь і нерівностей:

то двоїстої по відношенню до неї називається спільне завдання ЛП:

де D * визначається системою рівнянь і нерівностей:

Як випливає з наведеної схеми при переході від прямої задачі ЛП до двоїстою:
1. Тип оптимуму змінюється на протилежний, тобто максимум на мінімум, і навпаки.
2. Вектор коефіцієнтів цільової функції c і стовпець обмежень b міняються місцями.
3. Матриця обмежень задачі А транспонується.
4. Безліч індексів змінних, на які накладено умова позитивності у прямій задачі визначають номери обмежень, що мають форму нерівностей в двоїстої задачі.
5. Безліч номерів обмежень, що мають форму нерівностей у прямій задачі визначають безліч індексів змінних, на які накладається умова позитивності, в двоїстої задачі.
З наведеного визначення випливає важлива властивість - симетричність відносини подвійності, тобто завдання, двоїста по відношенню до двоїстої, збігається з прямою (вихідної) завданням.
((D *) *, (f *) *) ≡ (D, f),
Основні теореми:
Теорема 1. Якщо одна з двоїстих завдань має кінцевий оптимум, то інша також має кінцевий оптимум, причому екстремальні значення цільових функцій збігаються
Теорема 2 (про що доповнює нежорсткої). Для того щоб план х * й у * були оптимальними рішеннями відповідно завдань лінійного програмування і двоїстої до них необхідно і достатньо, щоб виконувалися наступні співвідношення:

Теорема 3 (про оцінки). Значення змінних

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

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

з обсягами виробництва в одиницю часу (місяць, квартал), рівними відповідно

і пункти споживання

споживають за той же проміжок часу відповідно

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

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

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

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

При цьому кожен споживач отримує потрібну кількість продукту:

і кожен постачальник відвантажує весь вироблений ним продукт:

Як і у всіх подібних випадках, тут також обумовлюється невід'ємності змінних: постачання від якогось пункту виробництва того чи іншого пункту споживання може бути дорівнює нулю, але негативною, тобто слідувати у зворотному напрямку, бути не може.
Розглянемо таблицю.
Рядки транспортної таблиці відповідають пунктам виробництва (в останній клітині кожного рядка зазначено обсяг запасу продукту ai), а стовпчики - пунктами споживання (остання клітина кожного стовпця містить значення потреби bj). Всі клітки таблиці (крім тих, які розташовані в нижньому рядку і правій колонці) містять інформацію про перевезення з i-го пункту в j-й: у лівому верхньому куті знаходиться ціна перевезення одиниці продукту, а в правому нижньому - значення обсягу перевезеного вантажу для даних пунктів. Клітини, які містять нульові перевезення (xi, j = 0), називають вільними, а ненульові - зайнятими (xi, j> 0).

	В1	В2	... ...	Вn	Всього
	C _1,1	C _1,2	... ...	C _{1, n}	а1
A ₁	C _2,1	C _2,2	... ...	C _{2, n}	а2
A ₂	....	....	....	....
....	...	...	...	....	....
A _m	C _{m, 1}	C _{m, 2}	... ...	C _{m, n}	аm
	b1	b2		bn

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

3. Рішення задач
3.1. Рішення задачі лінійного програмування
3.1.1.Постановка завдання
Сформулюємо задачу: Визначити значення змінних, що забезпечують мінімізацію цільової функції.
Складемо цільову функцію і задамо обмеження.
Нехай Х1, Х2, Х3, Х4, Х5 - невідомі змінні
Цільова функція: L (Х) = 14 х

-9 Х ₂ - х ₄ +6,4 х ₅ -> min;
Обмеження: g _1: 0,9 х

+ 10 х _{2-28х 4} +5 х ₅

245,
g _2: 0,8 х

+ 1,7 х ₂ -0,2 х ₃ -0,5 х ₄ = 9,
g _3: 6 х

+ 4х ₃ - 7х ₄ + 6,3 х ₅

54,
g _4: 8 х

+6,2 Х ₂ -4,8 х ₄ +2,9 х ₅

17,

3.1.2.Ввод даних
1. Введемо на робочий лист Excel необхідні дані. У комірці В5 запишемо вираз цільової функції, а в осередках В8: В11-ліві частини обмежень.
2.Командой Сервіс, Пошук рішення откройем діалогове вікно ² Пошук рішення ² (рис. 2) і заповнимо його даними. У полі Встановити цільову клітинку введемо адресу цільової функції $ В $ 5, в полі Змінюючи клітинки - адреси $ B $ 3: $ E $ 3. Переведіть перемикач Рівної в положення мінімального значення.
Щоб ввести обмеження у вікні ² Пошук рішення ² натиснемо кнопку Додати і на екрані з'явиться діалогове вікно ² Додавання обмеження ².
3. Почнемо з першого обмеження. Встановимо курсор в полі Посилання на клітинку і, виділяючи на аркуші (рис.1) клітинку В8, введемо її адресу $ B $ 8 в це поле.
Кнопкою-стрілкою відкриємо список і виберемо в ньому знак <=. У полі Обмеження встановіть курсор і, виділяючи на аркуші клітинку D8, введемо її адресу $ D $ 8 у це поле і натиснемо кнопку Додати.
4. Повторимо дії п.3 і введемо інші обмеження $ У $ 9 = $ D $ 9, $ В $ 10 <= $ D $ 10, $ В $ 11> = $ D $ 11, що реалізують граничні умови. Після введення останнього обмеження $ F $ 11 <= $ H $ 11 замість кнопки Додати натиснемо кнопку ОК.
Таким чином, у вікно ² Пошук рішення ² (рис. 2) будуть введені обмеження.
3.1.3. Рішення завдання
1. Для завдання необхідних параметрів оптимізації натисканням кнопки Параметри відкриємо вікно ² Параметри пошуку рішення ² (рис. 4).
У цьому вікні залиште незмінними встановлені за замовчуванням Максимальний час: 100 сек, що виділяється на пошук рішення (можливо до 9 годин), Гранична кількість ітерацій: 100, Відносна похибка: 0,000001, Допустиме відхилення: 5%, перемикачі в положенні лінійна, прямі , Ньютона.
Встановимо прапорець Лінійна, щоб забезпечити застосування симплекс-методу, і натисніть кнопку ОК.
2. У вікні ² Пошук рішення ² натисніть кнопку Виконати. На екрані з'явиться діалогове вікно ² Результати пошуку рішення ² (мал. 5) з інформацією «Рішення знайдено. Всі обмеження і умови оптимізації виконані », що підтверджує успішне вирішення задачі оптимального розподілу ресурсів та кількісні результати (значення змінних, обмежень і цільової функції), наведені на рис.6.
x ₁ = А3 = 0, x ₂ = В3 = 14,43, x ₃ = С3 = 39,93, x ₄ = D3 = 15,10, x ₅ = Е3 = 0
При цьому значення цільової функції:
L = В5 = -144,99.
3.1.4. Аналіз оптимального рішення
Аналіз оптимального рішення починається після успішного виконання завдання, коли на екрані з'являється діалогове вікно ² Результати пошуку рішення ². З його допомогою можна підготувати три типи звітів: за результатами (опція Результати), по стійкості (опція Стабільність), по межах (опція Межі).
1. Підготуємо звіт за результатами (рис.7).
Звіт складається з трьох таблиць.
У першій таблиці (Цільова осередок) наводяться відомості про цільової функції: вихідне значення (у графі "Початкові») і оптимальний результат (у графі «Результат»).
У другій таблиці (Змінні клітинки) наводяться вихідні (у графі "Початкові») та отримані в результаті рішення задачі (у графі «Результат») значення змінних x _1, x _2, x _3, x _4, x _5.
Третя таблиця (Обмеження) відображає результати оптимального рішення, що стосуються обмежень і граничних умов.
2. Клацанням на ярлику Звіт по стійкості відкриємо вміст звіту на робочому аркуші (рис. 8).
Звіт по стійкості містить дві таблиці.
У першій таблиці (Змінні клітинки) наводяться наступні значення змінних:
· Результати вирішення завдання (графа «результ. Значення»);
· Нормована вартість, тобто додаткові двоїсті змінні v _j,

, Які показують, наскільки змінюється цільова функція при примусовому включенні одиниці цієї продукції в оптимальне рішення;
· Коефіцієнти цільової функції (графа «Цільовий коефіцієнт»);
· Граничні значення приросту коефіцієнтів D c _j цільової функції (останні дві графи), при яких зберігається набір змінних, що входять в оптимальне рішення.
У другій таблиці наводяться значення обмежень:
· Значення використовуваних (графа «результ. Значення») і заданих (графа «Обмеження, права частина») ресурсів;
· Тіньова ціна, тобто двоїсті оцінки z _i, які показують, як зміниться цільова функція при зміні ресурсів на одиницю;
· Значення приросту ресурсів Δ b _i (останні дві графи), при яких зберігається оптимальний набір змінних, що входять в оптимальне рішення.
3. Звіт по переділах (рис.9) показує, в яких межах може змінюватися випуск продукції, що увійшла в оптимальне рішення, при збереженні його структури:
· Наводяться значення х _i в оптимальному рішенні (графа «Значення»);
· Даються нижні і верхні межі зміни х _i і відповідні значення цільової функції (у графах «Цільовий результат»).

3.2. Рішення одноіндексной завдання лінійного програмування
3.2.1. Побудова моделі
У цьому завданню шуканими невідомими є кількість полиць кожного виду, які будуть вироблені в поточному місяці. Таким чином, Х1 - кількість полиць А (шт. / міс.); Х2 - кількість полиць В1 (шт. / міс.); Х3 - кількість полиць В2 (шт. / міс.).
Цільова функція: Прибуток визначається різницею між ціною і собівартістю, тоді:

L (х) = (192-150) х1 + (154-120) х2 + (147-134) х3 мах
Руб. / шт .* шт. / міс. = Руб. / міс.
Обмеження:
· Обмеження по фонду часу (з використанням трудомісткості робіт)
3,2 х1

27 * 8 * 1 * 22
ч / шт .* шт. / міс.

чол .* год / (чел.см.) * див / дн. * Дн. / міс.
ч / міс.

ч / міс.
3,2 год / шт. (Тр1) - це час, що витрачається на столярні роботи при виробництві однієї полиці типу А;
27 чол. (Р1) - це кількість столярів;
8ч / (осіб * см) - кількість годин роботи 1 людини протягом зміни;
1см./дн. - Кількість змін в одному робочому дні;
22 дн. / міс. - Кількість робочих днів у місяці
Необхідно провести перевірку одиниць виміру!
Аналогічно - пакувальні роботи:
6/60х1 +9 / 60х2 +10 / 60х3

7,4 * 8 * 1 * 22
ч / міс.

год / міс
7 чол. (Р2) - це кількість пакувальників
Обмеження по фонду часу на покриття лаком полиць типу А:
1 / 2 * х1

7,4 * 1 * 22
ч / шт .* шт. / міс.

ч / см .* см. / дн .* дн. / міс.
ч / міс.

ч / міс.
1 / 2 - коефіцієнт, що показує кількість годин, що припадають на покриття лаком однієї полиці типу А.
Автомат працює за зміну 7,4 год за зміну (ФВ1).
Обмеження по фонду часу на різання скла для полиць типу А і В2:
2/180х1 +2 / 180х3

7,1 * 1 * 22
ч / шт .* шт. / міс.

ч / см .* см. / дн .* дн. / міс.
ч / міс.

ч / міс.
Обмеження по фонду часу на виробництво комплектуючих полиць типу В1 і В2:
1/7х2 +1 / 7х3

7,8 * 1 * 22
ч / шт .* шт. / міс.

ч / см .* см. / дн .* дн. / міс.
ч / міс.

ч / міс.
· Обмеження по запасу витрачаються у виробництві матеріалів (за запасом використовуваних для виробництва полиць деталей) ..
Доцільно орієнтуватися не на кількість листів ДСП, а на кількість комплектів для полиць, які можна отримати з наявного запасу ДСП. Оскільки листи ДСП можна розкроює різними способами і отримувати при цьому різну кількість деталей і комплектів, то позначимо місячний запас комплектів в правій частині як Yкомпл і розглянемо спосіб його чисельного визначення пізніше.
1х2 +1 х3

Yкомпл
Компл. / шт .* шт. / міс.

Компл. / міс.
Компл. / міс.

Компл. / міс.
Аналогічно складаємо обмеження за запасом задніх стінок з ДВП для полиць В1, В2:
1х2 +1 х3

215 * 6
Задня стінка / шт .* шт. / міс.

лист ДВП / міс .* задня стінка / лист ДВП
Задня стінка / міс.

Задня стінка / міс.
Де 215 - щомісячний запас листів ДВП
6 - кількість задніх стінок полиць з кожного аркуша ДВП.
Обмеження за запасом стекол для полиць А і В2:
2х1 +2 х3

240 * 13
скло / шт .* шт. / міс.

лист скла / міс .* скло / лист скла
скло / міс.

скло / міс.
Де 240 - щомісячний запас стекол
13 - кількість стекол з кожного листа скла.
· Обмеження по ємності допоміжних приміщень і ринку.
Обмеження за кількістю полиць А, які може вмістити сушарка:
х1

55 * 22
шт. / міс.

шт. / дн .* дн. / міс.
шт. / міс.

шт. / міс.
де 55 - кількість полиць, які можуть бути просушені протягом місяця.
Обмеження на кількість полиць всіх видів, які може вмістити склад готової продукції:
х1 + х2 + х3

370-80 +72 * 22
шт. / міс.

шт. / міс.-шт. / міс. + шт. / дн .* дн. / міс.
шт. / міс.

шт. / міс.
Тут враховується, що загальна ємність складу зменшується на залишок полиць, які залишилися невивезених з минулого місяця. Крім того, протягом місяця кожен день буде звільнятися за N місць для полиць.
Обмеження за приблизною ємності ринку:
х1 + х2 + х3

1100
шт. / міс.

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

5,
х3

12
шт. / міс.

шт. / міс.
Необхідно зробити як мінімум 5 полиць А і 12 полиць В3.
· Обмеження по співвідношенню обсягів продажів різних товарів.
Процентне відношення кількість полиць А і В1 до всього обсягу продажів:
(Х1-5) + х2

0,43 [(х1-5) + х2 + (х3-12)]
0,57 х1 +0,57 х2-0, 43х3 - 2,31
Шт. / міс.

шт. / міс.
· Визначення кількості комплектів для полиць В1 і В2
3.2.2. Перший етап вирішення завдання
У залежності від розмірів листів ДСП і габаритів полиць деталі В1 і В2 можна викроїти різними способами. Розглянемо 3 можливих варіанти такого розкрою (рис. 10).

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

L (Y) = Yкомпл мах
Кількість всіх розкроєних листів ДСП не повинно перевищувати 415, тобто щомісячний запас їх на складі:
у1 + у2 + у3

415
ліст. / міс.
Кількість верхніх і нижніх стінок, одержуваних при розкрою:
19у1 +12 у2 +16 у3

2Yкомпл
дет, міс.

дет. / міс.
Обмеження, що задають нижню межу кількості бічних стінок полиць:
9у1 +36 у2 +18 у3

2Yкомпл
дет, міс.

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

L (Y) = Yкомпл мах

у1 + у2 + у3

415
19у1 +12 у2 +16 у3

2Yкомпл
9у1 +36 у2 +18 у3

2Yкомпл
у1, у2, у3, Yкомпл

0
Вирішимо цю задачу за допомогою функції Пошук рішення в MS Excel. Для цього повторимо всі пункти виконання роботи 3.1.2 - 3.1.3 (рис.11).
3.2.3. Рішення вихідної одноіндексной завдання
Вирішивши завдання для варіанту 0 ми отримав значення правої частини обмеження Y = 3515 комплектів, після чого вирішуємо вихідну завдання, модель якої має такий вигляд:

L (х) = 42х1 +34 х2 +13 х3 мах

3,2 х1

4752;
0,1 х1 +0,15 х2 +0,167 х3

1232;
0,5 х1

162,8;
0,011 х1 +0,011 х3

156,2;
0,143 х2 +0,143 х3

171,6;
х2 + х3

3515;
х2 + х3

1290;
2х1 +2 х3

3120;
х1

1210;
х1 + х2 + х3

1874;
х1 + х2 + х3

1100;
х1

5;
х3

12;
0,57 х1 +0.57 х2 +0,43 х3

-2,31;
х1, х2, х3

0
Вирішимо задачу з використанням функції Пошук рішення в MS Excel аналогічно пунктам 3.1.2-3.1.3.
У осередок Е5 введемо цільову функцію, в осередки В6: В19 - обмеження, змінні будемо змінювати в осередках В3: В5 (рис.12).
Вирішивши завдання, отримуємо:
х1 = 326шт./мес., х2 = 762 шт. / міс., х3 = 12 шт. / міс.,
L (X) = 39753 руб. / міс.,

тобто в поточному місяці необхідно провести 326 полиць А, 762 полки В1, 12 полиць В2. Після реалізації всіх вироблених полиць комбінат отримає прибуток у розмірі 39753 рублів. Оформимо звіти аналогічно п.3.1.4.
Звіт за результатами, що складається з 3 таблиць:
1. Інформація про цільової функції.
2. Інформація про значення змінних, отриманих в результаті рішення задачі.
3. Результати оптимального рішення для обмежень і для граничних умов.
Аналіз звіту показує, що ми можемо зменшити фонд часу фонд часу з виробництва полиць В на 60,86 год і це ніяк не вплине на оптимальне рішення. Таким чином, ми знизимо час роботи автомата, що виробляє комплектуючі полиці В1 і В2.
Ємність сушарки може бути знижена до 326 полиць.
На підставі проведеного аналізу можна зробити висновок про те, що існують причини, що не дозволяють меблевому комбінату випускати більшу кількість полиць і отримувати більший прибуток. Проаналізувати ці причини дозволяє звіт за стійкістю.
Звіт по стійкості
Проаналізувавши 2 таблицю, ми побачимо, що доцільно збільшити місткість ринку найбільша на 425,6 = 426 полиць. Це призведе до нових оптимальних рішень, що збільшує прибуток у порівнянні з знайденої. Подальше збільшення ємності ринку понад зазначені межі не буде більше покращувати рішення. З колонки «Тіньова ціна» видно, що кожна полку, яка буде розміщена на ринку, принесе прибуток дорівнює 34 руб ..
Звіт по межах показує знайдені результати та межі, в яких вони можуть змінюватися.
3.3. Рішення двухіндексной завдання лінійного програмування. Транспортна задача
3.3.1. Визначення змінних
Позначимо через хij [меш.] Кількість мішків з борошном, які будуть перевезені з i-го складу в j-у хлібопекарню.
3.3.2. Перевірка збалансованості завдання
Перш ніж перевіряти збалансованість завдання, треба виключити обсяг гарантованої поставки з подальшого розгляду. Для цього віднімемо 40 т з таких величин:
· Із запасу третього складу = 60-40 = 20т/мес.;
· З потреби в борошні п'ятого хлібопекарні
b2 = 73,92-40 = 33,92 т / міс.
Згідно з умовою задачі борошно зберігається і перевозиться у мішках по 50 кг , Тобто одиницями виміру змінних хij є мішки борошна. Але
запаси борошна на складах і потреби в ній магазинів задані в тоннах. Тому для перевірки балансу і подальшого вирішення завдання наведемо ці величини до однієї одиниці виміру - мішкам. Наприклад, запас борошна на
перший складі дорівнює 80 т-міс., або 80т/мес. / 0,050 т. / меш .= 1600 меш / міс, а потреба третій хлібопекарні становить 58,88 т / міс, або 58,88 т / міс / 0,050 т. / меш .= 1178меш./мес. Округлення при розрахунку потреб треба проводити в більшу сторону, інакше потреба в борошні не буде задоволена повністю.
Для даної ТЗ має місце співвідношення
склади хлібопекарні
1600 +1400 +400 +1100 <1178 +1249 +679
4500меш./мес. 3106 меш. / міс.
Щомісячний сумарний запас борошна на складах більше сумарної потреби хлібопекарень на 1394 мішків борошна, звідки випливає висновок: ТЗ не збалансована.
3.3.3. Побудова збалансованої транспортної матриці
Збалансована транспортна матриця представлена в таблиці 3. Вартість перевезення борошна повинна бути віднесена до одиниці продукції, тобто до 1 мішку борошна. Так, наприклад, тариф перевезення з першого складу в третій магазин дорівнює 800 руб. / Т • 0,050 т / меш. = 40 руб. / меш.
Для встановлення балансу необхідний додатковий фіктивний магазин. Фіктивні тарифи перевезення задамо таким чином, щоб вони були дорожчими реальних тарифів.
Неможливість доставки вантажів з третього складу в третю хлібопекарню і з четвертого складу в п'яту хлібопекарню задається у моделі за допомогою забороняє тарифу, який повинен перевищувати величину фіктивного тарифу. Таблиця 3
Транспортна матриця завдання

	Хлібопекарні				Запас, мішки
Склади	X3	Х4	Х5	Х6	Запас, мішки
З!	40	10	10	50	1600
С2	25	30	25	50	1400
С3	100	30	15	50	400
С4	10	20	100	50	1100
Попит, мішки	1178	1249	679	1394	= 4500

3.3.4. Завдання цільової функції
Формальна ЦФ, тобто сумарні витрати на всі можливі перевезення борошна, що враховуються в моделі, задається наступним виразом:
L (X) = 40 х ₁₁ +10 х ₁₂ + 10х ₁₃ +50 х ₁₄ +
+25 Х ₂₁ +30 х ₂₂ +25 х ₂₃ +50 х ₂₄ +
+ 100х ₃₁ + 30х ₃₂ +15 х ₃₃ +50 х ₃₄ +

+10 Х ₄₁ +20 х ₄₂ +100 х ₄₃ +50 х ₄₄ min (руб. / міс) ..
При цьому слід враховувати, що внаслідок використання фіктивних тарифів реальна ЦФ буде менше формальної ЦФ на вартість знайдених в процесі вирішення фіктивних перевезень.
Завдання обмежень:
х ₁₁ + х ₁₂ + х ₁₃ + х ₁₄ = 1600,

х ₂₁ + х ₂₂ + х ₂₃ + х _{24 = 1400,}
х ₃₁ + х ₃₂ + х ₃₃ + х ₃₄ = 400,
х ₄₁ + х ₄₂ + х ₄₃ + х ₄₄ = 1100,
х _{11 +} х ₂₁ + х ₃₁ + х ₄₁ = 1178,
х ₁₂ + х ₂₂ + х ₃₂ + х ₄₂ = 1249,
х ₁₃ + х ₂₃ + х ₃₃ + х ₄₃ = 679,
х ₁₄ + х ₂₄ + х ₃₄ + х ₄₄ = 1394,
хij

0 (

.
Вирішимо завдання за допомогою засобів MS Excel. Аналогічно пунктам 3.1.2-3.1.3-введемо дані, цільову функцію в комірку F3, обмеження - у комірки С8: С15 (рис.16).
Вартість фіктивних перевезень складе: 127410 руб .. Знайдемо вартість необхідних перевезень: 127410-1400 (сума фіктивних витрат) = 126 010 руб.
З рис.13 ми також бачимо якусь кількість мішків борошна з якого складу надійде на кожну хлібопекарню:
2х3 = 1178 мішка;
1х4 = 1027 мішка;
2х4 = 222 мішка;
1х5 = 573 мішка + гарантоване постачання 800 мішків;
4х5 = 106 мішків (перевезення заборонена).

Висновок
Після проведених обчислень, в першій задачі, на перебування значення змінних, що забезпечують мінімізацію цільової функції, ми отримали наступні результати:
x ₁ = А3 = 0, x ₂ = В3 = 14,43, x ₃ = С3 = 39,93, x ₄ = D3 = 15,10, x ₅ = Е3 = 0
У другому рішенні, одноіндексной завдання лінійного програмування, отримуємо підсумковий відповідь:
х1 = 326шт./мес., х2 = 762 шт. / міс., х3 = 12 шт. / міс.,
L (X) = 39753 руб. / міс.,
У транспортній задачі, номер 3, вартість необхідних перевезень становила 126010 крб.
У даній роботі ми не тільки дослідили, але і довели вигідність проведення розрахунків завдань лінійного програмування і, зокрема, електронних таблиць Excel.

Бібліографічний список
1. О.М. Карасьов, Н.Ш. Кремер, Т.М. Савельєва [текст]: «Математичні методи в економіці», 1996. - 354 с.
2. Загальний курс вищої математики для економістів [Текст]: Підручник / за ред В.І. Єрмакова .- М.: інфа - М. - 656 с. - (Серія «вищу освіту»).
3. Т.Л. Партикіна, І.І. Попов Математичні методи [Текст]: підручник. - М.: ФОРУМ: інфа-М, 2005. - 464 с.: Іл - (професійна освіта).
4. Федосєєв В.В. та ін Економіко-математичні методи і прикладні моделі: навчальний посібник для ВУЗів. - М.: Юніті, 2002.
5. Лященко І.М. Лінійне і нелінійне програмування [Текст]: І. М. Лященко, Є. А. Карагодова, Н. В. Чернікова. - К.: «Вища школа», 1992, 372 с.
6. Гольштейн Є.Г., Юдін Д.Б. Завдання лінійного програмування транспортного типу. - M.: Наука, 1989. - 382с.
7. Балашевич В.А. [Текст]: Основи математичного програмування. Мн. Обчислюємо. шк. 2002. - 173с.
8. Branch MA, TF Coleman, Y. Li. [Текст]: A Subspace, Interior, and Conjugate Gradient Method for Large-Scale Bound-Constrained Minimization Problems. SIAM Journal on Scientific Computing, Vol. 21, Number 1, pp. 1-23, 1999.