49869 (609343), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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

Таблиця 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.

bj ai	b1	b2	...	bn
a1	c11 x11	c12 x12	...	c1n x1n
a2	c21 x21	c22 x22	...	c2n x2n
...	...	...	...	...
am	cm1 xm1	cm2 xm2	...	cmn xmn

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

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

(весь продукт із кожного i-го пункту повинен бути вивезений повністю),

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

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

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

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

.

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

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

2.1.1 Загальна форма моделі

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

Знайти сукупність значень n змінних що задовольняють системі обмежень:

і умові невід’ємності:

,

для яких лінійна функція (цільова функція) досягає екстремуму (максимуму або мінімуму) [9].

2.1.2 Стандартна форма моделі

Знайти сукупність значень n змінних що задовольняють системі обмежень:

і умові невід’ємності:

,

для яких лінійна функція (цільова функція) досягає максимуму.

Якщо ввести у розгляд матрицю:

і вектори:

, , ,

то стандартна форма моделі матиме вид:

Задачу ЛП в стандартній формі зручно вирішувати графічним методом, якщо число змінних дорівнює двом ( ) [1].

2.1.3 Канонічна форма моделі

Знайти сукупність значень n змінних що задовольняють системі рівнянь:

( )

і умові невід’ємності:

( ),

для яких цільова функція досягає максимуму.

Компактна форма моделі має вид:

,

,

. [9].

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

Симплекс-метод — метод розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального розв'язку; симплекс-метод також називають методом поступового покращення плану [6].

Опишемо метод.

Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:

,

Характеристики

Список файлов курсовой работы