Симплексний метод рішення задач лінійного програмування

Існує багато методів які дозволяють знайти оптимальне рішення в задачах лінійного програмування (ЗЛП). Одним з таких методів, який дозволяє ефективно вирішувати такі задачі є симплекс метод. Ідея цього методу складається з переходів від одного розв’язку x_k до другого x_k+1, для яких виконується умова f(x_k) > f(x_k+1). Для переходу від одного розв’язку до другого використовуються симлексні таблиці. Кожній симплексній таблиці відповідає один з розв’язків задачі. По змісту симплексної таблиці можна визначити, чі оптимальне рішення знайдено, або що задача рішень не має.

Послідовність рішення задачі лінійного програмування за допомогою симплексного методу. Рішення задачі лінійного програмування виконується в наступній послідовності:

Крок 1. Здійснюється перевірка економіко-математичної моделі на відповідність канонічному виду. Якщо модель не відповідає вимогам, то виконується приведення моделі до канонічного виду.

Крок 2. Для таблиці обмежень будується матриця коефіцієнтів та визначається базіс. Якщо треба, то послідовно у кожній строці визначається базисна змінна і за методом Гауса проводяться необхідні перетворення. Кожна базисна зміна має бути присутньою тільки в одній строці обмежень. Нехай X_k , X_k+1, …, X_k+j - є базіс, тогда X_k= B_1, X_k+1= B_{2, …,} X_k+j= B_m – є базисний розв’язок. Подальша задача полягає в тому, щоб від початкового допустимого базисного розв’язку перейти до іншого базисного розв’язку, при якому значення лінійної форми зменшиться. Лінійна форма при початковому базисному розв’язку дорівнює нулю. Для поліпшення результатів розв’язку на кожному кроці треба перевести одну змінну з неосновних в основні і одну змінну з основних в неосновні, тобто дві змінні міняються місцями.

Крок 3. Будуємо симлекс таблицю для лінійної моделі наступного виду:

Таблиця 1.5.1

В таблиці k, k+1, k+j < n, (X_k , X_k+1, …, X_k+j ) – початковий базіс рішення.

Крок 4. Серед коефіцієтів C_i (i = 1,n) обираємо C_i < 0 той, що має найменше значення (найбільше за абсолютним значенням). Стовпець з обраним C_i визначає змінну, яку треба перенести до базису. Щоб обрати змінну, яку треба виключити з бази розраховуємо оценку, яка визнається як B_i /a_ij. Виключати треба змінну, яка буде мати найменшу оцінку.

Крок 5. Після визначення змінної - притендента на перенесення в базис, використовуючі метод Гауса треба провести відповідні розрахунки в обмеженнях. Для цього строку обмежень з визначеною зміною пділимо на коефіцієнт при цей зміной. Потім знаходимо чому дорівнює ця змінна через інші змінні і підставляємо її значення в інші строки обмеження і лінейну форму.

Крок 6. За результатми проведених змін оновлюємо симплекс таблицю. Якщо серед коефіцієтів C_i (i = 1,n) є C_i < 0, то переходимо до кроку 4. Якщо всі C_i ³ 0, то знайдено оптимальне рішення.

Приклад 1. В прикладі 1 розділа 1.1 на підставі умов завдання побудована економіко-математична модель для пошуку рішення. Ця модель вимагає знайти максимальне значення цільової функції

F = 10x₁ + 12 x₂ ® max

при обмеженнях на ресурси виробництва по металу, склу та трудовим ресурсам відповідно до технологічних норм,

4x₁ + 5x₂ £ 300

2x₁ + x₂ £ 100

2x₁ + 3x₂ £ 160

x₁ ³ 0; x₂ ³ 0

Приводимо модель до канонічного виду

F = - 10x₁ - 12 x₂ ® min

при обмеженнях

4x₁ + 5x₂ + x₃ = 300

2x₁ + x₂ + x₄ = 100

2x₁ + 3x₂ + x₅ = 160

x₁ ³ 0; x₂ ³ 0; x₃ ³ 0; x₄ ³ 0; x₅ ³ 0

Будуємо сімплекс таблицю і визначаємо базіс. Так як додаткові змінні x₃, x₄, x₅ мають кофецієнт одиницю та присутні тільке один раз в кожній строці обмежень, то ці змінні можуть створювати базіс.

Таблиця 1.5.2

Аналізуємо остнню строку таблиці та визначаємо стовпець зі змінною, яку треба перенести до базису. В нашому випадку найменше значення “ -12 ”, що відповідає знмінній x₂.

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

300 / 5; 100 / 1; 160 / 3 або 60; 100; 53,33333

Найменше значення знаходиться в строці зі змінною x₅. Таким чином треба провести перетворення моделі за методом Гауса і перенести в базіс x₂ замість x₅. Обмеження, у якому визначено x₂ і x₅ поділимо на 3 і отримуємо (2/3)x₁ + x₂ + (1/3)x₅ = 160/3. Вирішуємо рівняння відносно x₂