Мета роботи: вивчення симплекс методу для знаходження розв’язку задач лінійного програмування . План Короткі теоретичні відомості. Постановка задачі Симплекс метод розв’язаний за допомогою симлекс таблиць з додаванням змінних. Розв’язання за допомогою пакету програм SimplexWin Розв’язання за допомогою власної програми. Хід роботи 1. Короткі теоретичні відомості Симплекс метод - універсальний метод для вирішення лінійної системи рівнянь або нерівностей і лінійного функціоналу. Для приведення системи обмежень нерівностей до канонічного виду, необхідно в системі обмежень виділити одиничний базис. I. Обмеження виду «?» - ресурсні обмеження. Справа знаходиться те що ми використовуємо на виробництві, ліворуч - те що отримуємо. При таких обмеженнях вводять додаткові змінні з коефіцієнтом «+1», що утворюють одиничний базис. У цільову функцію ці змінні увійдуть з коефіцієнтом «0». II. Обмеження виду «=». Часто буває, що незважаючи на те що обмеження мають вигляд рівності, одиничний базис не виділяється або важко виділяється. В цьому випадку вводяться штучні змінні для створення одиничного базису - Yi. В систему обмежень вони входять з коефіцієнтом «1», а в цільову функцію з коефіцієнтом «M», що прагнуть до нескінченності (при Fmin - «+ M», при Fmax - «-M»). III. Обмеження виду «?» - планові обмеження. Додаткові змінні (X), що несуть певний економічний зміст - перевитрата ресурсів або перевиконання плану, перевиробництво, додаються з коефіцієнтом «-1», в цільову функцію - з коефіцієнтом «0». А штучні змінні (Y) як у попередньому випадку. Алгоритм симплекс методу Нехай система приведена до канонічного виду. X1+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 X2+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 (1) X3+ q1,m+1 Xm+1 + …. + q1,m+n Xm+n = h1 ………………………………………………………………. Xm+ qm,m+1 Xm+1 + …. + qm,m+n Xm+n =hm У ній m базисних змінних, k вільних змінних. m + k = n - всього змінних. Fmin = C1X1 + C2X2 + C3X3 + .... + CnXn Всі hi повинні бути більше або дорівнюють нулю, де i = 1,2 ... m. На першому кроці в якості допустимого рішення приймаємо всі Xj = 0 (j = m +1, m +2, ..., m + k). При цьому всі базисні змінні Xi = Hi. Для подальших міркувань обчислень будемо користуватися першою симплекс таблицею. Таблица 1 –Перша симплес таблиця . C Б H C1 C2 … Cm Cm+1 … Cm+k
Перший стовпчик-коефіцієнти в цільової функції при базисних змінних. Другий стовпчик - базисні змінні. Третій стовпчик - вільні члени (hi?0). Самий верхній рядок - коефіцієнти при цільовій функції. Другий верхній рядок - змінні, що входять в цільову функцію і в систему обмежень. Основне поле симплекс методу - система коефіцієнтів з рівняння. Останній рядок - служить для того, щоб відповісти на питання: «оптимальний план чи ні». 2. Постановка задачі Розв’язати задачу лінійного програмування симплекс методом (номер завдання відповідає двом останнім цифрам залікової книжки студента, крім цифр 00 – які відповідають завданню під номером100) Варіант 32 F(x1,x2) = x1 + x2 max ; 3x1 - 2x2 -6, x1+ 2x2 3, 3x1 0, 5 x2 0. 2. Розв’язання без використання пакетів програм.
Cимплекс метод розв’язаний за допомогою сиплекс таблиць З додаванням додаткових змінних . Умова: F(X) = 14x1 + 10x2 7x1 + 5x2?7 7x1 - 5x2?35 x1 - x2?0 Вирішимо пряму задачу лінійного програмування симплексним методом, з використанням симплексного таблиці.Оскільки в правій частині присутні негативні значення, помножимо відповідні рядки на (-1).Визначимо максимальне значення цільової функції F (X) = x1 + x2 при наступних умовах-обмежень.- 3x1 + 2x2 ? 6x1 + 2x2 ? 3Для побудови першого опорного плану систему нерівностей приведемо до системи рівнянь шляхом введення додаткових змінних (перехід до канонічної формі).-3x1 + 2x2 + 1x3 + 0x4 = 61x1 + 2x2 + 0x3-1x4 = 3Введемо штучні змінні x: в 2-м рівність вводимо змінну x5;-3x1 + 2x2 + 1x3 + 0x4 + 0x5 = 61x1 + 2x2 + 0x3-1x4 + 1x5 = 3Для постановки задачі на максимум цільову функцію запишемо так:F (X) = x1 + x2 - Mx5 > maxЗ рівнянь виражаємо штучні змінні: x5 = 3-x1-2x2 + x4які підставимо в цільову функцію:F (X) = (1 +1 M) x1 + (1 +2 M) x2 + (-1M) x4 + (-3M) > maxМатриця коефіцієнтів A = a (ij) цієї системи рівнянь має вигляд: Вирішимо систему рівнянь щодо базисних змінних:x3, x5,Вважаючи, що вільні змінні рівні 0, отримаємо перший опорний план:X1 = (0,0,6,0,3) Базис БП x 1 x 2 x 3 x 4 x 5 x 6 z 1
x3 6 -3 2 1 0 0 0 0
z1 3 1 2 0 -1 0 0 1
x5 3 1 0 0 0 1 0 0
x6 5 0 1 0 0 0 1 0
ИС -3M -M-1 -2M-1 0 M 0 0 0
Переходимо до основного алгоритму симплекс-метода. Ітерація № 0.Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.В якості ведучого виберемо стовпець, відповідний змінної x2, так як це найбільший коефіцієнт за модулем.Обчислимо значення Di по рядках як частка від ділення: bi / ai2і з них виберемо найменше:Отже, 2-ий рядок є провідною.Дозволяє елемент дорівнює (2) і стоїть на перетині провідного стовпця і ведучою рядка Базис B x1 x2 x3 x4 x5 min
x3 6 -3 2 1 0 0 3
x5 3 1 2 0 -1 1 11/2
F(X1) -3M -1-1M -1-2M 0 1M 0 0
Отримуємо нову симплекс-таблицю: Базис B x1 x2 x3 x4 x5
x3 3 -4 0 1 1 -1
x2 11/2 1/2 1 0 -1/2 1/2
F(X1) 11/2 -1/2 0 0 -1/2 1/2+1M
Ітерація № 1.Поточний опорний план неоптимальний, тому що в індексному рядку знаходяться негативні коефіцієнти.В якості ведучого виберемо стовпець, відповідний змінної x4, так як це найбільший коефіцієнт за модулем.Обчислимо значення Di по рядках як частка від ділення: bi / ai4і з них виберемо найменше:Отже, 1-а рядок є провідною.Дозволяє елемент дорівнює (1) і стоїть на перетині провідного стовпця і ведучою рядка. Базис БП x 1 x 2 x 3 x 4 x 5 x 6 z 1
x3 3 -4 0 1 1 0 0 -1
x2 3/2 1/2 1 0 -1/2 0 0 1/2
x5 3 1 0 0 0 1 0 0
x6 7/2 -1/2 0 0 1/2 0 1 -1/2
ИС 3/2 -1/2 0 0 -1/2 0 0 M+1/2
Отримуємо нову симплекс-таблицю: Базис БП x 1 x 2 x 3 x 4 x 5 x 6 z 1
x3 15 0 8 1 -3 0 0 3
x1 3 1 2 0 -1 0 0 1
x5 0 0 -2 0 1 1 0 -1
x6 5 0 1 0 0 0 1 0
ИС 3 0 1 0 -1 0 0 M+1
Базис БП x 1 x 2 x 3 x 4 x 5 x 6 z 1
x3 15 0 2 1 0 3 0 0
x1 3 1 0 0 0 1 0 0
x4 0 0 -2 0 1 1 0 -1
x6 5 0 1 0 0 0 1 0
ИС 3 0 -1 0 0 1 0 M
Остаточний варіант симплекс-таблиці: Базис БП x 1 x 2 x 3 x 4 x 5 x 6 z 1
x3 5 0 0 1 0 3 -2 0
x1 3 1 0 0 0 1 0 0
x4 10 0 0 0 1 1 2 -1
x2 5 0 1 0 0 0 1 0
ИС 8 0 0 0 0 1 1 M
3. Розв’язання з допомогою пакету програм SimplexWin Cимплекс метод з додаванням змінних , розв’язаний за допомогою сиплекс таблиць . Ввід даних : / Крок 1: / Крок 2: / Крок 3: / Крок 4: / Крок 5: / /
4. Розв’язання за допомогою власної програми.
Програма написана мовою С++ Для правильного вирішення система лінійних обмежень повинна бути приведена до канонічного виду. При запуску програми потрібно ввести кількість рівнянь обмежень (rows) і найбільший індекс змінної (cols). Після цього потрібно послідовно ввести коефіцієнти рівнянь (xi) та їх праві частини (b), а також коефіцієнти цільової функції. Якщо який-небудь коефіцієнт відсутній, слід ввести нуль. Для виведення результату потрібно натиснути пробіл. Якщо для вирішення завдання були введені додаткові перемінні або штучні базиси, то їх потрібно виключити з підсумкового відповіді. Лістинг програми main.cpp #include "stdafx.h" #include <iostream> #include <cmath> #include <fstream> #include <sstream> #include <string> #include "user_data.h" #include "simplex.h" using std::cout; using std::endl; void simplex::init() { int i, j; func = 0; sv = new double *[num_l]; for (i = 0; i < num_l; i++) sv[i] = new double [num_v * 2]; for (i = 0; i < num_l; i++) { for (j = 0; j < num_v; j++) sv[i][j] = system[i][j]; for (; j < num_v * 2; j++) if (i + num_v == j) if (way) sv[i][j] = 1; else sv[i][j] = -1; else sv[i][j] = 0; } istr = new double [num_v * 2]; bv = new double *[num_l]; for (i = 0; i < num_l; i++) { bv[i] = new double [2]; bv[i][0] = i + num_v; bv[i][1] = fm[i]; } for (i = 0; i < num_v * 2; i++) if (i < num_v) istr[i] = function[i] * -1; else istr[i] = 0; i_lcol = 0; for (i = 0; i < num_v * 2 - 1; i++) { if (istr[i] < 0) if (fabs(istr[i + 1]) > fabs(istr[i])) i_lcol = i + 1; } th = new double [num_l]; for (i = 0; i < num_l; i++) th[i] = bv[i][1] / sv[i][i_lcol]; i_lrow = 0; for (i = 0; i < num_l - 1; i++) if (th[i] > th[i + 1]) i_lrow = i + 1; alm = sv[i_lrow][i_lcol]; print_result_to_file(0); } bool simplex::plane_is_valid() { int i; bool result = true; if (way) for (i = 0; i < num_v * 2; i++) if (istr[i] < 0) { result = false; break; } if (!way) for (i = 0; i < num_v * 2; i++) if (istr[i] >= 0) { result = false; break; } return result; } bool simplex::function_is_undefined() { int i; for (i = 0; i < num_l; i++) if (th[i] < 0) { return false; } return true; } void simplex::gen_plane() { int i, j, it_num = 0; double A, B; while (!plane_is_valid() && function_is_undefined()) { A = bv[i_lrow][1]; B = istr[i_lcol]; func -= A * B / alm; double *tmp_bv = new double [num_l]; bv [i_lrow][0] = i_lcol; A = bv[i_lrow][1]; for (i = 0; i < num_l; i++) { B = sv[i][i_lcol]; tmp_bv[i] = bv[i_lrow][1]; if (i != i_lrow) tmp_bv[i] = bv[i][1] - A * B / alm; else tmp_bv[i] /= alm; } for (i = 0; i < num_l; i++) bv[i][1] = tmp_bv[i]; double *tmp_istr = istr; B = istr[i_lcol]; for (i = 0; i < num_v * 2; i++) { A = sv[i_lrow][i]; tmp_istr[i] = istr[i] - A * B / alm; } istr = tmp_istr; double **tmp_sv = new double *[num_l]; for (i = 0; i < num_l; i++) tmp_sv[i] = new double [num_v * 2]; for (i = 0; i < num_l; i++) for (j = 0; j < num_v * 2; j++) { tmp_sv[i][j] = sv[i][j]; A = sv[i_lrow][j]; B = sv[i][i_lcol]; if (i == i_lrow) tmp_sv[i][j] /= alm; else tmp_sv[i][j] = sv[i][j] - A * B / alm; } sv = tmp_sv; i_lcol = 0; for (i = 0; i < num_l; i++) th[i] = bv[i][1] / sv[i][i_lcol]; i_lrow = 0; for (i = 0; i < num_l -1; i++) if (th[i] > th[i + 1]) i_lrow = i + 1; alm = sv[i_lrow][i_lcol]; it_num++; print_result_to_file(it_num); } if (!function_is_undefined()) cout << "zZilova funkzija ne obmeshena , dana zadasha nemaje rishenn" << endl; else { cout << "f(x) = " << func << "" << endl; for (i = 0; i < num_l; i++) { cout << "x" << bv[i][0] + 1 << " = " << bv[i][1] << endl; } cout << "Resultati zapisani u table.txt" << endl; } } void simplex::print_result_to_file(int it_num) { int i, j; if (!it_num) { table << "Задана цільова функція:" << endl; std::stringstream f_x; f_x << "f(x) = "; for (i = 0; i < num_v; i++) { if (!i) f_x << function[i] << "x" << i + 1 << " "; else { if (function[i] < 0) f_x << "- " << fabs(function[i]) << "x" << i + 1 << " "; if (function[i] > 0) f_x << "+ " << function[i] << "x" << i + 1 << " "; } } std::string minmax; if (way) minmax = "max"; else minmax = "min"; f_x << "=> " << minmax << "" << endl; table << f_x.str(); table << "І система рівнянь :" << endl; std::stringstream math_sys; std::string math_sign; for (i = 0; i < num_l; i++) { for (j = 0; j < num_v; j++) { if (!j) math_sys << system[i][j] << "x" << j + 1 << " "; else if (system[i][j] == 1) if (!j) math_sys << "x" << j + 1 << " "; else math_sys << "+ x" << j + 1 << " "; else if (system[i][j] == -1) if (!j) math_sys << "-x" << j + 1 << " "; else math_sys << "- x" << j + 1 << " "; else { if (system[i][j] < 0) math_sys << "- " << fabs(system[i][j])<< "x" << j + 1 << " "; else math_sys << "+ " << system[i][j] << "x" << i + 1 << " "; if (!sign[i]) math_sign = "<="; if (sign[i] == 1) math_sign = "="; if (sign[i] == 2) math_sign = ">="; } } math_sys << math_sign << " " << fm[i]; math_sys << endl; } std::string min_or_max; if (way) min_or_max = "максимум"; else min_or_max = "мінімум"; table << math_sys.str() << endl; table << "Вирішимо дану задачу на " << min_or_max << " методом симплексних таблиц.Побудуємо перший опорний план (таблицю):" << endl; } for (i = 0; i < num_l; i++) { table << "x" << bv[i][0] + 1 << " " << bv[i][1] << " "; for (j = 0; j < num_v * 2; j++) table << sv[i][j] << " "; if (!plane_is_valid()) table << th[i]; table << "" << endl; } table << "f(x) " << func << " "; for (i = 0; i < num_v * 2; i++) table << istr[i] << " "; table << ""; if (plane_is_valid()) { if (plane_is_valid() && function_is_undefined()) table << "Danij plan e optimalnim i ne potrrebuje pokrashennja. Rishennja najdeno." << endl; std::ofstream outfile ("table.txt"); outfile << table.str(); } else { std::string ln_or_gn; if (way) ln_or_gn = "nehativne"; else ln_or_gn = "pozetivne"; std::stringstream num_of_plane; if (!it_num) num_of_plane << "1 opornij plan"; else num_of_plane << it_num + 1 << "-j plan takosh"; table << "" << num_of_plane.str() << " ne javlajetsja optimalnim , oskilki v indeksnomu rjadku znahodjantsja " << ln_or_gn << " elementi.Yoho neobhidno pokrash4iti." << endl; } } int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "Russian"); simplex *ud = new simplex; ud->get_data_from_user(); ud->init(); ud->gen_plane(); return 0; } Лістинг програми user_data.cpp #include "stdafx.h" #include <iostream> #include <string> #include <cstdlib> #include "user_data.h" #include <cmath> #include <fstream> #include <sstream> #include "simplex.h" using namespace std;
void error(int err_no) { switch(err_no) { case 0: cout << "Vi vveli nekorektne znashennja." << endl; break; case 1: cout << "Vi ne moshete zadati menshe 2 rivnjan." << endl; break; case 2: cout << "Vi ne moshete zadati bilshe 500 rivnjan." << endl; break; case 3: cout << "Vi ne moshete zadati menshe 2 zminnih." << endl; break; case 4: cout << "Vi ne moshete zadati bilshe 500 rivnjan." << 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 << "Vvedit kilkist rivnjan sistemi: "; 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];
for (i = 0; i < num_v; i++) { do { cout << " Vvedit koephizienti zilovoji funkziji pri 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 << "Vvedit naprjamlenna zilovoji funkziji ( 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 << "Zapovnit sistemu rivnjan" << endl;
for (i = 0; i < num_l; i++) { cout << "Zapovnit " << i + 1 << "-е rivnjannja." << endl; for (j = 0; j < num_v; j++) { do { cout << "Vvedit koephizient pri 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 << "Vvedit znak pry " << i + 1 << "-mu rivnjanni ( <=, =, >= ) : "; 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 << "Vvedit znashennja vilnoho chlena (Bi) pri " << i + 1 << "-mu rivnjanni: "; getline(cin, fr_m); if (atof(fr_m.c_str()) == 0) error(0); else validator = true; } while (!validator);
class simplex : public user_data { public: void init(); void gen_plane(); bool plane_is_valid(); bool function_is_undefined(); void print_result_to_file(int it_num); private: double func; double **bv; double **sv; double *istr; double *th; double alm; int i_lrow; int i_lcol; std::stringstream table; };
#endif /* _SIMPLEX_H_ */ Лістинг хідер файлу user_data.h #ifndef _USER_DATA_H_ #define _USER_DATA_H_ #include "stdafx.h" class user_data { public: void get_data_from_user(); void user_data_is_valid(); protected: double *function; double *fm; double **system; int *sign; int num_v; int num_l; bool way; };
#endif /* _USER_DATA_H_ */ Висновок: на цій лабораторній роботі я набув навиків розв’язку задачі лінійного програмування симплекс-методом.
Міністерство освіти та науки, молоді та спорту України НУ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра АСУ / Лабораторна робота №3-4 з дисципліни “Математичні методи дослідження операцій” Виконав: студент групи КН-22 Саврук Сергій Прийняв: старший викладач Балич Б. І. Львів – 2012
