Завдання 1
Для виготовлення ВИРОБІВ № 1 і № 2 є 100 кг металу. На виготовлення вироб № 1 вітрачається 2 кг металу, а на віріб № 2 - 4 кг.
скластись план виробництва, Що забезпечує одержания найбільшого прибутку від продаж ВИРОБІВ, ЯКЩО відпускна вартість одного вироб № 1 становіть 3 грн. од., а вироб № 2 - 2 грн. од., причому ВИРОБІВ № 1 потрібно віготовіті НЕ Більше 40 штук, а ВИРОБІВ № 2 - 20 шт.
сировина
Вироби
Кількість сировини
В1
В2
Метал
2
4
100
Вартість, грн. кг
3
2
розв'язок
Складаємо математичних модель Задачі. Позначімо через х 1 кількість вироб № 1, Що віготовляє підприємство за Деяк планом, а через х2 кількість вироб № 2. Тоді прибуток, отриманого підпріємством від реалізації ціх ВИРОБІВ, складає
∫ = 3х1 +2 х2.
Витрати сировини на виготовлення Такої кількості ВИРОБІВ складають відповідно:
CI = 2х1 +4 х2,
Оскількі запаси сировини обмежені, то повінні віконуватісь нерівності:
2х1 +4 х2 ≤ 100
Окрім того, ВИРОБІВ № 1 потрібно віготовіті НЕ Більше 40 штук, а ВИРОБІВ № 2 - 20 шт., тобто повінні віконуватісь галі нерівності: х1 ≤ 40, х2 ≤ 20.
Таким чином, пріходімо до математичної Моделі:
знайте х1, х2такі, Що функція ∫ = 3х1 +2 х2досягає максимуму при сістемі обмежень:
Розв'язуємо задачу лінійного програмування симплексним методом.
Для Побудова Першого опорного плану систему нерівностей пріведемо до системи рівнянь шляхом Введення Додатковий змінніх.
2x1 + 4x2 + 1x3 + 0x4 + 0x5 = 100
1x1 + 0x2 + 0x3 + 1x4 + 0x5 = 40
0x1 + 1x2 + 0x3 + 0x4 + 1x5 = 20
Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має Вигляд:
Базісні змінні Це змінні, які входять Ліше в Одне рівняння системи обмежень и притому з одінічнім коефіцієнтом.
Вірішімо систему рівнянь відносно базисних змінніх:
x3, x4, x5
Вважаючі, Що Вільні змінні рівні 0, отрімаємо Перший опорний план:
X1 = (0,0,100,40,20)
Оскількі Завдання вірішується на максимум, то ведучий стовпець вібіраємо по максимальному негативному кількістю та індексного рядку. Всі перетворення провідності до тихий пір, Поки НЕ війдуть в індексному рядку Позитивні елементи.
Складаємо симплекс-таблицю:
План
Базис
В
x1
x2
x3
x4
x5
min
1
x3
100
2
4
1
0
0
50
x4
40
1
0
0
1
0
40
x5
20
0
1
0
0
1
0
Індексній рядок
F (X1)
0
-3
-2
0
0
0
0
Оскількі, в індексному рядку знаходяться негатівні коефіцієнті, поточний опорний план неоптимальним, тому Будуємо новий план. У ЯКОСТІ ведучого віберемо елемент у стовбці х1, оскількі Значення коефіцієнта за модулем найбільше.
План
Базис
В
x1
x2
x3
x4
x5
min
2
x3
20
0
4
1
-2
0
5
x1
40
1
0
0
1
0
0
x5
20
0
1
0
0
1
20
Індексній рядок
F (X2)
120
0
-2
0
3
0
0
Сейчас план, кож не оптимальний, тому Будуємо Знову нову симплексного таблиці. У ЯКОСТІ ведучого віберемо елемент у стовбці х2.
План
Базис
В
x1
x2
x3
x4
x5
min
3
x2
5
0
1
0,25
-0,5
0
5
x1
40
1
0
0
1
0
0
x5
15
0
0
-0,25
0,5
1
20
Індексній рядок
F (X3)
130
0
0
0,5
2
0
0
Оскількі ВСІ оцінкі> 0, то Знайда оптимальний план, Що забезпечує Максимальний прибуток: х1 = 40, х2 = 5. Прибуток, при випуску продукції за ЦІМ планом, становить 130 грн.
Завдання 2
Запісаті двоїсту задачу до поставленої Задачі лінійного програмування. Розв'язати одну Із завдань симплексним методом и візначіті оптимальний план іншої Задачі.
розв'язок
Розв'яжемо задачу лінійного програмування симплексним методом.
Візначімо мінімальне Значення цільової функції F (X) = x1 +3 x2прі Наступний Умова-обмежень.
9x1 +10 x2 ≥ 45
5x1-x2 ≤ 42
-x1 +13 x2 ≤ 4
Для Побудова Першого опорного плану систе...
