Задача лінійного програмування
Методика формування плану виготовлення виробів, при якому загальна вартість всієї виробленої підприємством продукції є максимальною. Порядок розробки плану перевезень цегли до будівельних об’єктів, при якому загальна вартість перевезень є мінімальною.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | украинский |
| Дата добавления | 21.02.2013 |
| Размер файла | 43,4 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Задача використання ресурсів
Для виготовлення різних виробів А, В і С підприємство використовує три види сировини (І, ІІ і ІІІ). Норми витрати сировини на виробництво одного виробу, ціна одного виробу А, В і С, а також загальна кількість сировини кожного виду, яка може бути використана підприємством, навені в таблиці.
|
Вид сировини |
Норми витрат сировини (кг) на один виріб |
Загальна кількість сировини, кг |
|||
|
А |
В |
С |
|||
|
І |
1 |
6 |
0 |
25 |
|
|
ІІ |
8 |
3 |
4 |
60 |
|
|
ІІІ |
5 |
6 |
2 |
96 |
|
|
Ціна одного виробу, у.о. |
10 |
5 |
3 |
- |
Вироби А, В і С можуть вироблятись в будь-яких співідношеннях, але виробництво обмежене виділенною підприємству сировиною кожного виду.
Скласти план виготовлення виробів, при якому загальна вартість всієї виробленої підприємством продукції є максимальною.
Розв'язок:
Введемо позначення:
Нехай X1, X2, Х3 - це відповідно кільсть плит А, В і С, що потрібно виготивити підприємству.
F - сумарний прибуток від реалізації всієї продукції.
Складемо матеметичну модель задачі:
Приведемо дану задачу до канонічної форми запису, з цією метою введемо три додаткові змінні (Х4, Х5, Х6) які означатимуть залишкі сировини трьох видів, після виговлення усіх плит.
Для розв'яку даної задачі утворимо утворимо початковий оптимальний початковий план. Для цього надаємо:
Х1=Х2=Х3=0 > отримаємо значення базисних змінних: Х4=25 Х5=60 Х6=196, а сам опорний план буде мати такій виляд:
Хо(0; 0; 0; 25; 60; 96)
Розв'язок задачі продовжимо з використанням симплекс-таблиць
|
№ сим. табл |
Б |
СБ |
А0 |
С1=10 |
С2=5 |
С3=3 |
С4=0 |
С5=0 |
С6=0 |
Qij |
|
|
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
||||||
|
1 |
А4 |
0 |
25 |
1 |
6 |
0 |
1 |
0 |
0 |
25 |
|
|
А5 |
0 |
60 |
8 |
3 |
4 |
0 |
1 |
0 |
7,5 |
||
|
А6 |
0 |
96 |
5 |
6 |
2 |
0 |
0 |
1 |
19,2 |
||
|
m+1 |
0 |
-10 |
-5 |
-3 |
0 |
0 |
0 |
||||
|
2 |
А4 |
0 |
17,5 |
0 |
5,625 |
-0,5 |
1 |
-0,125 |
0 |
3,11 |
|
|
А1 |
10 |
7,5 |
1 |
0,375 |
0,5 |
0 |
0,125 |
0 |
20 |
||
|
А6 |
0 |
58,5 |
0 |
4,125 |
-0,5 |
0 |
-0,625 |
1 |
14,18 |
||
|
m+1 |
75 |
0 |
-1,25 |
2 |
0 |
1,25 |
0 |
||||
|
3 |
А2 |
5 |
3,11 |
0 |
1 |
-0,08 |
0,17 |
-0,02 |
0 |
||
|
А1 |
10 |
6,33 |
1 |
0 |
0,53 |
-0,06 |
0,13 |
0 |
|||
|
А6 |
0 |
45,66 |
0 |
0 |
-0,13 |
-0,73 |
-0,53 |
1 |
|||
|
m+1 |
78,88 |
0 |
0 |
1,88 |
0,22 |
1,22 |
0 |
Умова оптимальності розв'язку задачі максимізації:
Zj - сума добутків
Економічне пояснення розв'язку задачі:
В результаті розв'язку задачі отримали оптимальний план
З цього плану досягається максимальне значення цільової функції: F=78,88
Висновок: Для того щоб отримати максимальний прибуток в кількості 78,8 в умовах постановки даної задачі необхідно виготовляти: 6,33 виробів І типу, 3,11 виробів ІI типу, при цьому залишається не використаною сировина ІII-го виду в кількості 45,66.
вартість виготовлення перевезення будівельний
Транспортна задача
Для будівництва об'єктів В1,…, Вn використовується цегла, що виготовляється на заводах А1,…, А3. Щоденно кожен із заводів може виготовляти а1,…, а3 ум. од. цегли. Щоденні потреби в цеглі на кожному із будівельних об'єктів відповідно рівні b1,…, b4. Тарифи перевезень 1 ум. од. цегли від кожного із заводів до кожного з об'єктів (год.) задаються матрицею Т.
Cкласти такий план перевезень цегли до будівелтних об'єктів, при якому загальна вартість перевезень є мінімальною.
Розрахунок:
1. Визначаємо вид транспортної задачі
Визначаємо сумарні запаси і сумарні потреби
І для її розвязку приведемо транспортну задачу до закритої.
Для цього введемо фіктивного постачальника , запаси вантажів у якого складатимуть
Матриця тарифів перевезень буде мати такий вигляд
2. Складемо опорний план перевезень вантажів
Опорні плани перевезень складемо трьома методами і виберемо серед них той, сумарні затрати на перевезення для якого будуть найменшими
Для кожного з опорних планів повинна виконуватися умова не виродженості:
Кількість заповнених клітинок таблиці перевезень (маршрутів перевезень) повинна складатись
Опорний план за методом Півн. Зх. кута
|
J і |
Споживачі |
Запаси |
|||||
|
В1 |
В2 |
В3 |
В4 |
||||
|
Постачальники |
A1 |
1 |
9 |
7 |
2 |
30 |
|
|
30 |
- |
- |
- |
||||
|
A2 |
3 |
1 |
5 |
5 |
40 |
||
|
5 |
35 |
- |
- |
||||
|
A3 |
6 |
8 |
3 |
4 |
70 |
||
|
- |
45 |
25 |
- |
||||
|
A4 |
2 |
3 |
1 |
3 |
60 |
||
|
- |
- |
0 |
60 |
||||
|
A5 |
0 |
0 |
0 |
0 |
10 |
||
|
- |
- |
- |
10 |
||||
|
Потреби |
35 |
80 |
25 |
70 |
210 |
Визначимо сумарні затрати на перевезення вантажів.
т.км
Опорний план за методом мінімального елементу
|
J і |
Споживачі |
Запаси |
|||||
|
В1 |
В2 |
В3 |
В4 |
||||
|
Постачальники |
A1 |
1 |
9 |
7 |
2 |
30 |
|
|
30 |
- |
- |
0 |
||||
|
A2 |
3 |
1 |
5 |
5 |
40 |
||
|
- |
40 |
- |
- |
||||
|
A3 |
6 |
8 |
3 |
4 |
70 |
||
|
- |
- |
- |
70 |
||||
|
A4 |
2 |
3 |
1 |
3 |
60 |
||
|
5 |
30 |
25 |
- |
||||
|
A5 |
0 |
0 |
0 |
0 |
10 |
||
|
- |
10 |
- |
- |
||||
|
Потреби |
35 |
80 |
25 |
70 |
210 |
Сумарні затрати на перевезення для даного опорного плану
т/км
Опорний план за методом подвійної переваги
|
J і |
Споживачі |
Запаси |
|||||
|
В1 |
В2 |
В3 |
В4 |
||||
|
Постачальники |
A1 |
1 |
9 |
7 |
2 |
30 |
|
|
30 |
- |
- |
0 |
||||
|
A2 |
3 |
1 |
5 |
5 |
40 |
||
|
- |
40 |
- |
- |
||||
|
A3 |
6 |
8 |
3 |
4 |
70 |
||
|
- |
- |
- |
70 |
||||
|
A4 |
2 |
3 |
1 |
3 |
60 |
||
|
5 |
30 |
25 |
- |
||||
|
A5 |
0 |
0 |
0 |
0 |
10 |
||
|
- |
10 |
- |
- |
||||
|
Потреби |
35 |
80 |
25 |
70 |
210 |
Сумарні затра
ти на перевезення для даного опорного плану
т.км.
Умови оптимальності плану перевезеньтранспортної задачі:
- для всіх заповнених клітинок
- для всіх порожніх клітинок
Запишемо систему потенціалів для заповнених клітинок
Перевіримо порожні клітинки на умову оптимальності
U1 +V2 =2<9
U1 +V3 =0<7
U2 +V1 =0<3
U2 +V3 =-1<5
U2 +V4 =1<5
U3 +V1 =3<6
U3 +V2 =4<8
U3 +V3 =2<3
U4 +V4 =3=3
U5 +V1=-1<0
U5 +V3=-2<0
U5 +V5=0=0
Оскільки умова оптимальності для порожніх клітинок виконується, то даний опорний план є оптимальним.
Затрати на перевезення вантажів за планом 2.2 будуть мінімальними і складуть:
т.км.
Матриця перевезень оптимального плану матиме вигляд
Оскільки споживач отримає 10 т вантажу від фіктивного постачальника, то його потреби не будуть повністю задоволені.
Размещено на Allbest.ru
Подобные документы
Дослідження предмету і сфери застосування математичного програмування в економіці. Класифікація задач цієї науки. Загальна задача лінійного програмування, деякі з методи її розв’язування. Економічна інтерпретація двоїстої задачі лінійного програмування.
курс лекций [59,9 K], добавлен 06.05.2010Розв'язок задач лінійного програмування симплексним методом, графічне вирішення системи нерівностей, запис двоїстої задачі: визначення прибутку, отриманого підприємством від реалізації виробів; загальних витрат, пов’язаних з транспортуванням продукції.
контрольная работа [296,0 K], добавлен 28.03.2011Послідовність графічного розв'язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід'ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.
задача [320,6 K], добавлен 31.05.2010Складання плану виробництва при максимальному прибутку. Введення додаткових (фіктивних) змінних, які перетворюють нерівності на рівності. Розв’язування задачі лінійного програмування графічним методом та економічна інтерпретація отриманого розв’язку.
контрольная работа [298,3 K], добавлен 20.11.2009Методи зведення до канонічної форми задач лінійного програмування. Визначення шляхів знаходження екстремумів функцій графічним способом. Побудова початкового опорного плану методом "північно-західного" напрямку. Складання двоїстої системи матриць.
контрольная работа [262,0 K], добавлен 08.02.2010Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.
лабораторная работа [264,1 K], добавлен 30.03.2015Основні типи та види моделей. Основні методи складання початкового опорного плану. Поняття потенціалу й циклу. Критерій оптимальності базисного рішення транспортної задачі. Методи відшукання оптимального рішення. Задача, двоїста до транспортного.
курсовая работа [171,2 K], добавлен 27.01.2011Теорема Куна-Такера. Побудування функції Лагранжа. Задача квадратичного програмування. Узагальнення симплексного метода лінійного програмування згідно методу Біла. Правила переходу від однієї таблиці до іншої. Система обмежень у допустимої області.
курсовая работа [252,9 K], добавлен 08.05.2014Сутність симплекс-методу у вирішенні задач лінійного програмування. Рішення задачі на відшукання максимуму або мінімуму лінійної функції за умови, що її змінні приймають невід'ємні значення і задовольняють деякій системі лінійних рівнянь або нерівностей.
реферат [28,5 K], добавлен 26.02.2012Використання методів розв’язування одновимірних оптимізаційних задач (метод дихотомії, золотого перерізу, Фібоначі) для визначення найменшого значення функції на відрізку. Задача мінімізації за допомогою методу Ньютона і методу найшвидшого спуску.
курсовая работа [739,5 K], добавлен 05.05.2011
