Мета роботи: вивчення двоїстої задачі лінійного програмування із застосування симплекс методу для знаходження розв’язку. План Короткі теоретичні відомості. Постановка задачі Двоїста задача із застосуванням сиплекс методу. Розв’язання за допомогою пакету програм SimplexWin Розв’язання за допомогою власної програми. Хід роботи 1. Короткі теоретичні відомості Кожній задачі лінійного програмування відповідає двоїста Спільний розгляд таких пар задач дозволяє проводити економічний аналіз результатів розрахунку. Пряма задача (мах) – розподіл обмежених ресурсів між різними споживачами, напр. між деякими технологічними процесами – стовпці матриці А. Рішення задачі (х1,х2,…,хn) вказує ту долю кожного із ресурсів хj, щоб отримати максимум прибутку. Завод випускає три види продукції х1,х2,х3 . кожен вид продукції вимагає затрат часу на обробку на токарному, фрезельному і свердлильному станках. Кількість машинного часу для кожного із станків обмежена. Нехай с1,с2,с3 – прибуток від одиниці відповідного виду продукції. Необхідно визначити, яку кількість кожного виду продукції (хj) необхудно випускати протягом визначеного часу, щоб отримати максимальний прибуток Обмеження
де а1j, а2j, а3j - час необхідний для обробки одиниці j-го виду продукції відповідно на токарному, фрезерному і свердлильному станках (j = 1,2,3); b1, b2, b3 - ресурс машинного часу відповідно для токарного, фрезерного і свердлильного станків. Для переходу до двоїстої задачі Позначимо y1, y2, y3 – ціну одиниці часу роботи на токарному, фрезерному і свердлильному станках: (yi>0). Тоді
витрати на виробництво Fmin при умові, що сумарні затрати на одиницю продукції не менше вартості товару. Обмеження
Основна теорема двоїстості Для оптимальних рішень пар двоїстих задач виконується умова :
Двоїсту задачу вигідно розв’язувати, коли в прямій задачі при малій кількості змінних є велика кількість обмежень (m > n). Індивідуальне завдання(варіант 32): F(x1,x2) = x1 + x2 max ; 3x1 - 2x2 -6, x1 + 2x2 3, 3x1 0, 5 x2 0. Розвя’зання без допомоги пакетів програм: F(y1, y2, y3) = 6y1 - 3y2 + 3y3 + 5y4 MIN -3y1 – y2 + y3 ? 1; 2y1 - 2y2 + y4 ? 1; Тобто: Кофіцієнти цільової функції прямої задачі с1,с2,…,сn стають вільними членами обмежень двоїстої задачі. Вільні члени обмежень прямої задачі b1,b2,…,bn стають коефіцієнтами цільової функції двоїстої задачі. Матрицю обмежень двоїстої задачі отримують транспонуванням матриці обмежень прямої задачі. Число змінних двоїстої задачі рівне числу обмежень прямої, а число обмежень двоїстої рівне числу змінних прямої, і навпаки. Взаємно однозначна відповідність між змінними прямої задачі і обмеженнями двоїстої: j-е обмеження двоїстої задачі буде нерівністю, якщо на j-у змінну прямої задачі накладена вимога невід’ємності, а в іншому випадку – j-е обмеження буде рівністю. Використання симплекс-методу: Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці. Визначимо мінімальне значення цільової функції F (X) = 6x1 - 3x2 + 3x3 + 5x4 при наступних умовах-обмежень. - 3x1 - x2 + x3?1 2x1 - 2x2 + x4?1 Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної форми). -3x1-1x2 + 1x3 + 0x4-1x5 + 0x6 = 1 2x1-2x2 + 0x3 + 1x4 + 0x5-1x6 = 1 Помножимо всі рядки на (-1) і будемо шукати початковий опорний план. 3x1 + 1x2-1x3 + 0x4 + 1x5 + 0x6 = -1 -2x1 + 2x2 + 0x3-1x4 + 0x5 + 1x6 = -1 Матриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд:Вирішимо систему рівнянь щодо базисних змінних:x5, x6, Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:X1 = (0,0,0,0,-1,-1) Базис B x1 x2 x3 x4 x5 x6
x5 -1 3 1 -1 0 1 0
x6 -1 -2 2 0 -1 0 1
F(X0) 0 6 -3 3 5 0 0
План 0 в симплексного таблиці є псевдопланом, тому визначаємо провідні рядок і стовпець. На перетині провідних рядка і стовпця знаходиться елемент (РЕ), рівний (-1). Базис B x1 x2 x3 x4 x5 x6
x5 -1 3 1 -1 0 1 0
x6 -1 -2 2 0 -1 0 1
F(X) 0 6 -3 3 5 0 0
? 0 - - 3 : (-1) = -3 - - -
Виконуємо перетворення симплексного таблиці методом Жордана-Гаусса. Базис B x1 x2 x3 x4 x5 x6
x3 1 -3 -1 1 0 -1 0
x6 -1 -2 2 0 -1 0 1
F(X0) -3 15 0 0 5 3 0
План 1 в симплексного таблиці є псевдопланом, тому визначаємо провідні рядок і стовпець. На перетині провідних рядка і стовпця знаходиться елемент (РЕ), рівний (-1). Базис B x1 x2 x3 x4 x5 x6
x3 1 -3 -1 1 0 -1 0
x6 -1 -2 2 0 -1 0 1
F(X) -3 15 0 0 5 3 0
? 0 15 : (-2) = -71/2 - - 5 : (-1) = -5 - -
Виконуємо перетворення симплексного таблиці методом Жордана-Гаусса. Базис B x1 x2 x3 x4 x5 x6
x3 1 -3 -1 1 0 -1 0
x4 1 2 -2 0 1 0 -1
F(X1) -8 5 10 0 0 3 5
У базисному стовпці всі елементи позитивні. Переходимо до основного алгоритму симплекс-метода. Кінець ітерацій: індексна рядок не містить негативних елементів - знайдений оптимальний планОстаточний варіант симплекс-таблиці: Базис B x1 x2 x3 x4 x5 x6
x3 1 -3 -1 1 0 -1 0
x4 1 2 -2 0 1 0 -1
F(X1) -8 5 10 0 0 3 5
Оптимальний план можна записати так:x3 = 1 x4 = 1 F(X) = 31 + 51 = 8 2.Реалізація за допомогою пакета SymplexWin: 1. Задаємо розмір матриці «Настройки» -> «Розмір матриці» (в даному випадку 4х2)
Вводимо дані в програму і натискаємо «Задача» - «Створити двоїсту»:
Після цього натискаємо «Вирахувати»
Натискаємо кілька раз «Авто», щоб спостерігати за ходом виконання:
Дані експортовані в MS Excel: Шаг 0
Базис БП y 1 y 2 y 3 y 4 y 5 y 6
y3 1 -3 -1 1 0 -1 0
y4 1 2 -2 0 1 0 -1
ИС -8 5 10 0 0 3 5
Реалізація за допомогою власної програми(реалізована на С++): #include <iostream> #include <string> #include <cstdlib> #include <cmath> #include <fstream> #include <sstream> using namespace std; class user_data { double *function; double *fm; double **system; int *sign; int num_v; int num_l; bool way; public: void get_data_from_user(); void go_to_dvoist(); void user_data_is_valid(); }; void error(int err_no) { switch(err_no) { case 0: cout << "Ви ввели не коректне значення." << endl; break; case 1: cout << "Ви не можете задати менше 2 рiвнянь." << endl; break; case 2: cout << "Ви не можете задати бiльше 500 р-нь." << endl; break; case 3: cout << "Ви не можете задати менше 2 змiнних." << endl; break; case 4: cout << "Ви не можете задати бiльше 500 р-нь." << endl; break; } }
void user_data::get_data_from_user() { string num_limits, num_vars, s_var, fr_m, sn, func, w; int i, j; bool validator = false;
do { cout << "Введiть к-ть р-нь системи: "; getline(cin, num_limits); if (atoi(num_limits.c_str()) < 2) error(1); else if (atoi(num_limits.c_str()) > 500) error(2); else validator = true;
function = new double [num_v]; system = new double *[num_l]; for (i = 0; i < num_l; i++) system[i] = new double [num_v]; fm = new double [num_l]; sign = new int [num_l];
cout << "Заповнiть коефiцiєнти при цiльовiй ф-ї" << endl;
for (i = 0; i < num_v; i++) { do { cout << "Введiть коефiцiєнт цiльової ф-ї при x" << i + 1 << ": "; getline(cin, func); if (atof(func.c_str()) < 0) error(0); else { validator = true; function[i] = atof(func.c_str()); } } while (!validator); validator = false; }
do { cout << "Введiть напрям цiльової ф-ї ( min, max ) : "; getline(cin, w); if (w == "max" || w == "MAX" || w == "min" || w == "MIN") { validator = true; if (w == "max" || w == "MAX") way = true; else way = false; } else error (0);
} while (!validator); cout << "Заповнiть системи р-нь" << endl;
for (i = 0; i < num_l; i++) { cout << "Заповнiть" << i + 1 << "-е р-ня." << endl; for (j = 0; j < num_v; j++) { do { cout << "Введiть коефiцiєнт при x" << j + 1 << ": "; getline(cin, s_var); if (atof(s_var.c_str()) < 0) error (0); else { validator = true; } } while (!validator); system[i][j] = atof(s_var.c_str()); validator = false; }
do { cout << "Введiть знак при " << i + 1 << "-му р-нi ( <=, =, >= ) : "; getline(cin, sn); if (sn == "<=" || sn == "=" || sn == ">=") { validator = true; if (sn == "<=") sign[i] = 0; if (sn == "=") sign[i] = 1; if (sn == ">=") sign[i] = 2; } else error(0); } while (!validator);
validator = false;
do { cout << "Введiть значення вiльного члена (Bi) при " << i + 1 << "-му р-нi: "; getline(cin, fr_m); if (atof(fr_m.c_str()) == 0) error(0); else validator = true; } while (!validator);
fm[i] = atof(fr_m.c_str()); validator = false;
cout << endl;
}
} void user_data::go_to_dvoist() { int i,j; user_data *ud2= new user_data; ud2->num_l=num_v; ud2->num_v=num_l; ud2->function = new double [ud2->num_v]; ud2->system = new double *[ud2->num_l]; for (i = 0; i < ud2->num_l; i++) ud2->system[i] = new double [ud2->num_v]; ud2->fm = new double [ud2->num_l]; ud2->sign = new int [ud2->num_l];
