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

Нехай підприємству задано план виробництва продукції за часом і номенклатурою: треба за час Т виготувати 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_1kx_1k+a_2kx_2k+………………+a_mkx_mk ≤ n_k

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

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

L= b_1kx_1k+b_2kx_2k+……+b_mkx_mk →min (7)

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

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

Приклад 3.

Інвестиційна компанія має на своєму рахунку 5 млн. грн. Розглядаються чотири види інвестицій – державні цінні папери, цінні папери корпорацій, акції сфери обслуговуння та акції виробничої сфери. Державні цінні папери належать до без ризикових, решта інвестицій – до ризикових. Метою інвестиційної компенії є максимізація прибутку. Прибуток від інвестицій становить відповідно – 5%, 8%, 10% та 12%. Гроші які не інвестуються, залишаються на банківському рахунку і дають прибуток 1%. Менеджер з інвестицій ухвалив рішення, що не менше ніж 2 млн. грн. слід розмістити у цінні папери корпорацій, а в інвестиційні проект из елементами ризику потрібно вкласти не більше ніж 4 млн. грн.

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

 

 

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

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

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

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

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

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

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

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

 

Тема 1. Предмет, методи і завдання дисципліни. Класифікація задач.

Лекція 2

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

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

 

План лекції

 

1. Задачі математичного програмування.

2. Класифікація методів математичного програмування.

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

 

Література:

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

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

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

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

 

1. Задачі математичного програмування.

Задачі математичного програмування – це задачі на знаходження екстремальних значень деяких функціональних залежностей.

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

В загальному вигляді математична постановка екстремальної задачі полягає в пошуку максимального або мінімального значення функції цілі f(x) при умовах g_i(x)≤b_i, дє f та g_i – задані функції, а b_i – деякі дійсні числа.

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

Економічні можливості формалізуються у вигляді системи обмежень. Всі ці умови складають математичну модель задачі.

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

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

1. Сукупність незалежних величин Х = (х₁,х₂,х₃…….х_n) діючі на яку, систему можна змінити. Їх називають планом задачі (вектором управління, рішенням, стратегією)

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

3. Умови (або система обмежень), накладені на невідомі величини. Ці умови випливають з обмежень ресурсів, якими володіє товариство в будь-який момент часу, з необхідності задовольнити поточні потреби, з умов виробничих та технологічних процесів. Обмеженнями є не тільки матеріальні, фінансові та трудові ресурси. Такими можуть бути можливості технічного, технологічного та взагалі наукового потенціалу. Математично обмеження існують у вигляді рівнянь та нерівностей. Їх сукупність є множиною планів задачі.

2. Класифікація методів математичного програмування.

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

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

Засновником ЛП є радянський математик-економіст Л.В. Канторовіч. (1939 р. наукова праця „Математичні методи організації та планування виробництва”).

Через 10 років американський математик Дж. Данціг розробив ефективний спосіб рішення даного класу задач – симплекс-метод. Вперше термін ЛП з’явився в 1951 році в працях Дж. Данціга та Т. Купманса.

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

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

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

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

В усіх наведених раніше розділах МП інформація звісна та достовірна. Такі методи оптимізації звуться детермінованими або методами існування рішень в умовах визначеності.

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Виробнича галузь	Споживча галузь	Продукція, тис.грн.
			j	N	Кінцева	Валова
	x11	x12	x13	…	x1n	y1	X1
	x21	x22	x23	…	x2n	y2	X2
	x31	x32	x33	…	x3n	y3	X3
I	…	…	…	…	…	...	…
N	xn1	xn2	xn3	…	xnn	yn	Xn
Оплата праці	v1	v2	v3	…	vn	vкін	-
Чистий дохід, тис. грн.	m1	m2	m3	…	mn	mкін	-
Валова продукція, тис. грн.	X1	X2`	X3	…	Xn	-	X

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

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

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

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

X (2)

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

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

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

Х_i= (3)

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

(4)

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

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

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

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

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

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

(5)

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

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

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

 

 

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

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

(6)

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

Х_i= (7)

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

(8), де

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

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

Е , (8^*)

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

(9)

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

(10)

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

(11)

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

(12)

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

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

 

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

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

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

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

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

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

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

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

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

 

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

Лекція 3

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

 

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

 

План лекції

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) у вигляді нерівностей ≤ та (3), коли шукається max цільвої функції f, або в загальній формі задачі ЛП присутні тільки обмеження (2) у вигляді ≥ та (3), коли шукається min цільвої функції f.

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

Приклад 1. Записати в канонічній формі задачу ЛП:

Приклад 2. Записати в канонічній формі задачу ЛП:

Приклад 3. Записати в канонічній формі задачу ЛП:

 

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

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-вимірному векторному просторі область визначеності задачі, інакше, область існування планів задачі ЛП. Кожна крапка області означеності є планом задачі, а сама область є множиною планів задачі ЛП.

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

2. Форми запису загальної задачі ЛП.

Якщо скористатися позначеннями:

- вектор (матриця-стовпець) змінних;

- вектор (матриця-стовпець) вільних членів;

- матриця коефіцієнтів при змінних х₁, х₂, …, х_n;

; ;…. - вектор-стовбці матриці А;

- вектор (матриця - рядок) коефіцієнтів при змінних у цільовій функції, - вектори – рядки матриці А, то канонічну форму задачі ЛП можна записати у вигляді:

· скалярно-векторному виді:

· матричному виді:

,

,

· векторному вигляді:

.

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

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

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

АХ=В (5)

Х≥0 (6)

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

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

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

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

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

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

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

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

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

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

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

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_12,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. Якщо, максимальне значення цільова функція приймає більш ніж в одній вершині – тоді таке ж значення цільова функція приймає і в лінійній комбінації цих вершин.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

Лекція 4

Тема лекції: Графічний метод розв’язування задач ЛП.

 

Мета: ознайомити студентів з графічми методом вирішення задачі ЛП

 

План лекції

1. Графічиний метод розв’язування задач ЛП з n=2.

2. Графічний метод розв’язування задач ЛП з n≥2 (n-m=2).

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

 

Література:

 

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

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

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

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

 

 

1. Графічний метод розв’язання задач ЛП n=2.

Загальна задача ЛП геометрично інтерпретується так: кожне 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 – вимірного простору, що лежить на один бік від цієї гіперплощини. За умоми сумітності системи нерівностей задачі ЛП, перетин усіх цих півпросторів як опуклих множин, утворює опуклий многогранник допустимих розв’язків. Кожна вершина цього многогранника розв’язків визначає опрний план.

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

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

2х₁ + 3х₂≤12

2х₁ - х₂≤4

х₁,х₂≥0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Графічний метод розв ’ язування задачі ЛП можна застосовувати і у випадку, коли система обмежень містить n невідомих і m незалежних рівнянь, але при цьому n-m=2.

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

(1)

за умов

(2)

(3)

При цьму припускаємо, що всі рівняння системи (2) лінійно-незалежні та виконується умова n-m=2.

Означення. Будь які m змінних системи лінійних рівнянь з n змінними (n>m) називаються базисними (основними), якщо визначник матриці коефіцієнтів при них не дорівнює нулю. Тоді решта змінних (n-m) називаються вільними (неосновними).

Нехай в системі (2) змінні є базисними змінними, тобто відмінним від нуля є визначник

(4)

Тоді - вільні змінні. Систему (2) можна записати у вигляді:

(5)

Оскільки вільні змінні x_m+1,x_m+2 можуть приймати довільні значення, то система (5) має нескінченну множину розв’язків.

Проводимо методом Жордана-Гаусса m виключень, тоді система обмежень (5) приймає вигляд:

(6)

Таким чином, базисним змінним після перетворень Жордана-Гаусса відповідають одиничні лінійно незалежні вектори

; ;….

Які утворюють одиничний базис у m – вимірному просторі.

Після підстановки (6) у (1) одержимо цільову функцію

,

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

(7)

за умов

(8)

(9)

Представлена задача, очевидно, може бути розв’язана графічним методом.

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

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

за умов

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

· Дайте геометричну інтерпретацію задачі ЛП.

· Чи можна в лінійній моделі замінюючи знаки обмежень ≤ або ≥ на знак = поліпшити значення цільової функції?

· В якій точці многогранника розв’язків лінійна цільова функція задачі ЛП досягає оптимального значення?

· Чи може у задачі ЛП із двома змінними цільова функція приймати однакові значення у двох різних екстремальних точках?

· Запишіть алгоритм розв’язання задачи ЛП графічним методом.

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

Лекція 5

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

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

План лекції

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

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

3. Поняття виродженності задач ЛП.

Література:

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

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

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

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

 

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

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

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

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

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

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

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

 

Z=∑c_ix_i →max

за умов

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

e_i – одиничні вектори, P_k = (a_1k, a_2k,….. 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	базис	Сбаз	Р0	c1	c2	…	сm	cm+1	…	cn
P1	P2		Pm	Pm+1	…	Pn
	P1	c1	b1					a1m+1	…	a1n
	P2	c2	b2					a2m+1	…	a2n
…	…	…	...					…	…	…
m	Pm	сm	bm					amm+1	…	amn
		Δj						Δm+1	…	Δn

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

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

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

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

Теорема 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, називають розв’язувальним. Для перерахунку елементів нової (наступної) симплекс – таблиці користуються методом Жордана – Гауса.

3. Поняття виродженності задач ЛП.

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

При використанні симплекс-методу вважалося, що всі вільні члени >0, () додатні як у вихідній системі обмежень, так і в системах обмежень, які одержуємо після чергових ітерацій. Якщо в деяких рівняннях вільні члени дорівнюють нулю, то у відповідному цій системі опорному плані базисні змінні приймають нульові значення. Опрний план, у якому хочаб одна з базисних змінних дорівнює нулю, називається виродженим. Задача ЛП, яка має хоча б один вироджений опорний план, називається виродженою задачею ЛП.

Вироджений опорний план може бути або початковим або виникнути у процесі розв’язання задачі.

Приклад 1.

За початковий базис можна вибрати Р₁, Р₄, Р₅ або Р₂, Р₄, Р₅, тоді початковий опорний план Х=(0,0,0,1,1) є виродженим, так як базисна змінна х₁=0 або х₂=0. Для обох початкових планів z=0, тобто у випадку виродженності значення цільової функції може повторюватись навідь при зміні базису.

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

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

Оскільки число наборів векторів скінченне, то після деякого числа ітерацій дійдемо до одного з висновків:

1. розв’язок оптимальний;

2. задача не розв’язувана;

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

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

Лекція 6

Тема лекції: Розв’язання задач ЛП симплекс-методом (продовження)

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

План лекції

4. Правило уникнення зациклювання при застосуванні симплекс-методу.

5. Метод штучної базиси розв’язування задач ЛП.

6. Приклад вирішення задачі ЛП методом штучної бази.

 

Література:

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

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

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

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

 

 

4. Правило уникнення зациклювання при застосуванні симплекс-методу.

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

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

Приклад 2. Вирішити задачу ЛП

за умов

5. Метод штучної базиси розв’язування задач ЛП.

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

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

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

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

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

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

6. Приклад вирішення задачі ЛП методом штучної бази.

Інвестиційна компанія має на своєму рахунку 5 млн. грн. Розглядаються чотири види інвестицій – державні цінні папери, цінні папери корпорацій, акції сфери обслуговуння та акції виробничої сфери. Державні цінні папери належать до без ризикових, решта інвестицій – до ризикових. Метою інвестиційної компенії є максимізація прибутку. Прибуток від інвестицій становить відповідно – 5%, 8%, 10% та 12%. Гроші які не інвестуються, залишаються на банківському рахунку і дають прибуток 1%. Менеджер з інвестицій ухвалив рішення, що не менше ніж 2 млн. грн. слід розмістити у цінні папери корпорацій, а в інвестиційні проект из елементами ризику потрібно вкласти не більше ніж 4 млн. грн.

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

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

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

· Поясніть основну ідею симплекс-методу.

· Як визначити початковий опорний план задачі ЛП?

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

· Як визначається вектор для введення у базис, якщо опорний план неоптимальний?

· Як визначається вектор, що виводиться із базису?

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

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

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

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

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

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

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