РІШЕННЯ ЗАДАЧІ ОПТИМІЗАЦІЇ НА ОСНОВІ СИМПЛЕКС-ТАБЛИЦ, ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ, ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ - Рішення оптимізаційної задачі лінійного програмування

ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ

Для приведення даного завдання до стандартної форми необхідно лише перейти від обмежень - нерівностей до рівності. Для цього введемо додаткові балансові ненегативні змінні. Також для спрощення подальших обчислень розділимо обидві частини обмежень на комплектацію деталей на 5:

X1 + X2 + X3 + X7 = 8;

X4 + X5 + X6 + X8 = 8;

    2X1 - X2 + 6X4 - 3X5 = 0; 2X1 - 2X3 + 6X4 - 2X6 =0;

X1, X2, X3, X4, X5, X6, X7, X8 v 0.

E= X1 + X2 + 2X3 + 3X4 + 3X5 + 2X6 max

Де Х7, Х8 - залишкові змінні.

Отже, наше початкове завдання ми привели до стандартної форми основного завдання лінійного програмування.

ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ

Для завдання, представленого в стандартній формі, кількість змінних звичайна більше, ніж кількість обмежень. Тому для знаходження початкового рішення задачі потрібно виразити m змінних (тобто кількість змінних, рівна кількості рівнянь) через решту n-m змінних, прийняти ці n-m змінних рівними нулю і, таким чином, знайти значення m змінних (у заданому завданні m=4 і n=8). Змінні, значення яких приймаються рівними нулю, називаються небазисними, а решта m змінних - базисними. Значення базисних змінних ненегативні (деякі з них можуть виявитися рівними нулю). Кількість базисних змінних завжди рівна кількості обмежень. Знайдене таким чином рішення називається початковим допустимим базисним рішенням. Воно відповідає всім обмеженням.

Початкове рішення найпростіше знайти у разі, коли в кожному обмеженні є змінна, яка входить в нього з коефіцієнтом 1 і при цьому відсутній в інших обмеженнях. Такі змінні приймаються як базисні (вони утворюють початковий базис завдання). Решта (небазисні) змінних приймається рівними нулю. Таким чином, базисні змінні приймають значення, рівні правим частинам обмежень.

Отже, для знаходження початкового допустимого рішення необхідно, щоб в кожне з рівнянь входила змінна з коефіцієнтом 1 і не входила в інші рівняння (базисна змінна). У нашому випадку ми маємо тільки 2 базисних змінної (X7 і X8), не вистачає ще двох базисних змінних. Їх можна створити за допомогою спеціального способу, який називається побудовою штучного базису.

Похожие статьи




РІШЕННЯ ЗАДАЧІ ОПТИМІЗАЦІЇ НА ОСНОВІ СИМПЛЕКС-ТАБЛИЦ, ПРИВЕДЕННЯ ЗАВДАННЯ ДО СТАНДАРТНОЇ ФОРМИ, ВИЗНАЧЕННЯ ПОЧАТКОВОГО ДОПУСТИМОГО РІШЕННЯ - Рішення оптимізаційної задачі лінійного програмування

Предыдущая | Следующая