Задача про завантаження обладнання

Нехай підприємству задано план виробництва продукції за часом і номенклатурою: треба за час Т виготувати n₁, n₂, …… n_k одиниць продукції Р₁, Р₂, P₃, ……P_k. Продукція обробляється на верстатах S₁, S₂, S₃,……. S_m. Для кожного верстата відома продуктивність а_ij (тобто кількість одиниць продукції Р_j, яку можна виготувати на верстаті S_i) і витрати b_ij на виготовлення продукції Р_j на верстаті S_i за одиницю часу.

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

Позначимо х_ij – час, протягом якого верстат S_i буде виготовляти продукцію Р_j (i=1.2.3…..m, j=1.2.3…..n).

Оскільки час роботи кожного верстата обмежений і не перевищує Т, то справедливі нерівності:

x_1,1+ x_1,2 +x_1,3+ ……. + x_1,k ≤ T

x_2,1+ x_2,2 +x_2,3+ ……. + x_2,k ≤ T

x_3,1+ x_3,2 +x_3,3+ ……. + x_3,k ≤ T (4)

x_m,1+ x_m,2 +x_m,3+ ……. + x_m,k ≤ T

Для виконання плану виготовлення за номенклатурою необхідно, щоб виконувались рівності:

a₁₁x₁₁+a₂₁x₂₁+……………. + a_m1x_m1 ≤ n₁

a₁₂x₁₂+a₂₂x₂₂+ …………… +a_m2x_m2 ≤ n₂

…………………………………………. (5)

a₁_kx₁_k+a₂_kx₂_k+………………+a_mkx_mk ≤ n_k

Крім цього, х_ij≥0, (i=1.2.3…..m, j=1.2.3…..k) (6)

Витрати на виробництво всієї продукції задаються функцією

L= b₁_kx₁_k+b₂_kx₂_k+……+b_mkx_mk →min (7)

Отже, ЕММ задачі про завантаження обладнання має вигляд:

Знайти такий розв’язок Х=(x₁₁,x₁₂,x₁₃,…….,x_mk), що задовольняє системам (4) – (6), за якою функція набуває мінімального значення.

6. Модель міжгалузевого балансу „Витрати - випуск”.

Матричні ЕММ призначені для аналізу та планування виробництва та розподілу продукції на різних рівнях – від окремого підприємства до народного господарства в цілому.

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

Зв’язок між галузями, відображається у таблицях міжгалузевого балансу, а математична модель, яка дозволяє їх аналізувати, розроблена в 1936 році американським вченим В. Леонтьєвим.

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

Кожна галузь двічі присутня в балансі: як виробник так і як споживач галузі. Як виробнику відповідає визначена строка балансу, а галузі як споживачу визначен стовпець балансу. Якщо номер будь якого виробника галузі позначити через i, аномер будь якої споживчої галузі через j, то величину х_ij потрібно розуміти як вартість засобів виробництва, вироблених у

i -й галузі та спожитої в якості матеріальних витрат в j-й галузі.

Матрична модель міжгалузевого балансу

Виробнича галузь	Споживча галузь	Продукція, тис.грн.
			j	N	Кінцева	Валова
	x₁₁	x₁₂	x₁₃	…	x_1n	y₁	X₁
	x₂₁	x₂₂	x₂₃	…	x_2n	y₂	X₂
	x₃₁	x₃₂	x₃₃	…	x_3n	y₃	X₃
I	…	…	…	…	…	...	…
N	x_n1	x_n2	x_n3	…	x_nn	y_n	X_n
Оплата праці	v₁	v₂	v₃	…	v_n	v_кон	-
Чистий дохід, тис. грн.	m₁	m₂	m₃	…	m_n	m_кон	-
Валова продукція, тис. грн.	X₁	X_2`	X₃	…	X_n	-	X

В стовбцях міжгалузевого балансу відображена структура матеріальних витрат та чистої продукції кожної галузі. Припустимо. 1-а галузь – це виробництво електоенергії, друга – вугільна промисловість. Тоді величина х₁₁ показує вартість електроенергії, яку спожила 1-а галузь для своїх внутрішніх виробничих потреб. Величина x₁₂ відображає витрати вугілля при виробництві електроенергії. В цілому ж стовбець х₁₁, x₂₁, х₃₁,..., х_n₁ характеризує структуру матеріальних витрат за звітний рік в розрезі галузей- постачальників.

В балансі відображені не тільки матеріальні витрати, но і чиста продукція галузей. Так, чиста продукція 1-ї галузі характеризується сумою оплати праці v₁ та чистого доходу (прибутку) m₁. підсумок матеріальних витрат та чистої продукції дорівнює, очевидь, валової продукції галузі (наприклад, для першої галузі – величені Х₁). Таким чином, можна записати:

Х1=х₁₁+х₂₁+х₃₁+…+х_n1+v₁+m₁ = (8)

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

X (9)

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

Х₁ = х₁₁+х₁₂+х₁₃+ … +х_1т+y₁ =

тоді для будь-якої виробничої галузі

Х_i= (10)

Якщо порівняти ліву та праву частину рівнянь (9) та (10), то можна відмітити, що:

(11)

Вираз (11) показує, що в міжгалузевому балансі додержується принцип – єдність матеріального балансу та ватістного складу національного прибутку.

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

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

Квадрант III – характеризує національний дохід з боку його вартісного складу як суму оплати праці та чистого доходу усіх галузей матеріального виробництва.

Квадрант IV – відображення кінцевого розподілу та використання національного доходу.

Коефіціети прямих та побічних витрат.

(12)

- технологічні коєфіцієнти;

а_ij – коєфіцієнти прямих витрат

Прямі матеріальні витрати будемо називати витрати, обумовлені на кінцевому етапі виробництва.

Z_повн = Z_поб + Z_прям

З рівняння (12) маемо:

(13)

Тоді у формулу (10) підставимо x_ij:

Х_i= (14)

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

(15), де

а – матриця кофіціентів прямих витрат

Рівняння (15) можна переписати у матричному вигляді:

Е , (15^*)

де Е – единична матриця:

(16)

= А – матриця повних витрат. Тоді:

(17)

Вираз (17) можна представити в розгорнутій формі:

(18)

В загальному вигляді для любої галузі i маємо:

(19)

Матриця а зветься продуктивною, як щодля любого вектора Y існує рішення Х рівняння (16). В цьому випадку і модель Леонтьева зветься продуктивною. Існує де кілька критеріїв визначення продуктивності матриці а. Один з них говорить, що матриця а продуктивна, якщо максимум сум ії столбців не перевищує одиниці, причому хоча б для одного з столбців сума елементів строго менше одиниці.

Зауважимо, що система рівнянь даної задачі допускає тільки невід’ємні розв’язки. Достатні умови існування таких розв’язків через власні числа матриці а можна записати так: λ_max<1.

Питання для самоконтролю.

· В звязку з чим, виникла потреба при аналізі економічних систем в використанні математичного аппарату та обчислювальної техніки?

· Що таке математичне моделювання?

· Що таке модель?

· Признаки кваліфікації моделей?

· Які задачі вивчає математичне програмування?

· Що включає математична модель задачі МП?

· Постановка задачі ЛП.

· Постановка задачі НП.

· Назвіть типи програмування.

· Сформулюйте задачу про максимальну рентабільність підприємства.

· Сформумюйте задачу про завантаження обладнання.

· Що таке балансовий аналіз?

· Напішить матриці прямих, побічних та повних витрат.

· Сформулюйте достатні умови продуктивності матриці прямих витрат.

Тема 3.Загальна задача лінійного програмування та деякі зметодів її розв’язання

Лекція 2

Тема лекції: Основні теореми та властивості задач лінійного програмування (ЛП).

Мета: ознайомити студентів з основними теоремами та властивостями задач лінійного програмування, розібрати задачі МП, які розв’язуються графічним методом.

План лекції

1. Загальна задача ЛП.

2. Основні теореми та властивості задачі ЛП.

3. Графічний метод розв’язання задач МП.

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1. Загальна форма задачі лінійного програмування (ЛП).

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

f(x)= c₁x₁ + c₂x₂ + …. + c_nx_n→extr (max/min) (1)

a₁₁x₁+ a₁₂x₂ + a₁₃x₃ + ….. +a_1nx_n{ ≤ = ≥ }b₁

a₂₁x₁ + a₂₂x₂ + a₃₃x₃ + …..+ a_2nx_n{ ≤ = ≥ }b₂

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n{ ≤ = ≥ }b_k(2)

a_m.1x₁ + a_m.2x₂ + a_m.3x₃ + a_m.nx_n { ≤ = ≥ } b_m

x_i≥0 i= 1,m (3)

Отже, загальна задача ЛП є формою із змішаною системою обмежень.

Означення 2. Задача ЛП має канонічний вигляд, якщо в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді рівнянь та (3).

Означення 3. Задача ЛП має стандартний вигляд, якщо в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді нерівностей ≤ та (2.3), коли шукається max цільвої функції f, або в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді ≥ та (3), коли шукається min цільвої функції f.

Перейти від стандартного вигляду задачі ЛП можна за допомогою додовання невід’ємних змінних.

В теоретичному плані всі задачі ЛП можна розглядати тільки як задачі на мінімум чи на максимум, змінивши знак цільової функції:

f(x)=c₁x₁ + c₂x₂ + c₃x₃ + …… +c_nx_n→max

z(x) = - f(x) = -(c₁x₁ + c₂x₂ + c₃x₃ + …… +c_nx_n) →min

Система обмежень (2) – (3) може бути сумісною або несумісною. Сумісна система обмежень визначає в n-вимірному векторному просторі область визначеності задачі, інакше, область існування планів задачі ЛП. Кожна крапка області означеності є планом задачі, а сама область є множиною планів задачі ЛП.

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

Запишемо задачу ЛП в матричній формі:

f(x)=(c,x) →max (4)

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

АХ=В (5)

Х≥0 (6)

де (,) – скалярний добуток

А – матриця умов задачі

В – вектор обмежень (вектор вільних членів задачі)

Х – вектор невідомих змінних

С – вектор цільової функції.

RangA=k визначає кількість базових змінних (незалежних змінних), усі інші змінні вважаються вільними (залежними).

Рішення системи обмежень, у якому вільні змінні дорівнюють нулеві, зветься базовим планом.

Будь який невід’ємний розв’язок системи обмежень задачі ЛП зветься допустимим планом.

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

2. Основні теореми та властивості задачі ЛП.

Запишимо задачу ЛП в векторній формі:

F(x)=(c,x) →max (7)

x₁P₁ + x₂P₂ + x₃P₃ +…… + x_nP_n= P₀ (8)

X≥0 (9)

P₁= (a_11,a₂₁,а₃₁…….a_m1), P₂= (a₁₂_,a₂₂,а₃₂…….a_m2), ……….. P_n= (a_1n_,a_2n,а_3n…….a_nm),

P₀=(b₁,b₂, b_3……. b_m) – m-мерні вектор столбці.

Означення 4. План Х=(х₁,х₂,х₃…….х_n) називається опорним планом задачі ЛП, якщо система векторів Р_j,які відповідають додатним компонентам x_jплану Х, утворюють лінійно незалежну систему.

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

Означення 5. Нехай Х₁, Х₂, Х₃, ……, Х_n – вільні крапки евклідова простору R_n. Опуклою лінійною комбінацією цих крапок є сума λ₁Х₁+ λ₂Х₂+ λ₃Х₃+...... + λ_nХ_n, де λ_i≥0 та ∑ λ_i=1.

Означення 6. Множина U називається опуклою, якщо для будь яких n крапок Х₁, Х₂, …Xn є U, до U належить будь яка опукла комбінація цих крапок, тобто [ λ₁Х₁+ λ₂Х₂+ λ₃Х₃+...... + λ_nХ_n] є U, де λ_i≥0 та ∑ λ_i=1.

Означення 7. Крапка Х опуклої множини є кутовою, якщо ця крапка не може бути означена в вигляді опуклої лінійної комбінації яких не будь n крапок даної множини.

Теорема 1. Опуклий n – мірний многогранік є лінійною комбінацією своїх кутових крапок.

Теорема 2. Множина планів задачі ЛП є опуклою множиною, якщо вона не поржня.

Означення 8. Не поржня множина планів задачі ЛП називається многогранником розв’язків, а будь яка кутова крапка многогранника розв’язків – вершиною.

Теорема 3. Якщо задача ЛП має оптимальний план, то максимальнє значення цільова функція задачі приймає в одній із вершин многогранника розв’язків.

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

Теорема 4. (Критерій кутової крапки многогранника розв’язків). Для того щоб крапка Х=(х₁,х₂,х₃…..х_к,....... х_n), многогранника розв’язків була кутовою, небхіно і достатньо, щоб вектори Р_j, які відповідають додатним компонентам х_j, утворювали лінійно незалежну систему.

Висновки:

1. Не поржня множина задачі ЛП – опуклий многогранник.

2. Кожна вершина многогранника - опорний план.

3. В одній із вершині многогранника розв’язків цільова функція приймає максимальне значення.

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

3. Графічний метод розв’язання задач МП.

Загальна задача ЛП геометрично інтерпретується так: кожне k – те обмеження – рівність

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n= b_k(k=1,….m)

задає в n – вимірному просторі основних змінних х₁,х₂,х₃…..х_к,....... х_nгіперплощину, а кожне k – те обмеження – нерівність

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n ≤ b_k(k=1,….m), визначає деяку ггіперплощину та півпростір n – вимірного простору, що лежить на один бік від цієї гіперплощини. За умоми сумітності системи нерівностей (2) та (3), перетин усіх цих півпросторів як опуклих множин, утворює опуклий многогранник допустимих розв’язків. Кожна вершина цього многогранника розв’язків визначає опрний план.

Розглянемо геометричну інтерпритацію задачі ЛП для випадку n=2.

Задача 1. Розв ’ язати задачу ЛП графічно.

2х₁ + 3х₂≤12

2х₁ - х₂≤4

х₁,х₂≥0

а) z =3х₁ + х₂→max

b) z =х₁ + 5х₂→max

c) z =4х₁ + 6х₂→max

Алгоритм розв’язку задачі ЛП графічним методом

1. Побудова многогранника розв ’ язків.

Визначаємо область допустимих розв ’ язків (перетин півплощін, що відповідають, обмеженням задачі). Згідно з обмеженнями (3) многокутник розв ’ язків міститься у першому квадранті. Область допустимих розв ’ язків (ОДР) може бути поржньою множиною, опуклим многокутником або необмеженою многокутною опуклою областю.

У першому випадку задача ЛП не має розв ’ язків.

В другому – завжди існує точка (або точки), в яких цільова функція (1) набуває максимального або мінімального значення.

У третьому – лінійна функція (1) на ОДР може не досягти екстремуму.

Надалі, нехай ОДР не є порожньою множиною.

2. Будуємо вектор нормалі N=(c₁,c₂). Вектор нормалі вказує на напрямок зростання цільової функції (1).

3. Проводимо перпендикулярно до вектора нормалі N=(c₁,c₂) лінію рівня.

4. Визначення оптимальних крапок.

Для знаходження крапки максимуму цільової функції зміщуємо лінію рівня паралельно самій собі у напрямку вектора нормалі N доти, доки пряма не стане опорною до множини ОДР.

5. Обчислення оптимальних значень.

Для цього знаходимо координати вершин, в яких досягається максимум (мінімум) цільової функції (1) та обчислюємо ці значення.

У загальному вигляді задача МП з двома змінними формулюється таким чином:

Z=f(x₁, x₂) →max/min (10)

За умов

g_k(x₁,x₂)≤ b_kк=1,2,......m (11)

x₁,x₂≥0 (12)

де f та g_k можуть бути лінійними або нелінійними.

При розв’язанні задачі (10) – (12) графічним методом важливим є поняття лінії рівня цільової функції.

Лінія рівня цільової функції називається така множина значень іі змінних, при яких функція набуває сталого значення f(x₁, x₂)=c:

- для лінійної функції f(x₁, x₂)=c=const – паралельні прямі;

- для квадратичної функції f(x₁, x₂)=(х₁)²+(х₂)²=c =const – концентричні кола різних радіусів r=(c)^1/2;

- для f(x₁, x₂)=a(х₁)²+b(х₂)²=c =const – концентричні еліпси.

Алгоритм знаходження розв’язку задачі МП графічним методом.

1. Знаходимо ОДР.

2. Будуємо лінії рівня цільової функції f(x₁, x₂)=c.

3. Визначаємо лінії рівня найвищого (найнижчого) рівня або встановлюємо нерозв’язність задачі із-за необмеженості цільової функції зверху (знизу) на ОДР.

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

Питання для самоконтролю.

· Сформулюйте задачу ЛП в загальній формі.

· Сформулюйте задачу ЛП в канонічній формі.

· Сформулюйте задачу ЛП в стандартній формі.

· Запишіть задачу ЛП в матричній формі.

· Запишіть задачу ЛП в векторній формі.

· Дайте означення опорного плану задачі ЛП.

· Дайте означення опуклої множини.

· Дайте означення кутової точки.

· Дайте означення області допустимих розв’язків.

· Сформулюйте критерій кутової крапки многогранника розв’язків.

· Як визначити кількість базових змінних?

· Дайте означення базових та вільних змінних.

· Дайте означення допустимого плану.

· Дайте означення оптимального плану.

· Що таке вектор нормалі цільової функції?

· Дайте означення лінії рівня цільової функції.

Тема 3.Загальна задача лінійного програмування та деякі з методів її розв’язання

Лекція 3

Тема лекції: Вирішення задач ЛП симплекс-методом.

Мета: ознайомити студентів з методами розв’язання задач ЛП симплекс – методов, методом штучного базису.

План лекції

1. Представлення задач ЛП в матричній та векторній формі.

2. Симплексний метод розв’язання задач ЛП.

3.Теоретичні основи симплекс-метода.

4. Метод штучного базису.

Література:

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1. Представлення задач ЛП в матричній та векторній формі.

f(x)= c₁x₁ + c₂x₂ + …. + c_nx_n→extr (max/min) (1)

a₁₁x₁+ a₁₂x₂ + a₁₃x₃ + ….. +a_1nx_n{ ≤ = ≥ }b₁

a₂₁x₁ + a₂₂x₂ + a₃₃x₃ + …..+ a_2nx_n{ ≤ = ≥ }b₂

a_k1x₁ + a_k2x₂ + a_k3x₃ + …….+ a_knx_n{ ≤ = ≥ }b_k(2)

a_m.1x₁ + a_m.2x₂ + a_m.3x₃ + a_m.nx_n { ≤ = ≥ } b_m

x_i≥0 i= 1,m (3)

Запишемо задачу ЛП в матричній формі:

f(x)=(c,x) →max (4)

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

АХ=В (5)

Х≥0 (6)

де (,) – скалярний добуток

А – матриця умов задачі

В – вектор обмежень (вектор вільних членів задачі)

Х – вектор невідомих змінних

С – вектор цільової функції.

Запишимо задачу ЛП в векторній формі:

F(x)=(c,x) →max (7)

x₁P₁ + x₂P₂ + x₃P₃ +…… + x_nP_n= P₀ (8)

X≥0 (9)

P₁= (a_11,a₂₁,а₃₁…….a_m1), P₂= (a₁₂_,a₂₂,а₃₂…….a_m2), ……….. P_n= (a_1n_,a_2n,а_3n…….a_nm),

P₀=(b₁,b₂, b_3……. b_m) – m-мерні вектор столбці.

2. Симплексний метод розв ’ язання задач ЛП. Теоретичні основи симплекс-метода.

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

Розглянемо два різновиди симплексного метода:

· Симплекс – метод із стандартним базисом;

· Симплекс метод із штучним базисом (М- метод).

Симплекс – метод із стандартним базисом

Для застосування цього методу розглянемо задачу ЛП у канонічному вигляді

Z=∑c_ix_i →max

за умов

х₁e₁+ х₂e₂+ х₃e₃ + ….. + х_me_m + х_m₊₁P_m₊₁ + ….. + х_nP_n=P₀, де

e_i – одиничні вектори, P_k = (a₁_k, a₂_k,….. a_mk) (k=m+1,m+2,…. n), P₀ = (b₁, b₂,… b_m)

Оскільки перші m векторів е_i одиничними, то легко бачити, що виконується рівність

b₁e₁+ b₂e₂+ b₃e₃ + ….. + b_me_m =P₀.

Тоді очевидним є початковий опорний план: X=(b₁,b₂,b₃, ….. b_m, 0….0), який перевіряємо на оптимальність. Для цього заповнюємо симплексну таблицю.

Таблиця 1.

i	базис	С_баз	Р₀	c₁	c₂	…	с_m	c_m+1	…	c_n
P₁	P₂		P_m	P_m+1	…	P_n
	P₁	c₁	b₁					a_1m+1	…	a_1n
	P₂	c₂	b₂					a_2m+1	…	a_2n
…	…	…	...					…	…	…
m	P_m	с_m	b_m					a_mm+1	…	a_mn
		Δ_j						Δ_m+1	…	Δ_n

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

Δ_j=∑c_ia_ij – c_j, (j=1,2, …. n) і Δ₀=∑c_ib_i_.Останній рядок називається індексним_.

Отриманий план перевіряють на оптимальність, зміст якої розкривається у наступних теоремах.

3. Теоретичні основи симплекс-метода.

Теорема 1.

Якщо для деякого вектора P_j, який не входить у базис, виконується умова

Δ_j<0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j>0, (j=1,2,3…..n) (для задачі на мінімум),

то можна отримати новий опорний план, для якого значення цільової функції f(x) буде більше (якщо f(x)→max),або менше (якщо f(x)→min) вихідного; при цьому можуть бути два випадки:

а) якщо координати вектора P_j, який необхідно ввести у базис, недодатні, то задача ЛП не має розв’язку;

б) якщо існує хоча б одна додатня координата вектора P_j, який необхідно ввести у базис, то можна отримати новий опорний план.

Теорема 2.

Якщо для всіх векторів P_j_,виконується умова

Δ_j≥0, (j=1,2,3…..n) (для задачі на максимум)

або

Δ_j≤0, (j=1,2,3…..n) (для задачі на мінімум),

то опорний план Х^*=((х₁)^*, (х₂)^*,......... (х_n)^*) є оптимальним.

Якщо після побудови симплекс-таблиці виявилось, що виконуються умови Т.1 (пункт а)), або Т.2 розв’язання задачі припиняється. Якщо виконуються умови Т.1 (пункт б)), то потрібно перейти до нового оптимального опорного плану, побудувавши наступну симплексну таблицю. Для переходу до нового опорного плану треба один вектор вивести з базису і на його місце ввести новий вектор, який не належить базису. У базис вводять вектор, якому відповідає найбільша за абсолютною величиною від’ємна оцінка Δ_j. Нехай існує така оцінка в k- му стовпці, тобто max| Δ_j | = Δ_k_.

Δ_j≤0

Тоді вектор Р_к вводимо у новий базис. Для знаходження вектора Р_r, який необхідно вивести, обчислюють співвідношення

Q= min(b_i/a_ik) (i=1,2…..m),

мінімальне значення якого досягається при i=r. Елемент a_rk називається розв’язувальним.

Рядок Р_r і стовпець Р_кна перетині яких знаходиться розв ’ язувальний елемент a_rk, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса.

Метод штучного базису.

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

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

У цільовій функції задачі ЛП штучні змінні мають коефіцієнт - М (f(x)→max) або +М (f(x)→min), де під М ми розуміємо досить велике додатне число.

При розв’язанні цієї задачі симплекс-методом оцінки Δ_j будуть залежити від М. Для порівняння оцінок, треба пам’ятати, що М – достатньо велике додатне число, тому із базису будуть виключатися у першу чергу штучні вектори.

Якщо із базису всі штучні вектори вийшли, то ми отримали вихідну задачу.

Якщо оптимальний розв’язок М – задачі містить штучні змінні або М – задача нерозв’язна, то початкова задача також нерозв’язна.

Питання для самоконтролю.

· В чому полягає симплекс-метод із стандартним базисом?

· Коли використовують симплекс-метод зі штучним базисом?

· Принципи заповнення симплекс-таблиці.

· Що таке розв’язувальний елемент симплекс-таблиці?

· Як перевірити опорний план на оптимальність?

· Поясніть метод Жордана-Гауса.

· Що таке штучні змінні?

Лекція 4

Тема лекції: Транспортна задача

Мета: ознайомити студентів з основними теоремами та методами розв’язання транспортної задачі

План лекції

1. Економічна та математична моделі транспортної задачі.

2. Основні теореми транспортної задачі.

3. Метод північно-західного кута (діагональний).

4. Метод найменших витрат.

5. Метод потенціалів.

Література:

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1 Економічна та математична моделі транспортної задачі.

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

У загальному вигляді транспортну задачу можна сформулювати так: в m пунктах постачання А₁, А₂,…… A_m (надалі постачальники) міститься однорідна продукція у кількості відповідно а₁, а₂,….. а_m_. Цю продукцію потрібно перевезти в n пункти призначення B₁, B₂,…… B_n (надалі споживачі) у кількості відповідно b₁, b₂,….. b_n_.Вартість перевезення одиниці товару (тариф) із пункту А_i в пункт B_j дорівнює с_ji_.

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

F(x_ji)= ∑∑ x_ji с_ji_→ min (1)

за умов

∑x_ji =a_i (i=1,2…..m) (2)

∑x_ji =b_j (j=1,2…..n) (3)

x_ji≥0 (i=1,2…..m; j=1,2…..n) (4)

Алгоритм і методи розв’язання транспортної задачі можна використати для знаходження розв’язку деяких економічних задач, які не мають нічого спільного з транспортуванням вантажів. У цьому разі величини тарифів перевезення с_ji мають різний зміст залежно від конкретної задачі. До таких задач належать наступні:

· Оптимальне закріплення за верстатами операцій з обробки деталей. У них с_ji означає продуктивність праці.

· Розміщення сільськогосподарських культур за ділянками землі різної врожайності.

· Оптимальні призначення або проблема вибору.

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

· Збільшення продуктивності автомобільного транспорту за рахунок мінімізації порожнього пробігу

2 Основні теореми транспортної задачі.

Означення 1. Якщо у транспортної задачі виконується умова балансу

∑b_j = ∑a_i (5)

То задача називається закритою або збалансованою.

Означення 2. Планом транспортної задачі називається сукупність величин x_ji (i=1,2…..m; j=1,2…..n), який задовольняє умови обмеження (2) – (4).

Означення 3. Опорний план транспортної задачі називається не виродженим, якщо він містить N=m+n-1 додатних елементів x_ji

Означення 4. Якщо опорний план містить менше N<m+n-1 додатних елементів, то він називається виродженим.

Означення 5. Оптимальним планом транспортної задачі називають матрицю Х^*, яка задовольняє умови задачі (2) – (4) і для якої цільова функція F набуває мінімального значення.

Теорема 1. (Необхідна і достатня умова існування розв’язку задачі ТЗ).

Транспортна задача має розв’язок тоді і тільки тоді, коли вона збалансована, тобто виконується умова (5).

Теорема 2. Для того щоб деякий план Х транспортної задачі був оптимальним необхідно і достатньо, щоб йому відповідала така система із m+n чисел u_i (i=1,2…..m) v_j (j=1,2…..n) для якої виконуються умови

v_j - u_i = с_ji для x_ji>0

v_j - u_i ≤ с_ji для x_ji=0.

Означення 6. Числа v_j та u_i називаються потенціалами строк та стовпців.

3. Метод північно-західного кута (діагональний.)

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

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

Зауважемо, що користуючись методом північно-західного кута початковий опорний план залежить від величин a_i та b_j і зовсім не залежить від вартостей перевезення с_ji_,а тому він буде далекий від оптимального.

4. Метод найменшої вартості.

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

5. Метод потенціалів.

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

v_j - u_i = с_ji для x_ji>0 (6)

Оскільки заповнених клітинок є m+n-1, то система рівнянь (6) із m+n невідомих містить m+n-1 рівнянь. Прийнявши одне невідоме за нуль, наприклад, u₁=0, решту знаходимо.

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

Δ_ji =v_j - u_i - с_ji

Якщо, Δ_ji ≤0, то побудований опрний план є оптимальним.

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

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

Означення 7. Циклом у транспортної задачі називають замкнену ламану лінію, вершини якої розміщуються в заповнених клітинках таблиці, а сторонни проходять уздовж рядків і стовпчиків таблиці.

Для вибраної вільної клітинки і клітинок, що пов’язані з нею циклом, здійснюють перерозподіл продукції в межах цього циклу за такими правилами:

· Кожній вершині циклу приписують певний знак, причому вільній клітинці – знак «+», а всім іншим по черзі- знаки «-» та «+»;

· У поржню клітинку переносять менше з чисел x_ji, що стоять у клітинках зі знком «-». Одночасно це число додають до відповідних чисел, які розміщені в клітинках зі знаком «+».

Приклад. Розв’язати транспортну задачу.

						u_i






v_j

Питання для самоконтролю.

· Чому транспортну задачу вирішують іншими методами, якщо це задача лінійного програмування?

· Яка транспортна задача називається закритою?

· Що робити якщо транспортна задача відкрита?

· Дайте означення опорного плану транспортної задачі.

· Коли опорний план транспортної задачі не вироджений?

· Що робити, якщо опорний план транспортної задачі вироджений?

· Дайте означення оптимального опорного плану транспортної задачі.

· Сформулюйте необхідні і достатні умови існування розв’язку транспортної задачі.

· Як построїти потенціали строк і стовпців?

· В чому полягає метод північно-західного кута?

· В чому полягає метод найменших витрат?

· Як визначити, що опорний план оптимальний?

· Дайте означення циклу перерозподілу поставок.

Тема 4. Теорія двоїстості та аналіз лінійних моделей оптимізаційних задач.

Лекція 5.

Тема лекції: Двоїста задача лінійного програмування

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

План лекції

1. Математичні моделі двоїстих задач.

2. Основні теореми теорії двоістості.

3. Взаємозв’язок розв’язків прямої та двоїстої задач.

Література:

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1 Математичні моделі двоїстих задач.

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

Початкова задача називається прямою задачею ЛП. Ці дві задачі тісно пов’язані між собою і утворюють єдину пару двоїстих задач.

Якщо пряма задача ЛП має вигляд:

Z=∑c_ix_i →max (1)

за умов

∑a_ijx_j ≤b_i, (i=1,2…..m) (2)

x_j ≥0 (j=1,2…..n) (3)

то двоїста задача записується так:

F=∑b_iy_i →min (1*)

за умов

∑a_ijy_i≥ c_j, (j=1,2…..n) (2*)

y_i≥0 (i=1,2…..m) (3*)

В матричному вигляді їх можна представити таким чином:

Пряма задача

, x_j ≥0 (j=1,2…..n)

де А – матриця системи обмежень задачі розміром m x n;

В – вектор стовпець;

С – вектор строка;

АХ≤В;

Z →max.

Двоїста задача

tr = , y_i ≥0 (i=1,2…..m)

де trA – транспонована матриця А;

trС – транспонований вектор С;

trB - транспонований вектор В;

AY ≥trC;

F →min.

У несиметричних парах двоїстих задач обмеження прямої задачі можуть бути записані як рівняння (у канонічному вигляді), а двоїстої – лише як нерівності. Якщо у цільовій функції двоїстої задачі вимагається знайти мінімум, то система обмежень матиме знак «≥», якщо максимум, то знак «≥».

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

Пряма задача	Двоїста задача
Z=∑c_ix_i →max/min за умов ∑a_ijx_j =b_i, (i=1,2…..m) x_j ≥0 (j=1,2…..n)	F=∑b_iy_i →min/max за умов ∑a_ijy_i≥/≤ c_j, (j=1,2…..n) y_i є(-∞,∞) (i=1,2…..m)

Математична модель прямої задачі мішаної пари двоїстих задач містить обмеження, записані як рівняння, так і нерівності, причому знаків різних, за виглядом. Для складання двоїстої задачі необхідно привести всі нерівності системи обмежень прямої задачі до одного вигляду: якщо пряма задача на максимум, то всі нерівності обмежень приводимо до вигляду «≤», якщо на мінімум до вигляду «≥». Нерівності, для яких дані вимоги не виконуються, домножимо на (-1).

2. Основні теореми двоїстості.

Розглянемо пару даоїстих задач, утворену канонічною задачею ЛП і двоїстої до неї:

Пряма:

Z=∑c_ix_i →max/min

за умов

∑a_ijx_j =b_i, (i=1,2…..m)

x_j ≥0 (j=1,2…..n)

Двоїста:

F=∑b_iy_i →min/max

за умов

∑a_ijy_i≥/≤ c_j, (j=1,2…..n)

y_i є(-∞,∞) (i=1,2…..m)

Між прямою і двоїстою задачами ЛП існує тісний взаємозв’язок, який видно з наведених далі лем та теорем.

Лема 1. Якщо Х – деякий план прямої задачі, Y – довільний план двоїстої задачі, то значення цільової функції прямої задачі при плані Х не перевищує значення цільової функції двоїстої задачі при плані Y, тобто

Z(X)≤F(Y)

Лема 2. Якщо Z(X*)=F(Y*), та X* - оптимальний план прямої задачі, то Y* - оптимальний план двоїстої задачі.

Теорема 1. (перша теорема двоїстості). Якщо одна із пар двоїстих задач має оптимальний план, то і друга задача має оптимальний план і значення цільової функції при їх оптимальних планах рівні між собою, тобто Z(X*)=F(Y*).

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

Теорема 2. (друга теорема двоїстості). Для того щоб плани Х* і Y* відповідно до задач (1) – (3) і (1*) – (3*) були оптимальними планами цих задач, необхідно і достатньо, щоб для кожного j (j=1,2…..n) виконувалась рівність:

(a₁_j(y₁)* + a₂_j(y₂)* + ……. + a_mj(y_m)* - c_j)(x_j)* = 0

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

Z=∑c_ix_i →max

за умов

∑a_ijx_j =b_i, (i=1,2…..m)

x_j ≥0 (j=1,2…..n)

Двоїста задача до неї буде така:

F=∑b_iy_i →min

за умов

∑a_ijy_i≥ c_j, (j=1,2…..n)

y_i ≥0 i=1,2…..m

Приклад. Підприємство виготовляє три види продукції А,В,С.

Дані задачі приведені у таблиці:

Види сировини	Норми витрат сировини (кг)	Запаси сировини
А	В	С
S₁
S₂
S₃
Ціна від реалізації 1-ї одиниці продукції

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

3 Взаємозв’язок розв’язків прямої та двоїстої задач.

Розглянемо пару двоїстих задач ЛП (1) – (3) і (1)* - (3)*, пряма задача якої записана у канонічному вигляді. Наступна теорема встановлює взаємозв’язок між розв’язками прямої і двоїстої задачами.

Теорема 3. Якщо пряма задача ЛП має оптимальний план Х*, отриманий симплекс методом, то оптимальний план Y* двоїстої задачі визначається за формулою:

Y*=C_базР^-1 (4)

де C_баз– вектор рядок, що складається з коефіцієнтів цільової функції прямої задачі при невідомих, які є базисними в оптимальному плані; Р^-1 – матриця, обернена до матриці Р, складеної з компонент базисних векторів оптимального плану задачі.

Таким чином, якщо знайти симплекс методом оптимальний план задачі (1) –(3), то використовуючи останню симплекс таблицю, можна визначити C_базі Р^-1та за допомогою співвідношення (5.4), знайти план двоїстої задачі.

Відмітимо, що існує взаємно-однозначна відповідність між змінними: основним змінним прямої задачі відповідають додаткові змінні двоїстої задачі і навпаки:

Змінні прямої задачі
Основні	Додаткові
Х₁	Х₂	……..	Х_к	Х_к+1	Х_к+2	……….	Х_n
Y_n-k+1	Y_n-k+2	……..	Y_n	Y₁	Y₂	………	Y_n-k
Додаткові	Основні
Змінні двоїстої задачі

Ідея двоїстого симплексного методу полягає у зв’язку між розв’язуваннями прямої та двоїстої задач ЛП. Немає потреби окремо розв’язувати пряму задачу, а окремо двоїсту, оскільки розв’язок обох задач можна знайти за одними й тими самими симплекс таблицями, пам’ятаючи, що невідомим прямої задачі відповідають стовпчики таблиці, а невідомим другої – рядки таблиці.

Двоїстий симплекс метод використовується для знаходження розв’язку задачі ЛП, записаної у канонічному вигляді, для якої серед векторів Р_j, складених з коефіцієнтів при невідомих у системі рівнянь, є рівно m одиничних.

Також цей метод можна використовувати для знаходження розв’язку задач ЛП, коли вільні члени системи рівнянь є довільними числами (для розв’язування задач симплекс методом числа b_i припускались невід’ємними).

Питання для самоконтролю.

· Нехай є задача про оптимальне використання ресурсів. Дайте економічну інтерпретацію двоїстої задачі.

· Сформулюйте першу теорему двоїстості.

· Сформулюйте другу теорему двоїстості.

· Перечисліть ознаки взаємно двоїстих задач.

· Як по рішенню прямої задачі знайти рішення двоїстої задачі.

· В чому полягає ідея двоїстого симплекс методу.

· Який економічний зміст основних змінних двоїстої задачі?

· Який економічний зміст додаткових змінних двоїстої задачі?

· Який економічний зміст перевірки системи обмежень прямої задачі для знайденого оптимального плану?

· Що дає перевірка обмежень двоїстої задачі?

· Як проводиться аналіз стовбців останньої симплекс таблиці, для яких Δ_i>0?

Тема 5. Цілочислові та параметричні задачі лінійного програмування

Лекція 6.

Тема лекції: Узагальнення задачі лінійного програмування.

Мета: ознайомити студентів з методами розв’язання задач цілочислового та параметричного програмування.

План лекції

1. Задачі цілочислового програмування.

1. Метод Гоморі.

2. Параметричне лінійне програмування.

Література:

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

1. Задачі цілочислового програмування.

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

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

Задача цілочислового програмування формулюється так:

Z= (1)

за умов

,= b_i, i= , (2)

x_j≥0, (j= ), (3)

x_j - цілі, (j= ), (4)

умова цілочисельності (4), яка додається до звичайної задачі ЛП, суттєво ускладнює її розв’язання.

2. Метод Гоморі.

Сутність методу Гоморі (метод відтинання) полягає у тому, що спочатку розв’язується звичайна задача ЛП без урахування вимог цілочисельності змінних. Якщо отриманий оптимальний план задачі цілочисловий, то задача розв’язана. У протилежному випадку у модель вводиться спеціальне додаткове обмеження, що враховує цілочисельність змінних і володіє такими властивостями:

- вона повинна бути лінійною;

- вона повинна відтинати знайдений оптимальний нецілочисловий план задачі;

- не повинна відтинати ні одного цілочислового плану.

Додаткове обмеження, що має перелічені вище властивості, називається правильним відтинанням.

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

де - дробова частина числа,

=а-[a].

[a] – ціла частина числа а, т.б. найбільше ціле число, яке не перевищує числа а.

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

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

Розглянемо метод Гоморі на прикладі.

Приклад 1.

за умов