Рішення. Дана задача подана у канонічному виді

Дана задача подана у канонічному виді. Побудуємо вихідний опорний план. З коефіцієнтів при змінних і вільних членах рівнянь системи обмежень складаємо розширену матрицю (її j- й стовпець відповідає вектору-стовпцю коефіцієнтів при змінній x_j (j =1,2,3,4,5), останній стовпець – вектору-стовпцю вільних членів). Приводимо дану матрицю до одиничного базису (за допомогою елементарних перетворень рядків матриці виділяємо максимальну кількість попарно різних одиничних векторів-стовпців). Помножимо перший і четвертий рядки на (–1):

.

Змінні, яким відповідають одиничні вектори-стовпці у перетвореній матриці, будемо вважати базисними, інші змінні – вільними.

У нашому випадку

I крок. Базисні змінні: x ₃, x ₄, x ₅, x ₆; вільні змінні: x ₁, x ₂.

Тому базисний розв’язок (у силу його визначення): . Цей розв’язок не є допустимим, тому що він містить дві від’ємні компоненти (виділені).

Знаходимо новий базисний розв’язок. Визначаємо базисну змінну, що виводиться з базису, і вільну змінну, що вводиться замість неї до базису. Для цього розглянемо рядки матриці, де містяться від’ємні вільні члени і (перший і четвертий), і від’ємні коефіцієнти при вільних змінних x ₁і x ₂у цих рядках: , , . Знаходимо

Мінімум досягається на елементі . Цей елемент буде ключовим. Його перший індекс визначає ключовий рядок IV (який вказує на базисну змінну x ₆, що виводиться з базису), другий індекс – ключовий стовпець II (змінну x ₂, що вводиться до базису). За допомогою елементарних перетворень рядків матриці в стовпці II будуємо одиничний вектор, в якому 1 знаходиться в рядку IV. (Помножимо рядок IV на (–1), одержимо . Потім додамо до рядка I рядок IV, помножений на 3, і віднімемо з рядків II і III рядок IV).

.

Після перетворення

II крок. Базисні змінні: x ₂, x ₃, x ₄, x ₅; вільні змінні: x ₁, x ₆.

Тому базисний розв’язок: . Цей розв’язок не є допустимим, тому що він теж містить від’ємну компоненту.

Знову виконуємо перетворення. Рядок I (з від’ємним вільним членом ) має від’ємні коефіцієнти при вільних змінних x ₁і x ₆у цьому рядку: , . Знаходимо

Мінімум відповідає елементу , тому базисною змінною, що виводиться з базису, є x ₃(третій стовпець містить одиничний вектор, в якому 1 розташована у ключовому рядку I), вільною змінною, що вводиться до базису, є x ₆. За допомогою елементарних перетворень у стовпці VI будуємо одиничний вектор, в якому 1 розташована в рядку I.

.

Після другого перетворення

III крок. Базисні змінні: x ₂, x ₄, x ₅, x ₆. Вільні змінні: x ₁, x ₃.

Базисний розв’язок: . Цей розв’язок вже є опорним планом задачі, тому що всі його компоненти невід’ємні.

Зауваження 3.1. Якщо базисний розв’язок не є допустимим, а в рівнянні, що містить від’ємний вільний член, немає вільної змінної з від’ємним коефіцієнтом, то в цьому випадку опорний план одержати неможливо, тобто умови задачі суперечливі.

3.2. Симплексні таблиці

Алгоритм знаходження оптимального плану за допомогою симплекс-таблиць:

1. Дані задачі, отримані після приведення її системи обмежень до невід’ємного одиничного базису (після визначення опорного плану), заносимо в симплекс-таблицю. У самому верхньому рядку таблиці записуємо імена стовпців Б, c_б, b і змінні x_j (j =1,.., n) задачі, указуючи під ними відповідні коефіцієнти c_j (j =1,.., n) цільової функції. У робочу (виділену) частину таблиці заносимо коефіцієнти a_ij (i =1,.., m; j =1,.., n) при змінних із системи обмежень. У першому стовпці таблиці записуємо базисні змінні (порядок їхнього запису визначається положенням одиниці відповідного одиничного вектора-стовпця), у другому – коефіцієнти цільової функції при цих базисних змінних, у третьому – вільні члени системи. У першій клітині нижнього рядка записуємо значення
цільової функції на даному опорному плані (сума добутків елементів стовпця c_б на відповідні елементи стовпця b), в інших n клітинах – оцінки оптимальності. Оцінка оптимальності , що відповідає змінній x_j, дорівнює сумі добутків елементів стовпця c_б на відповідні елементи a_ij стовпця коефіцієнтів при x_j мінус c_j.

2. Перевіряємо виконання критерію оптимальності. Якщо всі оцінки оптимальності недодатні (), то даний опорний план оптимальний – рішення закінчене. Якщо серед оцінок є додатні, то будуємо новий опорний план.

3. Найбільша додатна оцінка оптимальності визначає вільну змінну x_s, що вводиться до базису (ключовий стовпець s). Знаходимо мінімальне значення із симплексних відносин: . Якщо мінімуму нема, то задача не має розв’язку і обчислення закінчені. Якщо мінімум є, то обираємо рядок, на якому він досягається (будь-який, якщо їх декілька). Цей рядок є ключовим. Він
вказує на базисну змінну, що виводиться з базису. За допомогою елементарних перетворень одержуємо новий опорний план.

4. Переходимо до п. 1 алгоритму.

Задача 3.2. Розв’язати симплексним методом задачу планування виробництва, математичну модель якої було побудовано в задачі 1.1 (с. 5).

Дата добавления: 2014-11-06