Главная | Обратная связь | Поможем написать вашу работу!

Знаходження розв’язку задачі лінійного програмування

Розв’язок будь-якої задачі лінійного програмування можна знайти або симплексним методом, або методом штучного базису. Перш ніж застосовувати один із зазначених методів, потрібно записати вихідну задачу у формі основної задачі лінійного програмування, якщо вона не має такої форми запису.

1. Симплексний метод. Симплексний метод розв’язку задачі лінійного програмування заснований на переході від одного опорного плану до іншого, при якому значення цільової функції зростає (за умови, що дана задача має оптимальний план і кожний її опорний план є не виродженим). Зазначений перехід можливий, якщо відомо який-небудь вихідний опорний план. Розглянемо задачу, для якої цей план можна безпосередньо записати.

Нехай потрібно знайти максимальне значення функції

F=c₁x₁ + c₂x₂+... + c_nx_n

при умовах

x_j ≥ 0 (j =

Тут a_ij, b_i, і c_i (i = ; j = – задані постійні числа (т < п і b_i > 0).

Векторна форма даної задачі має такий вигляд: знайти максимум функції

при умовах

х₁Р₁+х₂Р₂+...+х_тР_т+...+х_пР_п=Р₀, (23)

x_j ≥ 0 (j = (24)

де

Так як

b_iP₁ + b₂P₂ +... + b_mP_m=Р₀,

то по визначенню опорного плану Х=(b₁; b₂;...; b_т; 0;...; 0) є опорним планом даної задачі (останні п – т компонентів вектора X дорівнюють нулю). Цей план визначається системою одиничних векторів P₁, P₂,...; P_т,які утворять базис т -мірного простору. Тому кожний з векторів P₁, P₂,...; P_n,а також вектор Р₀ можуть бути представлені у вигляді лінійної комбінації векторів даного базису. Нехай

Покладемо

Так як вектори P₁, P₂,...; P_т – одиничні, то х_ij = a_ij і а

Теорема 1.5 (ознака оптимальності опорного плану). Опорний план Х*=(x₁*; x₂*;...; x_т*; 0;...; 0) задачі (22)-(24) є оптимальним, якщо Δ _j ≥ 0 для будь-якого j (j = ).

Теорема 1.6. Якщо Δ _k < 0 для деякого j=k серед і чисел а_ik (i = ) немає додатних (а_ik ≤ 0), то цільова функція (22) задачі (22)-(24) не обмежена на множині її планів.

Теорема 1.7. Якщо опорний план X задачі (22)-(24) не вироджений і Δ _k < 0, але серед чисел а_ik є додатні (не всі а_ik ≤ 0), то існує опорний план X′ такий, що F (X′)> F(Х).

Сформульовані теореми дозволяють перевірити, чи є знайдений опорний план оптимальним, і виявити доцільність переходу до нового опорного плану.

Дослідження опорного плану на оптимальність, а також подальший обчислювальний процес зручніше вести, якщо умови задачі s первісні дані, отримані після визначення вихідного опорного плану, записати так, як показано в табл. 1.3.

У стовпці С_б цієї таблиці записують коефіцієнти при невідомих цільової функції, що мають ті ж індекси, що і вектори даного базису.

У стовпці Р₀ записують додатні компоненти вихідного опорного плану, у ньому ж у результаті обчислень одержують додатні компоненти оптимального плану. Стовпці векторів Р_j, являють собою коефіцієнти розкладання цих векторів по векторам даного базису.

У табл. 1.3 перші т рядків визначаються вихідними даними задачі, а показники (т +1) - горядка обчислюють. У цьому рядку в стовпці вектора Р₀ записують значення цільової функції, які вона приймає при даному опорному плані, а в стовпці вектора Р_j; – значення Δ _j = z_j – c_j.

Значення z_j знаходиться як скалярний добуток вектора P_j (j = )на вектор С_б= (c₁, c₂,...; c_т):

Значення F₀ дорівнює скалярному добутку вектора Р₀ на вектор С_б:

Після заповнення табл. 1.3 вихідний опорний план перевіряють на оптимальність. Для цього переглядають елементи (т +1)-го рядка таблиці. У результаті може мати місце один з наступних трьох випадків:

1) Δ _j ≥ 0 для j = т +1, т +2,..., n (при (j = ), z_j = c_j). Тому в цьому випадку числа Δ _j ≥ 0 для всіх j від 1 до n;

2) Δ _j < 0 для деякого j, і всі відповідні цьому індексу величини а_ij ≤ 0 (i = );

3) Δ _j < 0 для деяких індексів j, і для кожного такого j принаймні одне із чисел а_ij додатне.

У першому випадку на підставі ознаки оптимальності вихідний опорний план є оптимальним. У другому випадку цільова функція не обмежена зверху на множині планів, а в третьому випадку можна перейти від вихідного плану до нового опорного плану, при якому значення цільової функції збільшиться. Цей перехід від одного опорного плану до іншого здійснюється виключенням з вихідного базису якого-небудь із векторів і введенням у нього нового вектора. У якості вектора, що вводиться в базис, можна взяти будь-який з векторів Р_j, щомає індекс j ’, для якого Δ _j < 0. Нехай, наприклад, Δ _k < 0 і вирішено ввести в базис вектор Р_k.

Для визначення вектора, що підлягає виключенню з базису, знаходять тіп b_i /а_ik) для всіх а_ik > 0. Нехай цей мінімум досягається при i = r. Тоді з базису виключають вектор Р_r, а число а_rk називають розв’язним елементом.

Стовпець і рядок, на перетинанні яких перебуває розв’язний елемент, називають направляючими.

Після виділення направляючого рядка і направляючого стовпця знаходять новий опорний план і коефіцієнти розкладання векторів Р_j, через вектори нового базису, що відповідає новому опорному плану. Це легко реалізувати, якщо скористатися методом Жордана-Гаусса. При цьому можна показати, що додатні компоненти нового опорного плану обчислюються за формулами

а коефіцієнти розкладання векторів Р_j через вектори нового базису, що відповідає новому опорному плану, – за формулами

Після обчислення b′_i і a′_ij відповідно за формулами (25) і (26) їх значення заносять у табл. 1.4. Елементи (т +1)-го рядка цієї таблиці можуть бути обчислені за формулами

або на підставі їхнього визначення.

Наявність двох способів знаходження елементів (т +1)-го рядка дозволяє здійснювати контроль правильності проведених обчислень.

З формули (27) випливає, що при переході від одного опорного плану до іншого найбільш доцільно ввести в базис вектор Р_j, щомає індекс j, при якому максимальним по абсолютній величині є число (b_r / а_rj) Δ _j (Δ _j < 0, Δ _j > 0). Однак з метою спрощення обчислювального процесу надалі будемо вектор, що вводиться в базис, визначати, виходячи з максимальної абсолютної величини від’ємних чисел Δ _j. Якщо ж таких чисел декілька, то в базис будемо вводити вектор, що має такий же індекс, як і максимальне із чисел c_j що визначаються даними числами Δ _j (Δ _j < 0).

Отже, перехід від одного опорного плану до іншого зводиться до переходу від одної симплекс-таблиці до іншої. Елементи нової симплекс-таблиці можна обчислити як за допомогою рекурентних формул (25)-(28), так і за правилами, що безпосередньо випливають з них. Ці правила полягають у наступному.

У стовпцях векторів, що входять у базис, на перетині рядків і стовпців однойменних векторів проставляються одиниці, а всі інші елементи даних стовпців приймають рівними нулю.

Елементи векторів Р_о і Р_j у рядку нової симплекс-таблиці, у якій записаний вектор, що вводиться в базис, одержують із елементів цього ж рядка вихідної таблиці діленням їх на величину розв’язного елемента. У стовпці С_б у рядку вектора, що вводиться, проставляють величину c_k, де k – індекс вектора, що вводиться.

Інші елементи стовпців вектора Р₀ і Р_j нової симплекс-таблиці обчислюють за правилом трикутника. Для обчислення якого-небудь із цих елементів знаходять три числа:

1) число, що стоїть у вихідній симплекс-таблиці на місці шуканого елемента нової симплекс-таблиці;

2) число, що стоїть у вихідній симплекс-таблиці на перетині рядка, у якому перебуває шуканий елемент нової симплекс-таблиці, і стовпця, що відповідає вектору, що вводиться в базис;

3) число, що стоїть в новій симплекс-таблиці на перетині стовпця, у якому стоїть шуканий елемент, і рядка вектора, що заново вводиться в базис (як відзначено вище, цей рядок отримується з рядка вихідної симплекс-таблиці діленням її елементів на розв’язний елемент).

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

Після заповнення нової симплекс-таблиці переглядають елементи (т +1)-го рядка. Якщо всі z′_j – c_j ≥ 0, то новий опорний план є оптимальним. Якщо ж серед зазначених чисел є від’ємні, то, використовуючи описану вище послідовність дій, знаходять новий опорний план. Цей процес продовжують доти, поки або не одержують оптимальний план задачі, або не встановлюють її нерозв’язність.

При знаходженні розв’язок задачі лінійного програмування ми припускали, що ця задача має опорні плани і кожний такий план є не виродженим. Якщо ж задача має вироджені опорні плани, то на одній з ітерацій одна або декілька змінних опорного плану можуть виявитися рівними нулю. Таким чином, при переході від одного опорного плану до іншого значення функції може залишитися попереднім. Більше того, можливий випадок, коли функція зберігає своє значення протягом декількох ітерацій, а також можливе повернення до первісного базису. В останньому випадку звичайно говорять, що відбулося зациклення. Однак при рішенні практичних задач цей випадок зустрічається дуже рідко, тому ми на ньому зупинятися не будемо.

Отже, знаходження оптимального плану симплексним методом включає наступні етапи:

1. Знаходять опорний план.

2. Складають симплекс-таблицю.

3. З’ясовують, чи є хоча б одне від’ємне число Δ _j. Якщо ні, то знайдений опорний план оптимальний. Якщо ж серед чисел Δ _j є від’ємні, то або встановлюють нерозв’язність задачі, або переходять до нового опорного плану.

4. Знаходять направляючі стовпець і рядок. Направляючий стовпець визначається найбільшим по абсолютній величині від’ємним числом Δ _j, а направляючий рядок – мінімальним з відношень компонентів стовпця вектора P₀ до додатних компонентів направляючого стовпця.

5. За формулами (25)-(28) визначають додатні компоненти нового опорного плану, коефіцієнти розкладання векторів P_j по векторам нового базису і числа F′₀, Δ′ _j. Всі ці числа записуються в новій симплекс-таблиці.

6. Перевіряють знайдений опорний план на оптимальність. Якщо план не оптимальний і необхідно перейти до нового опорного плану, то повертаються до етапу 4, а у випадку одержання оптимального плану або встановлення нерозв’язності процес розв’язок задачі закінчують.

1.41. Для виготовлення різних виробів А, В і С підприємство використовує три різних види сировини. Норми витрати сировини на виробництво одного виробу кожного виду, ціна одного виробу А, В і С, а також загальна кількість сировини кожного виду, що може бути використана підприємством, наведені в табл. 1.5.

Таблиця 1.5

Вид сировини	Норми витрат сировини на один виріб (кг)	Загальна кількість сировини (кг)
А	В	С
I II III
Ціна одного виробу (грн)

Вироби А, В і С можуть вироблятися в будь-яких співвідношеннях (збут забезпечений), але виробництво обмежене виділеною підприємству сировиною кожного виду.

Скласти план виробництва виробів, при якому загальна вартість всієї виготовленої підприємством продукції є максимальною.

Розв’язок. Складемо математичну модель задачі. Шуканий випуск виробів А позначимо через х₁, виробів В – через х₂, виробів С – через х₃. Оскільки є обмеження на виділений підприємству фонд сировини кожного виду, змінні х₁, х₂, х₃ повинні задовольняти наступній системі нерівностей:

Загальна вартість виробленої підприємством продукції за умови випуску х₁ виробів А, х₂ виробів В і х₃ виробів С становить

F= 9 x₁ +10 x₂ +16 x₃ (30)

По своєму економічному змісту змінні х₁, х₂ і х₃ можуть приймати лише невід’ємні значення:

x₁, x₂, x₃ ≥ 0 (31)

Таким чином, приходимо до наступної математичної задачі: серед всіх невід’ємних розв’язків системи нерівностей (29) потрібно знайти таке, при якому функція (30) приймає максимальне значення.

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

Ці додаткові змінні за економічним змістом означають не використовувану при даному плані виробництва кількість сировини того або іншого виду. Наприклад, x₄ – це не використовувана кількість сировини I виду.

Перетворену систему рівнянь запишемо у векторній формі:

х₁Р₁+х₂Р₂+х₃Р₃+х₄Р₄+х₅Р₅+х₆Р₆=Р₀

де

;

Оскільки серед векторів Р₁, Р₂, Р₃, Р₄, Р₅, Р₆ є три одиничних вектори, для даної задачі можна безпосередньо записати опорний план. Таким є план Х= (0; 0; 0; 360; 192; 180), визначений системою тривимірних одиничних векторів Р₄, Р₅, Р₆,які утворять базис тривимірного векторного простору.

Складаємо симплексну таблицю для I ітерації (табл. 1.6), підраховуємо значення F₀, z_j – c_j,і перевіряємо вихідний опорний план на оптимальність:

F₀ =(C, Р₀)=0; z₁ =(C, Р₁)=0; z₂ =(C, Р₂)=0; z₃= (C, Р₃)=0;

z₁ – c₁ =0 – 9= –9; z₂ – c₂ =0 – 10= –10; z₃ – c₃ = –16.

Для векторів базису z_j – c_j = 0.

Таблиця 1.6

i	Базис	C₆	P₀
P₁	P₂	P₃	P₄	P₅	P₆
	P₄ P₅ P₆			–9	–10	–16

Як видно з табл. 1.6, значення всіх основних змінних х₁, х₂, х₃ дорівнюють нулю, а додаткові змінні приймають свої значення відповідно до обмежень задачі. Ці значення змінних відповідають такому «плану», при якому нічого не виробляється, сировина не використовується і значення цільової функції дорівнює нулю (тобто вартість виробленої продукції відсутня). Цей план, звичайно, не є оптимальним.

Це видно і з 4-го рядка табл. 1.6, тому що в ній є три від’ємних числа: z₁ – c₁= – 9, z₂ – c₂ = –10 і z₃ – c₃ = –16. Від’ємні числа не тільки свідчать про можливість збільшення загальної вартості виробленої продукції, але і показують, на скільки збільшиться ця сума при введенні в план одиниці того або іншого виду продукції.

Так, число –9 означає, що при включенні в план виробництва одного виробу А забезпечується збільшення випуску продукції на 9 грн. Якщо включити в план виробництва по одному виробі В і С, то загальна вартість виготовленої продукції зросте відповідно на 10 і 16 грн. Тому з економічної точки зору найбільш доцільним є включення в план виробництва виробів С. Це ж необхідно зробити і на підставі формальної ознаки симплексного методу, оскільки максимальне по абсолютній величині від’ємне число Δ _j стоїть в 4-му рядку стовпця вектора Р₃ Отже, у базис уведемо вектор Р₃. Визначаємо вектор, що підлягає виключенню з базису. Для цього знаходимо θ₀= тіп (b_i / а_i3) для а_i3 > 0, тобто θ₀= min (360/12; 192/8; 180/3)=192/8.

Знайшовши число 192/8=24, ми тим самим з економічної точки зору визначили, яку кількість виробів С підприємство може виготовляти з урахуванням норм витрати й наявних об’ємів сировини кожного виду. Так як сировини даного виду відповідно є 360, 192 і 180 кг, а на один виріб С потрібно затратити сировини кожного виду відповідно 12, 8 і 3 кг, то максимальне число виробів С, що може бути виготовлено підприємством, дорівнює тіп (360/12; 192/8; 180/3)=192/8=24, тобто обмежуючим фактором для виробництва виробів С є наявний об’єм сировини II виду. З урахуванням його наявності підприємство може виготовити 24 вироби С. При цьому сировина II виду буде повністю використана.

Отже, вектор Р₅ підлягає виключенню з базису. Стовпець вектора Р₃ і 2-ий рядок є направляючими. Складемо таблицю для II ітерації (табл. 1.7).

Таблиця 1.7

i	Базис	C₆	P₀
P₁	P₂	P₃	P₄	P₅	P₆
	P₄ P₅ P₆			3/4 11/4	1/2 3/2 –2	–3/2 1/8 –3/8

Спочатку заповнюємо рядок вектора, заново введеного в базис, тобто рядок, номер якого збігається з номером направляючого рядка. Тут направляючим є 2-ий рядок. Елементи цього рядка табл. 1.7 виходять із відповідних елементів табл. 1.6 діленням їх на розв’язний елемент (тобто на 8). При цьому в стовпці С_б записуємо коефіцієнт С₃ =16, що стоїть в стовпці вектора Р₃, що вводиться вбазис. Потім заповнюємо елементи стовпців для векторів, що входять у новий базис. У цих стовпцях на перетині рядків і стовпців однойменних векторів проставляємо одиниці, а всі інші елементи приймаємо рівними нулю.

Для визначення інших елементів табл. 1.7 застосовуємо правило трикутника. Ці елементи можуть бути обчислені і безпосередньо по рекурентним формулам.

Обчислимо елементи табл. 1.7, що стоять у стовпці вектора Р₀. Перший з них перебуває в 1-у рядку цього стовпця. Для його обчислення знаходимо три числа:

1) число, що стоїть в табл. 1.6 на перетині стовпця вектора Р₀ і 1-го рядка (360);

2) число, що стоїть в табл. 1.6 на перетині стовпця вектора Р₃ і 1-го рядка (12);

3) число, що стоїть в табл. 1.7 на перетині стовпця вектора Р₀ і 2-го рядка (24).

Віднімаючи від першого числа добуток двох інших, знаходимо шуканий елемент: 360–12·24 = 72; записуємо його в 1-у рядку стовпця вектора Р₀ табл. 1.7.

Другий елемент стовпця вектора Р₀ табл. 1.7 був уже обчислений раніше. Для обчислення третього елемента стовпця вектора Р₀ також знаходимо три числа. Перше з них (180) перебуває на перетині 3-го рядка і стовпця вектора Р₀ табл. 1.6, друге (3) – на перетині 3-го рядка і стовпця вектора Р₃ табл. 1.6, третє (24) – на перетині 2-го рядка і стовпця вектора Р₀ табл. 1.8. Отже, зазначений елемент є 180–24·3=108. Число 108 записуємо в 3-у рядку стовпця вектора Р₀ табл. 1.7.

Значення F₀ в 4-му рядку стовпця цього ж вектора можна знайти двома способами:

1) по формулі F₀= (C, Р₀),тобто F₀= 0·72 + 16·24+0·108=384;

2) за правилом трикутника; у цьому випадку трикутник утворений числами 0, –16,·24. Цей спосіб приводить до того ж результату: 0 – (–16)·24=384.

При визначенні за правилом трикутника елементів стовпця вектора Р₀ третє число, що стоїть в нижній вершині трикутника, увесь час залишалося незмінним і мінялися лише перші два числа. Врахуємо це при знаходженні елементів стовпця вектора Р₁ табл. 1.7. Для обчислення зазначених елементів перші два числа беремо зі стовпців векторів Р₁ і Р₃ табл. 1.6, а третє число – з табл. 1.7. Це число стоїть на перетині 2-го рядка і стовпця вектора Р₁ останньої таблиці. У результаті одержуємо значення шуканих елементів: 18–12·(3/4)=9; 5–3·(3/4)=11/4.

Число z₁ – c₁ в 4-у рядку стовпця вектора Р₁ табл. 1.7 можна знайти двома способами:

1) по формулі z₁ – c₁= (C, Р₁) - с₁ маємо 0·9+16·3/4+0·11/4–9=3;

2) за правилом трикутника одержимо –9–(–16)·(3/4)=3

Аналогічно знаходимо елементи стовпця вектора Р₂

Елементи стовпця вектора Р₅ обчислюємо за правилом трикутника. Однак побудовані для визначення цих елементів трикутники виглядають інакше.

При обчисленні елемента 1-го рядка зазначеного стовпця виходить трикутник, утворений числами 0,12 і 1/8. Отже, шуканий елемент дорівнює 0–12·(1/8)= –3/2. Елемент, що стоїть в 3-у рядку даного стовпця, дорівнює 0–3·(1/8)= –3/8.

По закінченні розрахунку всіх елементів табл. 1.7 у ній отримані новий опорний план і коефіцієнти розкладання векторів Р (j = ) через базисні вектори Р₄, Р₃, Р₆ і значення Δ′ _j і F′₀. Як видно із цієї таблиці, новим опорним планом задачі є план Х= (0; 0; 24; 72; 0; 108). При даному плані виробництва виготовляється 24 вироби С і залишаються невикористаними 72 кг сировини I виду і 108 кг сировини III виду. Вартість всієї виробленої при цьому плані продукції дорівнює 384 грн. Зазначені числа записані в стовпці вектора Р₀ табл. 1.7. Як видно, дані цього стовпця як і раніше являють собою параметри розглянутої задачі, хоча вони перетерпіли значні зміни. Змінилися дані і інших стовпців, а їх економічний зміст став більш складним. Так, наприклад, візьмемо дані стовпця вектора Р₂. Число 1/2 в 2-у рядку цього стовпця показує, на скільки варто зменшити виготовлення виробів С, якщо запланувати випуск одного виробу В. Числа 9 і 3/2 в 1-у і 3-у рядках вектора Р₂ показують відповідно, скільки буде потрібно сировини I і II виду при включенні в план виробництва одного виробу В, а число -2 в 4-у рядку показує, що якщо буде заплановано випуск одного виробу В,то це забезпечить збільшення випуску продукції у вартісному вираженні на 2 грн. Іншими словами, якщо включити в план виробництва продукції один виріб В, то це вимагатиме зменшення випуску виробу С на 1/2 од. і вимагатиме додаткових витрат 9 кг сировини I виду і 3/2 кг сировини III виду, а загальна вартість виготовленої продукції відповідно до нового оптимального плану зросте на 2 грн. Таким чином, числа 9 і 3/2 виступають як би новими «нормами» витрат сировини I і III виду на виготовлення одного виробу В (як видно з табл. 1.6, раніше вони були рівні 15 і 3), що пояснюється зменшенням випуску виробів С.

Такий же економічний зміст мають і дані стовпця вектора Р₁ табл. 1.7. Дещо інший економічний зміст мають числа, записані в стовпці вектора Р₁. Число 1/8 в 2-у рядку цього стовпця, показує, що збільшення об’ємів сировини II виду на 1 кг дозволило б збільшити випуск виробів С на 1/8 од. Одночасно потрібно було б додатково 3/2 кг сировини I виду і 3/8 кг сировини III виду. Збільшення випуску виробів С на 1/8 од. призведе до росту випуску продукції на 2 грн.

З викладеного вище економічного змісту даних табл. 1.7 випливає, що знайдений на II ітерації план задачі не є оптимальним. Це видно і з 4-го рядка табл. 1.7, оскільки в стовпці вектора Р₂ цього рядка стоїть від’ємне число -2. Виходить, у базис варто ввести вектор Р₂, тобто в новому плані варто передбачити випуск виробів В. При визначенні можливого числа виготовлення виробів В варто враховувати наявну кількість сировини кожного виду, а саме: можливий випуск виробів В визначається тіп (b′_i / а′_i2)для а′_i2 > 0, тобто знаходимо

θ₀= тіп (72/9; 24·2/1; 108·2/3)=72/9=8.

Отже, виключенню з базису підлягає вектор Р₄, іншими словами, випуск виробів В обмежений наявною у розпорядженні підприємства сировиною I виду. З урахуванням наявних об’ємів цієї сировини підприємству варто виготовити 8 виробів В. Число 9 є розв’язним елементом, а стовпець вектора Р₂ і 1-й рядок табл. 1.7 є направляючими. Складемо таблицю для III ітерації (табл. 1.8).

Таблиця 1.8

i	Базис	C₆	P₀
P₁	P₂	P₃	P₄	P₅	P₆
	P₂ P₃ P₆			1/4 5/4		1/9 –1/18 –1/6 2/9	–1/6 5/24 –1/8 5/3

У табл. 1.8 спочатку заповнюємо елементи 1-го рядка, що являє собою рядок вектора Р₂, що заново вводиться в базис. Елементи цього рядка одержуємо з елементів 1-го рядка табл. 1.7 діленням останніх на розв’язний елемент (тобто на 9). При цьому в стовпці С_б даного рядка записуємо С₂ =10.

Потім заповнюємо елементи стовпців векторів базису і за правилом трикутника обчислюємо елементи інших стовпців. У результаті в табл. 1.8 одержуємо новий опорний план X =(0; 8; 20; 0; 0; 96) і коефіцієнти розкладання векторів Р_j (j = ) через базисні вектори Р₂, Р₃, Р₆ і відповідні значення Δ _j" і F₀.

Перевіряємо, чи є даний опорний план оптимальним чи ні. Для цього розглянемо 4-ий рядок табл. 1.8. У цьому рядку серед чисел Δ _j" немає від’ємних. Це означає, що знайдений опорний план є оптимальним і F_тах= 400.

Отже, план випуску продукції, що включає виготовлення 8 виробів В і 20 виробів С, є оптимальним. При даному плані випуску виробів повністю використовується сировина I і II видів і залишається невикористаним 96 кг сировини ІІІ виду, а вартість виробленої продукції дорівнює 400 грн.

Оптимальним планом виробництва продукції не передбачається виготовлення виробів А. Введення в план випуску продукції виробів виду А призвело б до зменшення зазначеної загальної вартості. Це видно з 4-го рядка стовпця вектора Р_j, де число 5 показує, що при даному плані включення в нього випуску одиниці виробу А призводить лише до зменшення загальної величини вартості на 5 грн.

Розв’язок даного прикладу симплексним методом можна було б проводити, використовуючи лише одну таблицю (табл. 1.9). У цій таблиці послідовно записані одна за іншою всі три ітерації обчислювального процесу.

Таблиця 1.9

i	Базис	C₆	P₀
P₁	P₂	P₃	P₄	P₅	P₆
	P₄ P₅ P₆			–9	–10	–16
	P₄ P₃ P₆			3/4 11/4	1/2 3/2 –2			–3/2 1/8 –3/8
	P₂ P₃ P₆			1/4 5/4			1/9 –1/18 –1/6 2/9	–1/6 5/24 –1/8 5/3

⇐ Предыдущая 1 2 345 6 7 8 9 10 Следующая ⇒