Приклади розв'язування оптимізаційних задач лінійного програмування

Завдання 2.1. Оптимальне використання ресурсів при плануванні робіт. Визначення оптимального асортименту

Розрахувати максимальний прибуток цеху від продажу виро­бів А1, А2, АЗ і А4. Ресурси (листи металу, пластмаса, деревина, гроші, трудові ресурси), норми витрат і прибуток від одного ви­робу подано в табл. 2.1.

Таблиця 2.1 - Оптимальне використання ресурсів при плануванні робіт. Визначення оптимального асортименту

№ з/п	Показник	Запаси ресурсів	Норми витрат
Виріб А1	Виріб А2	Виріб АЗ	Виріб А4
	Листи металу (куб. м)
	Пластмаса (кг)
	Деревина (куб. м)
	Прибуток за 1 виріб, грн./шт.

Позначимо через х₁ шукану кількість штук виробу А1, а через х₂, х₃ і х₄ відповідно - кількість виробів А2, А3 і А4.

Тоді перше об­меження з використання металу запишеться у вигляді нерівності:

Друге обмеження з використання пластмаси має вигляд:

Третє обмеження з деревини має вигляд:

14

Тоді цільова функція буде такою:

Приклад розв'язання задачі в Місrоsoft. Ехсеl представлено на рисунку 2.1.

Рисунок 2.1 - Приклад розв'язання задачі на ПК

Аналізуючи розв'язок задачі, можна зробити такі висновки.

1. Оптимальний (максимальний) прибуток від реалізації ста­новить 44 грн.

2. Оптимальне сполучення асортименту таке: виріб А1 - 4 шт.; виріб А2 - 6 шт.; виріб АЗ - 2 шт.; виріб А4 - 0 шт.

Завдання 2.2. Визначення оптимального асортименту продукції

Підприємство виготовляє два види продукції - П₁ і П₂, яка над­ходить до оптового продажу. Для виробництва продукції вико­ристовуються два види сировини - А і В. Максимально можливі добові запаси сировини становлять 9 і 13 одиниць відповідно. Витрати сировини на одиницю продукції виду П₁ і виду П₂ на­ведені в табл. 1.1.

Таблиця 2.2 - Витрати сировини

Сировина	Витрати сировини на 1 од. продукції	Запас сировини, од.
П1	П2
А
В

Вивчення ринку збуту показало, що добовий попит на продукцію П₁ ніколи не перевищує попит на продукцію П₂ більш, ніж на 1 од. Крім того, встановлено, що попит на продукцію П₂ ніколи не перевищує 2 од. за добу.

Оптові ціни одиниці продукції дорівнюють: 3 гр.од. - для П₁ і 4 гр.од. - для П₂.

Необхідно побудувати математичну модель, яка дозволяє встано­вити, яку кількість продукції кожного виду потрібно виготовити, щоб доход від реалізації продукції був максимальним.

Розв'язання

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

1) Що є шуканими величинами задачі?

2) Яка мета розв'язання? Який параметр задачі служить кри­терієм ефективності (оптимальності) розв'язку, наприклад: прибу­ток, собівартість, час і т. д. У якому напрямку повинно змінювати­ся значення цього параметра (до max або до min) для досягнення найкращих результатів?

3) Які умови щодо шуканих величин і ресурсів задачі повинні бути виконані?

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

Тільки після економічної відповіді на всі ці питання можна при­ступати до запису цих відповідей в математичному виді, тобто до запису математичної моделі.

1) Шукані величини є змінними задачі, які, як правило, познача­ються малими латинськими буквами з індексами, наприклад, одно­типні змінні зручно зображати у вигляді Х= (х₁, x₂, х_п).

2) Ціль розв'язання записується у вигляді цільової функції, що позначається, наприклад, f(X). Математична формула ЦФ f(X) ві­дображає спосіб розрахунку значень параметра - критерію ефек­тивності задачі.

3) Умови, що накладаються на змінні і ресурси задачі, запису­ються у вигляді системи рівностей або нерівностей, тобто обме­жень. Ліві і праві частини обмежень відображають спосіб одер­жання (розрахунок або чисельні значення з умови задачі) значень тих параметрів задачі, на які були накладені відповідні умови.

У процесі запису математичної моделі необхідно вказувати оди­ниці виміру змінних задачі, цільової функції і всіх обмежень. По­будуємо модель задачі 2.2 використовуючи описану методику.

Змінні задачі: У задачі потрібно встановити, скільки продукції кожного виду не­обхідно виготовити. Тому шуканими величинами, а значить, і змін­ними задачі є добові обсяги виробництва кожного виду продукції:

х₁ - добовий обсяг виробництва продукції П_| [од./добу];

х₂ - добовий обсяг виробництва продукції П₂ [од./добу].

Цільова функція: В умові задачі сформульована мета - досягти максимального до­ходу від реалізації продукції. Тобто критерієм ефективності слу­жить параметр добового доходу, який повинен прагнути до мак­симуму. Щоб розрахувати величину добового доходу від продажу продукції обох видів, необхідно знати обсяги виробництва продук­ції, тобто х₁, і х₂ одиниць за добу, а також оптові ціни на продукцію П₁ та продукцію П₂. Таким чином, дохід від продажу добового об­сягу виробництва продукції П₁ дорівнює Зх₁ гр.од. за добу, а від продажу продукції П₂ - 2х₂ гр.од. за добу. Тому, запишемо ЦФ у вигляді суми доходу від продажу продукції П₁ й П₂ (при допущенні незалежності обсягів збуту кожної з продукти): f(X)=3х₁+4х₂ [гр.од./добу].

Обмеження: Можливі обсяги виробництва продукції х_{ і х₂ обмежуються на­ступними умовами:

- кількість сировини А і В, витрачена протягом доби на виробни­цтво продукції обох видів, не може перевищувати добового запасу цієї сировини на складі;

- відповідно до результатів вивчення ринкового попиту добовий обсяг виробництва продукції П₁ може перевищувати обсяг вироб­ництва продукції П₂, але не більш, ніж на 1 од. продукції;

- обсяг виробництва продукції П₂ не повинен перевищувати 2 од. за добу, що також виходить з результатів вивчення ринків збуту;

- обсяги виробництва продукції не можуть бути від'ємними.

Таким чином, всі обмеження задачі діляться на 3 групи, обумовлені:

1) витратами сировини;

2) ринковим попитом на продукцію;

3) невід'ємністю обсягів виробництва.

Обмеження на витрати кожного з видів сировини мають наступ­ну змістовну форму запису:

(Витрати конкретної сировини на виробництво обох видів продукції) (Максимально можливий запас даної сировини).

Запишемо ці обмеження в математичній формі.

Ліва частина обмеження - це формула розрахунку добових ви­трат конкретної сировини на виробництво продукції. Так, з умо­ви відомі витрати сировини А на виробництво 1од. продукції П₁ і 1 од. продукції П₂ (див. табл. 1.1). Тоді на виробництво х_х од. про­дукції П, і х₂ од. продукції П₂ потрібно 2х_х + 3х₂ од. сировини А.

Права частина обмеження - це величина добового запасу сиро­вини на складі, наприклад, 9 од. сировини А за добу (див. табл. 2.2).

Таким чином, обмеження на витрати А має вигляд:

2х₁ + 3х₂ < =9.

Аналогічний математичний запис обмеження на витрати В:

3х₁ + 2х₂<= 13.

Примітка. Варто завжди перевіряти розмірність лівої й правої частини кожно­го з обмежень, оскільки їхня розбіжність свідчить про принципову помилку при складанні обмежень.

Обмеження щодо добового обсягу виробництва продукції П₁ по­рівняно з обсягом виробництва продукції П₂ має змістовну форму:

(Перевищення обсягу виробництва продукції П₁ над обсягом виробництва продукції П₂) 1од. продукції/добу)

і математичну форму:

Обмеження щодо добового обсягу виробництва продукції П₂ має змістовну форму:

(Попит на продукцію П₂) 2од. продукції/добу)

і математичну форму: х₂ 2.

Невід'ємність обсягів виробництва задається як: х₁ 0, х₂ 0.

Таким чином, математична модель цієї задачі має вигляд:

f(X)=3х₁+4х₂

Завдання 2.3. Задача використання фонду робочого часу.

Виконати замовлення на виробництво 32 виробів В₁ і 4 виробів В₂ узялися бригади Б, і Б₂. Продуктивність бригади Б₁ на виробництво виробів B1 і В₂ становить відповідно 4 і 2 виробів за годину, фонд робочого часу цієї бригади 9,5 год. Продуктивність бригади Б₂ ~ відповідно 1 і 3 вироби за годину, а її фонд робочого часу - 4 год. Витрати, пов'язані з виробництвом одиниці виробу, для бригади Б₁ дорівнюють відповідно 9 і 20 гр.од., для бригади Б₂ — 15 і 30 гр.од.

Складіть математичну модель задачі, яка дозволяє знайти опти­мальний обсяг випуску виробів, що забезпечує мінімальні витрати на виконання замовлення.

Розв'язання

Змінні задачі: Шуканими величинами в задачі є обсяги випуску виробів. Вироби В₁ будуть виготовлятися двома бригадами Б₁ і Б₂. Тому необхідно розрізняти кількість виробів В₁, виготовлених бригадою Б₁ і кіль­кість виробів В₁ виготовлених бригадою Б₂. Аналогічно, обсяги ви­пуску виробів В₂ бригадою Б₁ і бригадою Б₂ також є різними величи­нами. Внаслідок цього в даній задачі 4 змінні. Для зручності сприй­няття використовуватимемо двоіндексну форму запису хij - кількість виробів Вj (j = 1,2), що виготовляються бригадою Бi (i = 1,2), а саме:

х₁₁ - кількість виробів В₁, що виготовляються бригадою Б₁ [од.];

х₁₂- кількість виробів В₂, що виготовляються бригадою Б₁ [од.];

х₂₁ - кількість виробів В_1, що виготовляються бригадою Б₂ [од.];

х₂₂ - кількість виробів В₂, що виготовляються бригадою Б₂ [од.].

Примітка. Уданій задачі немаєнеобхідності прив'язуватися до якого-небудь часового інтервалу (у задачі 2.2 була прив'язка до доби), оскільки тут потрібно знайти не обсяг випуску за певний час, а спосіб розподілу відомої планової вели­чини замовлення між бригадами.

Цільова функція: Метою розв'язання задачі є виконання плану з мінімальними ви­тратами, тобто критерієм ефективності розв'язку служить показ­ник витрат на виконання всього замовлення. Тому ЦФ повинна бути зображена формулою розрахунку цих витрат. Витрати кожної бригади на виробництво одного виробу В₁ і В₂ відомі з умови. Та­ким чином, ЦФ має вигляд:

f(X) = 9х_х і + 20х_п + 15х₂₁ + 30х₂₂ min гр.од.

Обмеження. Можливі обсяги виробництва виробів бригадами обмежуються наступними умовами:

- загальна кількість виробів В₁, виготовлена обома бригадами, повинна дорівнювати 32 од., а загальна кількість виробів В₂ -4 од.;

- час, відпущений на роботу над даним замовленням, складає для бригади Б₁-9,5 год., а для бригади Б₂ - 4 год.;

- обсяги виробництва виробів не можуть бути від'ємними вели­чинами.

Таким чином, всі обмеження задачі 1.4 діляться на 3 групи обу­мовлені:

1) величиною замовлення на виробництво виробів;

2) фондом часу, виділеним бригадам;

3) невід'ємністю обсягів виробництва.

Для зручності складання обмежень запишемо вихідні дані у ви­гляді табл. 2.3.

Таблиця 2.3 -. Вихідні дані задачі 2.3

Бригада	продуктивність бригад, од./год	фонд робочого часу, год.
В1	В2
Б 1			9,5
Б2
Замовлення			-

Обмеження на виробництво виробів мають наступну змістовну форму запису:

(Кількість виробів В₁, виготовлених бригадами Б₁ і Б₂) = (32 од.)

(Кількість виробів В₂, виготовлених бригадами Б₁ і Б₂) = (4 од.)

Математична форма запису має вигляд: х₁₁+х₁₂=32; х₂₁+х₂₂=4

Обмеження щодо фонду часу мають змістовну форму^:

(3агалий час, витрачений бригадою Б₁, на виготовлення виробів В, і В₂) (9,5 год.)

(Загальний час, витрачений бригадою Б₂ на виготовлення виробів В₁ і В₂) (4 год.)

Проблема полягає у тому, що в умові задачі прямо не заданий час, який витрачають бригади на виготовлення одного виробу В₁ або В₂, тобто не задана трудомісткість виробництва. Але є інформація про продуктивність кожної бригади, тобто про кількість виготов­лених виробів за 1 годину. Трудомісткість Тр і продуктивність Пр є зворотними величинами, тобто:

Тому, використовуючи табл. 2.3, отримуємо наступну інфор­мацію:

> 1/4 год. витрачає бригада Б₁ на виробництво одного виробу В₁;

> 1/2 год. витрачає бригада Б₁ на виробництво одного виробу В₂;

> 1/1 год. витрачає бригада Б₂ на виробництво одного виробу В₁;

> 1/3 год. витрачає бригада Б₂ на виробництво одного виробу В₂.

Запишемо обмеження щодо фонду часу в математичному вигляді:

Невід'ємність обсягів виробництва задається як

Таким чином, математична модель цієї задачі має вигляд:

f(X)=9х₁₁+20х₁₂+15х₂₁+30х₂₂

Завдання 2.4. Задача про розкрій або про мінімізацію обрізків.

Для пошиття одного виробу потрібно викроїти із тканини 6 де­талей. На швейній фабриці були розроблені два варіанти розкрою тканини. У табл. 2.4 наведені характеристику варіантів розкрою 10 м² тканини й комплектність, тобто кількість деталей певного виду, які необхідні для пошиття одного виробу. Щомісячний запас тканини для пошиття виробів даного типу становить 405 м². У най­ближчий місяць планується зшити 90 виробів.

Таблиця 2.4. - Характеристики варіантів розкрою відрізів ткани­ни по 10 м²

Варіант розкрою	Кількість деталей, шт./відріз	Відходи, м2/відріз
							0,5
							0,35
Комплектність, шт./ виріб							-

Побудуйте математичну модель задачі, що дозволяє в найближ­чий місяць виконати план за пошиття з мінімальною кількістю відходів.

Розв'язання

Змінні задачі. У даній задачі шукані величини явно не вказані, але сказано, що повинен бути виконаний щомісячний план з пошиття 90 виробів. Для пошиття 90 виробів на місяць потрібно розкроїти строго пев­ну кількість деталей. Крій проводиться з відрізів тканини по 10 м² двома різними способами, які дозволяють одержати різне число деталей. Оскільки заздалегідь невідомо, скільки тканини буде роз­кроєно першим способом і скільки — другим, то шукані величини можна задати як кількість відрізів тканини по 10 м², розкроєних кожним із способів:

х₁ - кількість відрізів тканини по 10 м², розкроєних першим спо­собом протягом місяця [відріз/міс.];

х₂ - кількість відрізів тканини по 10 м², розкроєних другим спо­собом протягом місяця [відріз/міс].

Цільова функція. Метою розв'язання задачі є виконання плану при мінімальній кількості відходів. Оскільки кількість виробів строго запланована (90 шт./міс.), то цей параметр не описує ЦФ, а відноситься до об­меження, невиконання якого означає, що задача не розв'язана. А критерієм ефективності виконання плану служить параметр «кіль­кість відходів», який необхідно звести до мінімуму. Оскільки при розкрої одного відрізу (10 м²) тканини за 1-им варіантом виходить 0,5 м² відходів, а за 2-им варіантом - 0,35 м² (див. табл. 2.4).

Загальна кількість відходів при розкрої (ЦФ) має вигляд

Обмеження. Кількість розкроїв тканини різними способами обмежується на­ступними умовами:

- повинен виконуватись план з пошиття виробів, інакше кажучи, загальна кількість викроєних деталей має бути такою, щоб з них можна було пошити 90 виробів на місяць, а саме: деталей 1 -го виду повинно бути як мінімум 90 і деталей інших видів - як мінімум по 180 (див. комплектність в табл. 2.4);

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

- кількість відрізів розкроєних тканин не може бути від'ємною.

Обмеження за планом пошиття виробів мають наступну зміс­товну форму запису:

(Загальна кількість деталей №1, розкроєних за всіма варіантами) (90 штук);

(Загальна кількість деталей №2, розкроєних за всіма варіантами) (180 штук);

………………………………………………

(Загальна кількість деталей №6, розкроєних за всіма варіантами) (180 штук). шт.

Математично ці обмеження записуються у вигляді:

60х₁ + 80х₂ 90,

35х₂ 180,

90х₁ + 20х₂ 180,

40х₁ +78х₂ 180,

70х₁ + 15х₂ 180,

90х₁ 180,

Обмеження щодо витрат тканини мають наступну змістовну форми запису: (Загальна кількість тканини, розкроєної за місяць) (405 м²)

і математичну: ,

Невід’ємність кількості розкроєних відрізків задається у вигляді:

Таким чином, математична модель цієї задачі має вигляд:

f(X)=0,5х₁+0,35х₂

3. Розв'язування задач лінійного програмування на площині

Розв'язати задачу лінійного програмування графічно означає знайти таку вершину многокутника розв'язків, у результаті підставляння координат якої лінійна цільова функція набуває найбільшого (найменшого) значення.

Алгоритм графічного методу розв'язування задач лінійного програмування складається з розглянутих далі кроків.

1. Будуємо прямі лінії, рівняння яких дістаємо заміною в об­меженнях задачі знаків нерівностей на знаки рівностей.

2. Визначаємо півплощини, що відповідають кожному обме­женню задачі.

3. Знаходимо многокутник розв'язків задачі лінійного програ­мування.

4. Будуємо вектор N= (с₁;с₂), що задає напрям зростання зна­чень цільової функції задачі.

5. Будуємо пряму , перпендикулярну до век­тора N.

6. Переміщуючи пряму в напрямі вектора N (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину многокутника розв'язків, де цільова функція досягає екстремального значення.

7. Визначаємо координати точки, в якій цільова функція набуває максимального (мінімального) значення, і обчислюємо екст­ремальне значення цільової функції в цій точці.

Завдання 3.1. Графічним способом знайти максимум і мінімум лінійної функції L= 2x-2y

за умов

Па площині побудуємо прямі лінії –х+у=2, 5х+3у=18, відкладемо вектор N= (2, —2) і знайдемо область М (рис. 3.1).

Рисунок 3.1. – Геометрична інтерпретація ЗЛП

Областю М буде п'ятикутник ОАВСD. Перетнемо область М примою l, перпендикулярною до вектора N. Якщо пряму l зміщувати паралельно самій собі в напрямку вектора N доти, поки вона не стане опорною до М, то бачимо, що L досягає мак­симуму н точці С. Якщо пряму l зміщувати в протилежному нап­рямку доти, поки вона не стане опорною до М, то бачимо, що L досягне мінімуму в будь-якій точці відрізка АВ (пряма l пара­лельна прямій —х+у=2).

Координатами точки А є х=0, у = 2. Тому, підставивши ці зна­чення в лінійну форму, одержимо тіп L = 2-0—2-2=— 4.

Знайдемо координати точки С. Для цього розв'яжемо систему рів­нянь:

Розв'язком цієї системи є х=3, у=1. Тому точка С має коорди­нати х = 3, у=1. Підставивши ці значення в лінійну форму, отри­маємо тах L =2-3—2-1=4.

Методика розв’язання ЗЛП графічним методом з використанням електронних таблиць

1. Для кожного обмеження можна визначити параметри рівняння, що його визначає:

2. У свою чергу можна побудувати вектор-градієнт за двома точками та .

3. Лінії рівня, перпендикулярні вектору-градієнту визначаються рівняннями:

,

де – будь-яка константа, яка визначає точку перетину прямої з віссю ординат.

4. Для побудови відповідних ліній необхідно створити таблиці:

Рівняння	Параметри
a	b
Обмеження 1
Обмеження 2
Обмеження 3

	Обмеження 1	Обмеження 2	Обмеження 3

Вектор-градієнт

Лінії рівня для окремих значень

5. За допомогою майстер діаграм (тип діаграми «точечная» в Excel) побудувати відповідні лінії. Потім діаграму можна доповнити різними елементами у будь-якому графічному редакторі:

Рисунок 3.2 – Приклад графічної інтерпретації ЗЛП

6. Координати точок перетину різних ліній за необхідністю можна визначити шляхом розв’язання систем відповідних рівнянь.

4. Алгоритм розв'язування задачі лінійного програмування симплекс-методом складається з п'яти етапів:

1. Визначення початкового опорного плану задачі лінійного програмування.

2. Побудова симплексної таблиці.

3. Перевірка опорного плану на оптимальність за допомогою оцінок: .

Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі.

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

4 Перехід до нового опорного плану задачі виконується визначенням розв’язувального елемента та розрахунком нової симплекс таблиці.

5. Повторення дій починаючи з п. 3.

Завдання 4.1. Нехай x_j — план виробництва продукції j -го виду, де j може набувати значень від 1 до 4.

Умовами задачі будуть обмеження на час використання верстатів для виробництва продукції всіх видів:

• для верстата 1: 2х₁ + 3х₂ + 4х₃ + 2х₄ <= 450 (машино-год);

• для верстата 2: 3х₁ + 2х₂ + х₃ + 2х₄ <= 380 (машино-год).

Цільова функція задачі визначається як загальний чистий прибуток від реалізації готової продукції і складається з різниці між ціною та собівартістю виготовлення продукції кожного виду:

Z=(73-(2*10+3*15))x₁+(70-(3*10+3*15))x₂+

+(55-(4*10+1*15))x₃+(45-(2*10+2*15))x₄;

Z= 8x₁+10x₂+0x₃-5x₄.

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

Розв'яжемо задачу симплекс-методом згідно з розглянутим алгоритмом

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

x_j 0, j=1,6.

Ці додаткові змінні за економічним змістом означають можливий, але не використаний для виробництва продукції час роботи верстатів 1 та 2. У цільовій функції Z додаткові змінні мають коефіцієнти, які дорівнюють нулю:

Канонічну систему обмежень задачі запишемо у векторній формі:

де

Оскільки вектори та одиничні та лінійно незалежні, саме з них складається початковий базис у зазначеній системі векторів. Змінні задачі x₅ та x₆, що відповідають одиничним базисним векторам, називають базисними, а решту — вільними змінними задачі лінійного програмування. Прирівнюючи вільні змінні до нуля, з кожного обмеження задачі дістаємо значення базисних змінних: x₁=х₂=х₃=х₄ =0, х₅=450, х₆=380.

Згідно з визначеними хj (j = 1, 6) векторна форма запису системи обмежень задач матиме вигляд:

Оскільки додатні коефіцієнти x₅ та x₆ відповідають лінійно незалежним векторам, то за означенням x0=(0;0;0;0;450;380)

є опорним планом задачі і для цього початкового плану

Z0= 8*0 + 10*0-5*0 + 0*450 + 0*380 = 0.

2. Складемо симплексну таблицю для першого опорного плану задачі.

Елементи останнього рядка симплекс-таблиці є оцінками за допомогою яких опорний план перевіряють на оптимальність. Їх визначають так:

Z₁-C₁=(0*2+0*3)-8= -8;

Z₂-C₂=(0*3+0*2)-10= -10;

Z₃-C₃=(0*4+0*1)-0= 0;

Z₄-C₄=(0*2+0*2)-(-5)= 5;

Z₅-C₅=(0*1+0*0)-0= 0;

Z₆-C₆=(0*0+0*1)-0= 0;

У стовпчику «План» оцінкового рядка записують значення цільової функції Z, якого вона набуває для визначеного опорного плану: Z0 =0*450 + 0*380 = 0.

3. Після обчислення всіх оцінок опорний план перевіряють на оптимальність.

Для цього продивляються елементи оцінкового рядка. Якщо всі (для задачі на max) або (для задачі на min), визначений опорний план є оптимальним.

Якщо ж в оціночному рядку присутня хоча б одна оцінка, що не задовольняє умову оптимальності (від'ємна в задачі на max або додатна в задачі на min), то опорний план є неоптимальним і його можна поліпшити.

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

4. Перехід від одного опорного плану до іншого виконують зміною базису, тобто за рахунок виключення з поточного базису якоїсь змінної та включення замість неї нової з числа вільних змінних.

Для введення до нового базису беремо змінну х₂, оскільки їй відповідає найбільша за абсолютною величиною оцінка серед тих, які не задовольняють умову оптимальності (|-10| > |-8|).

Щоб визначити змінну, яка підлягає виключенню з поточного базису, для всіх додатних елементів стовпчика «х₂» знаходимо відношення і вибираємо найменше значення.

Згідно з даними симплексної таблиці бачимо, що min = {450/3; 380/2} = 150, і тому з базису виключаємо змінну х₅, а число а₁₂ = 3 називатимемо розв'язувальним елементом.

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

Друга симплексна таблиця має такий вигляд:

У цій таблиці спочатку заповнюють два перших стовпчики «Базис» і «С_баз», а решту елементів нової таблиці розраховують за розглянутими далі правилами:

1. Розв’язувальний (напрямний) рядок необхідно поділити на розв'язувальний елемент і здобуті числа записати у відповідний рядок нової симплексної таблиці.

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

3. Якщо в напрямному рядку є нульовий елемент, то відповідний стовпчик переписують у нову симплексну таблицю без змін.

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

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

Щоб визначити будь-який елемент нової таблиці за цим прави­лом, необхідно в попередній симплексній таблиці скласти умовний прямокутник, вершини якого утворюються такими числами:

1 — розв'язувальний елемент;

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

3 та 4 — елементи, що розміщуються в двох інших протилежних вершинах умовного прямокутника.

Необхідний елемент нової симплекс-таблиці визначають так:

Наприклад, визначимо елемент а'24, який розміщується в новій таблиці в другому рядку стовпчика «х₄». Складемо умовний прямокутник:

Тоді а’₂₄ = (3 • 2 - 2 • 2):3 = 2/3. Це значення записуємо в стовпчик «x₄» другого рядка другої симплексної таблиці.

Після заповнення нового оціночного рядка перевіряємо виконання умови оптимальності для другого опорного плану. Цей план також неоптимальний, оскільки =-4/3.

Використовуючи процедуру симплекс-методу, визначаємо третій опорний план задачі, який наведено у вигляді таблиці:

Базис	Сбаз	План				-5
х1	х2	х3	х4	х5	х6
х2						2/5	3/5	-2/5
х1					-1	2/5	-2/5	3/5
					61/5	14/5	4/5

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

або Х*=(48;118;0;0;0;0) max Z=8*48+10*118+0*0-5*0=1564.

Отже, план виробництва продукції, що передбачає випуск 48 одиниць продукції А та 118 од. продукції В, оптимальний і дає найбільший прибуток 1564 грош.од.

При цьому час роботи верстатів використовується повністю (x₅ = x₆ = 0).

5. Транспортна задача

Транспортна задача — це специфічна задача лінійного про­грамування, застосовувана для визначення найекономічнішого плану перевезення однорідної продукції від постачальників до споживачів.

Математична модель транспортної задачі має такий вигляд:

(5.1)

за обмежень

(5.2)

(5.3)

, (5.4)

де х_ij — кількість продукції, що перевозиться від i-го постачаль­ника до j-го споживача;

с_ij — вартість перевезення одиниці про­дукції від i-го постачальника до j-го споживача;

а_i — запаси про­дукції i-го постачальника;

b_j — попит на продукцію j-го споживача.

Алгоритм розв’язання транспортної задачі представлено на рис.5.1.

Рисунок 5.1 – Розв’язок транспортної задачі

Методи пошуку початкових опорних планів транспортної задачі представлені на рис.5.2.

Рисунок 5.2. - Методи пошуку початкових опорних планів транспортної задачі

Метод північно-західного кута

Побудову опорного плану задачі починають із заповнення лівої верхньої клітинки таблиці х11, в яку записують менше з двох чисел а1 та b1.

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