Економічні задачі лінійного програмування і методи їх вирішення (стр. 2 из 4)

Z = c1x1 + c2x2 +. . . + cnxn .

Сумарні витрати ресурсу Si (i =

складають:

.

У силу обмеженості ресурсу Si величиною bi отримаємо систему обмежень:

.

На змінні хj повинна бути накладена умова невід’ємності

тобто продукція Рj або може випускатися (xj > 0), або не випускатися (xj = 0).

Отже, математична модель буде мати вид:

,

.

1.2.2 Задача про суміші

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

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

Потрібно забрати суміш із заданими властивостями при найменших витратах на вихідні сировинні матеріали.

Для складання математичної моделі запишемо умови задачі у вигляді таблиці:

Таблиця 2.

Вид речовиниВид сировини	1	...	j	...	n	Обсяг сировини	Цінасировини
1	a11	...	a1j	...	a1n	d1	c1
…	...	...	...	...	...	…	…
i	ai1	...	aij	...	ain	di	ci
…	...	...	...	...	...	…	…
m	am1	...	amj	...	amn	dm	cm
Мінімальна кількість речовини в суміші	b1	...	bj	...	bn

Позначимо через х_i

кількість сировини і-го виду, що входить у склад суміші.

Мета завдання (цільова функція) – мінімізувати сумарні витрати на сировину:

Система обмежень включає в себе обмеження за технічними характеристиками:

а також обмеження за обсягом сировини, які з урахуванням невід’ємності будуть мати вид:

Запишемо модель у компактній формі:

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

1.2.3 Задача про розкрій

Задача оптимального розкрою матеріалів полягає у визначенні найбільш раціонального способу розкрою наявного матеріалу (колоди, сталеві смуги, шкіра і т.д.), при якому буде виготовлено найбільшу кількість готових виробів у заданому асортименті чи буде досягнуто найменшу кількість відходів. Нехай на обробку поступає a одиниць сировинного матеріалу одного виду (наприклад, a колод однієї довжини). З нього потрібно виготовити комплекти, в кожен з яких входить n видів виробів у кількості, пропорційній числах. Є m способів розкрою (обробки) даного матеріалу, тобто відомі величини визначають кількість одиниць j-х виробів при i-му способі розкрою одиниці сировинного матеріалу [10].

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

Таблиця 3.

Вид виробуСпосіброзкрою	1	...	j	...	n
1	a11	...	a1j	...	a1n
…	...	...	...	...	...
i	ai1	...	aij	...	ain
…	...	...	...	...	...
m	am1	...	amj	...	amn

Нехай

– кількість одиниць сировинного матеріалу, розкроюється i-м варіантом ( .

Тоді кількість виробів 1-го виду одно:

.

Беручи до уваги умову комплектності, маємо:

де y – кількість комплектів.

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

Очевидно, що

(на розкрій надходить a одиниць сировинного матеріалу), а також

Мета задачі – максимізувати кількість комплектів:

.

Отже, приходимо до математичної моделі задачі про розкроєння:

,

.

Щоб виразити цільову функцію через змінні x₁,…,x_m, достатньо скористуватися будь-яким із співвідношень:

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

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

Нехай є m пунктів виробництва однорідного продукту (видобуток руди в кар'єрах, виробництво автобусів, кондитерських виробів, комп'ютерів і т.д.) і n пунктів споживання цього продукту. Потужності пунктів виробництва складають аi одиниць однорідного продукту, а потреби кожного j-го пунктуспоживання рівні одиниці. Відомі витрати на перевезення одиниці продукту від i-го постачальника j-му споживачеві. Скласти такий план перевезень, при якому сумарні витрати на всі перевезення були б найменшими. Нехай попит і пропозиція збігаються, тобто

Таку транспортну задачу називають збалансованою (закритою). При цьому передбачається, що вся продукція від постачальників буде вивезена і попит кожного із споживачів буде задоволений [7]. Складемо математичну модель задачі. кількість-Позначимо через продукту, що перевозиться з i-го пункту виробництва в j-й пункт споживання. Тоді матриця:

- план перевезень.

Матрицю

називають матрицею витрат (тарифів).

Внесемо початкові дані і перевезення

в транспортну таблицю:

Таблиця 4.

bjai	b1	b2	...	bn
a1	c11x11	c12x12	...	c1nx1n
a2	c21x21	c22x22	...	c2nx2n
...	...	...	...	...
am	cm1xm1	cm2xm2	...	cmnxmn

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

Яку необхідно мінімізувати при обмеженнях:

(весь продукт із кожного i-го

пункту повинен бути вивезений повністю),

(попит кожного j-го

споживача повинен бути повністю задоволений).

Із умови задачі виходить, что всі

Отже, математична модель сбалансованої транспортної задачі має вид:

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

.

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

2.1 Різновиди форм моделі задач лінійного програмування