Лінійне програмування
Завдання оптимального планування виробництва на авіапідприємстві
Авіапідприємство по конструюванню і виробництву повітряних суден планує технічну доробку двох типів літаків I і II, для здійснення якої необхідно витрачати три види комплектуючих A, B і C. Потреба аij на кожен літак j-го типу комплектуючих i-го виду, запас bi відповідного виду комплектуючих і прибуток Cj від випуску і реалізації одиниці j-го типу модернізованого повітряного судна задані таблицею:
Індивідуальні значення: m=4, n=5
Види комплектующіхТіпи самолетовЗапаси комплектующихIIIAa11=5a12=2b1=45Ba21=1a22=1b2=12Ca31=2a32=5b3=45Прибыльc1=6c2=6План(ед)х1х2- Кількість літаків типу I- кількість літаків типу II
Завдання:
а) Скласти цільову функцію прибутку L і відповідну систему обмежень по запасах комплектуючих, припускаючи, що потрібно виготовити в сумі не менше n одиниць літаків.
б) В умовах задачі скласти оптимальний план (х1, х2) виробництва забезпечує максимальний прибуток Lmax. Визначити залишки кожного виду комплектуючих. (Завдання вирішити симплекс-методом).
в) Побудувати по отриманій системі обмежень багатокутник допустимих рішень і знайти оптимальний план виробництва геометричним шляхом. Визначити відповідний прибуток Lmax.
Скласти двоїсту задачу і знайти її рішення по теоремам подвійності.
а) 1. Вводимо змінні, де х?=(х1, х2)
2.Система обмежень
х1 + 2х2? 45
х1 + х2? 12
х1 + 2х2? 45
х1? 0
х2? 0
х1 + х2? 5
) цільова функція:
z=3х1 + 6х2 max
x1 + 2x2? 45 + x2? 12
x1 + 5x2? 45 + x2? 5
=45-5x1-2x2? 0=12-x1-x2? 0=45-2x1-5x2? 0=- 5 + x1 + x2? 0
4) візьмемо х1 і х2 в якості вільних змінних, а х3, х4, х5, х6 в якості базисних.
б) Симплекс-метод
Базисні переменниеСвободние члениСвободние переменниех1х2x345 - 105 - 22 2x412 - 51 - 11 1x545 - 252 - 55 5x6-5 5-1 1-1 - 1L0 30-6 6-6 - 6
Базисні переменниеСвободние члениСвободние переменниех1x6x335 - 83 1,22 - 0,4x47 - 40 0,61 - 0,2x520 4-3 - 0,65 0,2x25 41 - 0,6-1 0,2L30 240 - 3,6-6 1,2
Базисні переменниеСвободние члениСвободние переменниех1x5x327 - 214,2 - 7-0,4 1,4x43 50,6 1,6-0,2 - 0,3x64 3-0,6 10,2 - 0, 2x29 - 2,10,4 - 0,70,2 0,14L54 18-3,6 - 61,2 - 1,2
Базисні переменниеСвободние члениСвободние переменниеx4x5x36 - 7 1 x15 1,6 - 0,3 x67 1 0 x26,9 - 0,7 0,34 L72 6 0
х1=5 I тип літаків
х2=6,9? 7 II тип літаків
х3=6 кількість залишків сировини А
х4=0 кількість залишків сировини В (витрачено повністю)
х5=0 сировину З витрачено
х6=7 для перевірки повністю
Оптимальний план: (5; 6,9; 6; 0; 0; 7) прибуток в кількості 72 одиниць досягається, якщо доопрацювати I тип літака з використанням 7 запасів комплектуючих, а технічну доробку II типу літака з використанням 5 комплектуючих.
Двоїста задача
=6x1 + 6x2
x1-2x2?- 45
x1-x2?- 12
x1-5x2?- 45 + x2? 5
- 5 - 2 - 45 * - 1 - 1 - 12
- 2-5 - 45
1. 1 5
6 червня Z
Транспоніруем матрицю:
- 5 - 1 - 2 1 6
А2 * - 2 - 1 - 5 1 6
- 45 - 12 - 45 +5 2
L=45y1 - 12y2 - 45y3 - 5y4
- 5 - 1 - 2 1? 6
- 2 - 1 - 5 1? 6
=Lmin=72
*=5 *=7 *=6 *=0 *=0 *=7
Змінні прямої задачі
ОсновниеДополнітельниеx1 x2x3, x4, x5, x6y5 y6y1, y2, y3, y4Переменние подвійної задачі
Відповідь: Lmin=72. Оптимальний план: y1 *=0; y2 *=0; y3 *=3; y4 *=0; y5 *=0; y6 *=0
Теорія масового обслуговування
Завдання 1.
Необхідно спроектувати автоматизовану інформаційну систему (АІС) так, щоб вона володіла пропускною здатністю, при якій імов...
