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

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

Таблиця 2.

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

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

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

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

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

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

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

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

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

Таблиця 3.

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

.

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

.

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

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

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

Очевидно, що

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

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

.

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

,

.

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

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

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

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

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

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

Внесемо початкові дані і перевезення в транспортну таблицю:

Таблиця 4.

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

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

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

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

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

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

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

.

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

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

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

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

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

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

,

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

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

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

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

,

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

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

і вектори:

, , ,

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

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

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

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

( )

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

( ),

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

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

,

,

. [9].

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

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

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

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

,