Економічні задачі лінійного програмування і методи їх вирішення
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?му буде виготовлено найбільшу кількість готових виробів у заданому асортименті чи буде досягнуто найменшу кількість відходів. Нехай на обробку поступає a одиниць сировинного матеріалу одного виду (наприклад, a колод однієї довжини). З нього потрібно виготовити комплекти, в кожен з яких входить n видів виробів у кількості, пропорційній числах. Є m способів розкрою (обробки) даного матеріалу, тобто відомі величини визначають кількість одиниць j-х виробів при i-му способі розкрою одиниці сировинного матеріалу [10].
Визначити план розкрою, що забезпечує максимальну кількість комплектів. Згідно з умовами завдання маємо таблицю розкрою:
Таблиця 3.
Вид виробу
Спосіб
розкрою
1
...
j
...
n1a11...a1j...a1n…...............iai1...aij...ain…...............mam1...amj...amn
Нехай кількість одиниць сировинного матеріалу, розкроюється i-м варіантом ( .
Тоді кількість виробів 1-го виду одно:
.
Беручи до уваги умову комплектності, маємо:
де y кількість комплектів.
Аналогічні рівності можна записати і для всіх інших видів виробів, тобто умова комплектності призводить до системи обмежень:
Очевидно, що
(на розкрій надходить a одиниць сировинного матеріалу), а також
Мета задачі максимізувати кількість комплектів:
.
Отже, приходимо до математичної моделі задачі про розкроєння:
,
.
Щоб виразити цільову функцію через змінні x1,…,xm, достатньо скористуватися будь-яким із співвідношень:
1.2.4 Транспортна задача
Розглянемо транспортну задачу, тобто завдання, в якій мова йде про раціональну перевезення деякого однорідного продукту від виробників до споживачів.
Нехай є m пунктів виробництва однорідного продукту (видобуток руди в карєрах, виробництво автобусів, кондитерських виробів, компютерів і т.д.) і n пунктів споживання цього продукту. Потужності пунктів виробництва складають аi одиниць однорідного продукту, а потреби кожного j-го пункту споживання рівні одиниці. Відомі витрати на перевезення одиниці продукту від i-го постачальника j-му споживачеві. Скласти такий план перевезень, при якому сумарні витрати на всі перевезення були б найменшими. Нехай попит і пропозиція збігаються, тобто Таку транспортну задачу називають збалансованою (закритою). При цьому передбачається, що вся продукція від постачальників буде вивезена і попит кожного із споживачів буде задоволений [7]. Складемо математичну модель задачі. кількістьПозначимо через продукту, що перевозиться з i-го пункту виробництва в j-й пункт споживання. Тоді матриця:
план перевезень.
Матрицю називають матрицею витрат (тарифів).
Внесемо початкові дані і перевезення в транспортну таблицю:
Таблиця 4.
bj
aib1b2...bna1 c11
x11 c12
x12... c1n
x1na2 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].
Опишемо метод.
Нехай невироджену задачу лінійного програмування представлено в канонічному вигляді:
,
де X = (x1, …, xn) вектор змінних,
C = (c1, …., cn), B = (b1, …, bm)T,
Aj = (a1j, …, amj)T, j = 1, …, n задані вектори,
T знак транспонування, та
&