vm1

xj ¸ 0; j 2 f1; : : : ; 5g:

J Маємо n = 5, m = 3. Оскiльки n¡m = 5¡3 = 2, то задачу можна розв’язати графiчно. Для цього спочатку запишемо систему обмежень у базиснiй формi, скориставшись методом Жордана-Гаусса

Отже, система обмежень набула вигляду

Запишемо задачу, виразивши цiльову функцiю та обмеження через вiльнi змiннi x4 i x5. З системи обмежень випливає, що

8

< x1 = 3 ¡ 2x5;

:x2 = 1 ¡ 2x4 + 2x5; x3 = 1 + x4 ¡ x5:

Пiдставивши цi вирази в цiльову функцiю, дiстанемо

f~ = 3 ¡ 2x5 + 2(1 + x4 ¡ x5) + x5 = 2x4 ¡ 3x5 + 5:

241

Якщо в системi обмежень вiдкинути базиснi змiннi x1 ¸ 0, x2 ¸ 0 i x3 ¸ 0, то одержимо таку задачу лiнiйного програмування:

f~ = 2x4 ¡ 3x5 + 5 ! min;

8

< 2x5 · 3;

:2x4 ¡ 2x5 · 1; ¡x4 + x5 · 1;

§4. Симплексний метод розв’язування задач лiнiйного програмування

Цей метод є унiверсальним, оскiльки дозволяє розв’язувати практично будь-яку задачу лiнiйного програмування, записану в канонiчному виглядi.

Iдея симплексного методу полягає в тому, що початковий опорний план послiдовно покращується i за певну кiлькiсть етапiв (iтерацiй) доводиться до оптимального. Значення цiльової функцiї при цьому переходi для задач на максимум не спадає, а для задач на мiнiмум не зростає. Напрямок переходу вiд одного опорного розв’язку до iншого вибирається згiдно з критерiєм оптимальностi цiльової функцiї задачi. При цьому використовується той факт, що коли задача лiнiйного програмування має оптимальний розв’язок, то вiн вiдповiдає принаймнi однiй кутовiй точцi многогранника розв’язкiв, тобто допустимому опорному плану.

4.1. Алгоритм симплексного методу. Розглянемо задачу лiнiйного програмування, записану в базиснiй формi

f = c1x1 + c2x2 + : : : + cnxn ! max;

Умови такої задачi зручно записувати у виглядi симплексної таблицi

245

Над позначеннями векторiв A1, : : :, An записуються коефiцiєнти цiльової функцiї. У стовпчику Б (базис) записуємо одиничнi базиснi вектори; у стовпчику Cб – коефiцiєнти цiльової функцiї, якi вiдповiдають векторам базису; у стовпчику A0 – значення базисних змiнних; у стовпчиках A1, : : :, An – коефiцiєнти aij матрицi умов.

При заповненнi (m + 1)-го рядка користуємося тим, що f0 = CбA0 = c1b1 + c2b2 + : : : + cmbm;

fj = CбAj = c1a1j + c2a2j + : : : + cmamj; ¢j = fj ¡ cj; j 2 f1; : : : ; ng:

Очевидно, що коли цiльова функцiя мiстить лише вiльнi змiннi, то елементи (m + 1)-го рядка визначається так: f0 = 0, ¢j = 0 для базисних змiнних x1, : : :, xm i ¢j = ¡cj для вiльних

змiнних xj+1, : : :, xn.

Опишемо алгоритм симплексного методу по кроках.

1. Переглядаємо знаки всiх коефiцiєнтiв ¢j оцiночного (m + 1)-го рядка. Якщо всi ¢j ¸ 0, то задача розв’язана: допустимий базисний розв’язок X0 = (b1; : : : ; bm; 0; : : : ; 0) оптималь-

ний, fmax = f0. Якщо не всi ¢j ¸ 0, то переходимо до кроку 2.

2. Серед значень ¢j < 0 вибираємо найбiльше за абсолютною величиною, i стовпчик, який йому вiдповiдає, беремо за провiдний. Нехай це буде стовпчик As. Якщо в провiдному стовпчику всi елементи ais · 0, i 2 f1; : : : ; mg, то задача

246

(1) розв’язку не має, бо цiльова функцiя необмежена, тобто

fmax = +1. Якщо ж серед ais, i 2 f1; : : : ; mg є додатнi, то переходимо до кроку 3.

ваємо рядок, де воно досягається, провiдним. Нехай це буде рядок з номером r. Елемент ars, який знаходиться на перетинi провiдного стовпчика i провiдного рядка беремо за провiдний (розв’язувальний).

4. Заповнюємо наступну симплексну таблицю. Для цього переписуємо провiдний рядок, подiливши його на провiдний елемент, у стовпчику Б (базис) замiнюємо вектор Ar на As, а в стовпчику Cб – cr на cs. Решту коефiцiєнтiв таблицi знаходимо за методом Жордана-Гаусса (за правилом прямокутника). Одержаний новий опорний план перевiряємо на оптимальнiсть, тобто переходимо до кроку 1.

Зауваження 1. Якщо на кроцi 2 є декiлька найбiльших за абсолютною величиною оцiнок ¢j, то в базис включають

той вектор, якому вiдповiдає max cj. Точнiшим є таке пра-

j

вило: якщо не виконується умова оптимальностi ¢j ¸ 0, j 2 f1; : : : ; ng, то в базис включають той вектор, якому вiд-

повiдає min µ0j¢j, де мiнiмум береться по тих j, для яких

j

¢j < 0; якщо ж мiнiмальних оцiнок декiлька, то в базис вклю-

чають вектор, якому вiдповiдає max cj.

j

Зауваження 2. Якщо в задачi (1) f ! min, то умовою оптимальностi плану є ¢j · 0, j 2 f1; : : : ; ng. Якщо ж умова оптимальностi не виконується, то в базис включають вектор, якому вiдповiдає найбiльше ¢j. У випадку, коли таких значень

є декiлька, то включають той вектор, якому вiдповiдає min cj.

j

Зауваження 3. Якщо в останнiй симплекснiй таблицi виконується умова оптимальностi плану, але число тих ¢j, якi дорiвнюють нулю, бiльше за число обмежень m, то це означає,

247

що оптимальний план не єдиний. Для знаходження другого оптимального плану, треба перейти до наступної симплексної таблицi, взявши за провiдний той з небазисних стовпчикiв, якому вiдповiдає ¢j = 0, а провiдний рядок вибравши за симплекс-

ним вiдношенням.

Приклад 1. Пiдприємство на основi трьох типiв ресурсiв S1, S2 i S3 може органiзувати виробництво певної продукцiї двома рiзними

способами P1 i P2.

Запаси ресурсiв i витрати кожного типу ресурсiв при кожному способi виробництва визначено таблицею

При першому способi виробництва пiдприємство випускає за один мiсяць 3 тис. виробiв, при другому – 4 тис. виробiв.

Скiльки мiсяцiв повинне працювати пiдприємство кожним з цих способiв, щоб при наявних ресурсах забезпечити максимальний випуск продукцiї?

J Складемо математичну модель задачi. Нехай x1 – час (в мiсяцях) роботи пiдприємства способом P1, а x2 – час (в мiсяцях) роботи пiдприємства способом P2. Тодi математична модель має вигляд:

f = 3x1 + 4x2 ! max;

8

< x1 + 2x2 · 4;

:x1 + x2 · 3;

2x1 + x2 · 8;

x1 ¸ 0; x2 ¸ 0:

Для того щоб розв’язати цю задачу симплексним методом, зведемо її до канонiчного базисного вигляду, ввiвши додатковi (балансуючi) змiннi x3 ¸ 0, x4 ¸ 0 i x5 ¸ 0:

f = 3x1 + 4x2 ! max;

248

xj ¸ 0; j 2 f1; : : : ; 5g:

Розв’язуватимемо цю задачу за допомогою симплексних таблиць

У першiй симплекснiй таблицi умова оптимальностi не виконується, бо ¢1 = ¡3 < 0, ¢2 = ¡4 < 0. Оскiльки найбiльшим за абсолютною величиною є ¢2, то до базису треба ввести вектор A2 i вивести A3, бо

ної таблицi, зробивши перерахунок елементiв таблицi за методом Жордана-Гаусса.

У другiй симлекснiй таблицi є вiд’ємне ¢1 = ¡1. Стовпчик, який йому вiдповiдає, беремо за провiдний. Провiдний рядок виберемо за

Переходимо до третьої симплексної таблицi, взявши за провiдний елемент 12 .

249

Утретiй симплекснiй таблицi умова оптимальностi виконується,

аце означає, що задача розв’язана. Оптимальним розв’язком є X¤ = (2; 1; 0), fmax = 10.

Отже, за першим способом пiдприємство повинно працювати два

мiсяцi, а за другим – один мiсяць. При цьому максимальний випуск

продукцiї становитиме 10 тис. од.I Приклад 2. Розв’язати задачу

f = 2x2 ¡ 4x3 + 2x5 ! min;

½x1 + 3x2 ¡ x3 + 2x5 = 7; ¡2x2 + 4x3 + x4 = 12;

xj ¸ 0; j 2 f1; : : : ; 5g:

J Оскiльки задача записана в канонiчнiй базиснiй формi, то розв’язуватимемо її за допомогою симплексного методу

У першiй симплекснiй таблицi умова оптимальностi не виконується, бо ¢3 = 4 > 0. Стовпчик A3 беремо за провiдний. Оче-

видно, що провiдним елементом є 4 . Складемо другу симплексну таблицю, замiнивши в базисi вектор A4 на вектор A3, i зробивши перерахунок елементiв таблицi за методом Жордана-Гаусса. У другiй симплекснiй таблицi умова оптимальностi виконується, бо всi ¢j · 0, j 2 f1; : : : ; 5g. Це означає, що задача розв’язана i X1¤ = (10; 0; 3; 0; 0), fmin = ¡12. Оскiльки нульових ¢j бiльше нiж обмежень задачi, то задача має безлiч розв’язкiв. Для того щоб знайти другий оптимальний план, перейдемо до третьої симплексної таблицi, взявши за провiдний стовпчик A2, бо йому вiдповiдає ¢2 = 0, але вiн не є базис-

250