Математичне програмування в економiцi

Математичне програмування

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

Математичне програмування тАУ математична дисциплiна, яка займаiться вивченням методiв розвтАЩязування, аналiзу та використання задач зi знаходження екстремуму функцii на множеннi допустимих варiантiв функцii. Математичне програмування використовують при розвтАЩязаннi рiзноманiтних практичних задач, у тому числi i економiчних.

Загалом послiдовнiсть використання економiко-математичних моделей така:

- формуiться економiчна проблема;

- створюiться математична модель задачi, у якiй логiчнi звтАЩязки економiчноi моделi перетворюються на математичнi спiввiдношення: функцii. рiвняння, нерiвностi;

- розвтАЩязуiться математична задача, перевiряiться рiшення;

- перекладаiться розвиток на економiчну мову i аналiзуiться результат.

Математичне програмування тАУ це частковий випадок системного аналiзу однiii чiтко вираженоi мети, досягнення якоi здiйснюiться за одним критерiiм.

У загальному виглядi математична формулювання задачi виглядаi таким чином:

- необхiдно знайти найбiльше або найменше значення цiльовоi функцii f (x₁, x₂, x₃тАж, x_n);

- якщо треба виконати умови g_i (x₁, x₂, x₃тАж, x_n) £ b_i, i = 1,2,3тАж,m;

- де: f, g_i тАУ вiдомi функцii,

b_i - деякi дiйснi числа, n > m.

Задачу оптимiзацii з точки зору економiки можна сформулювати таким чином:

- знайти такi значення змiнних. що надають ефективностi дiяльностi максимальне чи мiнiмальне значення;

- за умов виконання обмежень, якi повтАЩязанi зi змiнними, , за допомогою котрих, змiнних, здiйснюiться керування дiяльнiстю.

Конкретна цiль, поставлена у економiчнiй задачi, пояснюiться цiльовою функцiiю (критерiiм ефективностi), екстремум якоi i треба знайти.

Обмеження вiдображають умови, при розвтАЩязаннi економiчноi задачi, наприклад, брак ресурсiв, гранична вартiсть i таке iнше. Змiннi, з яких будуiться цiльова функцiя, та на якi накладаються обмеження, використовують як тАЬiнструменттАЭ, за допомогою якого досягаiться той чи iнший варiант цiлi. Як змiннi задовольняють усiм обмеженням, так отриманий варiант називають припустимим (допустимим).

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

РозвтАЩязати задачу тАУ це знайти ii оптимальне рiшення, або зтАЩясувати його вiдсутнiсть.

Функцiя цiлi (критерiй оптимальностi) повинна обтАЩiктивно характеризувати суспiльно-корисну значущiсть соцiально-економiчного явища або процесу. Критерiй оптимальностi можливо зтАЩясувати лише з економiчноi сутностi проблеми тАУ задача, яку розвтАЩязуi фахiвець економiст. Принципово неможливо визначити цiльову функцiю на етапi розвтАЩязання задачi математиком. такою ж мiрою це все стосуiться також обмежень задачi оптимiзацii.

Класифiкацiя моделей задач математичного програмування залежить вiд властивостей функцii цiлi та функцiй обмежень.

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

Якщо у математичнiй моделi ураховуiться поетапно час, така задача маi назву задачi динамiчного програмування; у iншому випадку тАУ задачi статичного програмування.

В залежностi вiд того, який характер мають вихiднi данi моделi тАУ детермiнований або стохастичний тАУ задачi мають назву вiдповiдно детермiнованого та стохастичного програмування.

Серед задач нелiнiйного програмування особливо досконало дослiдженi задачi опуклого програмування тАУ задачi знаходження екстремума опуклоi функцii, заданоi на опуклiй замкненiй множинi. У свою чергу, серед задач опуклого програмування найпростiшi i найдосконало дослiдженi задачi квадратичного програмування, у яких функцiя цiлi тАУ квадратична, а обмеження тАУ лiнiйнi.

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

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

Якщо у задачi математичного програмування вiдсутнi усi обмеження. така задача маi назву задачi безумовного програмування.

У якостi прикладiв економiчних проблем, якi доцiльно розвтАЩязувати. використовуючи методи та моделi математичного програмування, розглянемо такi:

Приклад 1. Задача про планування випуску продукцii малого пiдприiмства.

Плануiться виробляти жiночi та чоловiчi костюми. На жiночiй костюм потрiбно 1 м. шерстi, 2 м. шовку та 1 людино-тиждень працевитрат. На чоловiчий костюм потрiбно 3,5 м. шерстi, 0,5 м. шовку i також 1 людино-тиждень працевитрат. Загалом пiдприiмство маi 350 м. шерстi, 240 м. шовку та 150 людино-тижнiв працевитрат. За попередньою домовленiстю iз замовником мають виробити 110 костюмiв жiночих та чоловiчих загалом. Акцiонери, якi вклали грошi у пiдприiмство та сировину (тканину), вимагають прибуток не менше, нiж 1400 грн. Замовник купуi жiночий костюм на 10 грн. дорожче собiвартостi, чоловiчий тАУ на 20 грн. Потрiбно зтАЩясувати: скiльки необхiдно виготовити жiночих та чоловiчих костюмiв, щоб задовольнити усiм вимогам та отримати найбiльший прибуток.

РозвтАЩязок задачi: Позначимо кiлькiсть жiночих костюмiв, якi потрiбно виготовити, через х₁; кiлькiсть чоловiчих тАУ х₂. Загальний прибуток (критерiй оптимiзацii, мета, цiль) виробництва складаi:

Z = f (x) = 10 x₁ + 20 x₂ ;

витрати: шерстi = 1 ´ х₁ + 3,5 ´ х₂;

шовку = 2 ´ х₁ + 0,5 ´ х₂;

трудомiсткостi = х₁ + х₂;

результати: кiлькiсть загальна костюмiв х₁ + х₂;

прибуток 10 x₁ + 20 x₂.

Функцiональнi обмеження задачi мають вигляд:

х₁ + 3,5 х₂ £ 350;

2 х₁ + 0.5 х₂ £ 240; обмеження ресурсiв

х₁ + х₂ £ 150;

х₁ + х₂ ³ 110; обмеження планового завдання

10 х₁ + 20 х₂ ³ 1400;

Нефункцiональнi обмеження вочевидь складають:

х₁ ³ 0;

х₂ ³ 0.

РозвтАЩязок задачi математичного програмування у даному прикладi складаi: х₁ = 70; х₂ = 80; f (x)_max = 2300 грн.

Приклад 2. Задача про постачання вантажiв вiд постачальникiв до замовникiв.

Вiд трьох постачальникiв, розташованих у пунктах А₁, А₂, А₃ до чотирьох замовникiв, розташованих у пунктах В₁, В₂, В₃, В₄, треба перевезти однорiдний вантаж. Наявнiсть вантажу по пунктах постачальникiв: А₁= 50т, А₂ = 40 т, А₃ = 20т. Потреба у вантажi: В₁ = 30т, В₂ = 25т, В₃ = 35т, В₄ = 20т. Вiдстанi мiж пунктами замовникiв та постачальникiв наведенi у таблицi.

Таблиця

РозвтАЩязок задачi. Позначимо x_ij тАУ кiлькiсть вантажу. який буде перевезено з тАЬiтАЭтАУого пункта постачання у тАЬjтАЭтАУий пункт замовлення; c_ij тАУ вiдстань вiд тАЬiтАЭ-ого постачальника до тАЬjтАЭ-ого замовника. Мета: розшукати вартiсть перевезення вантажiв з найменшою витратою транспортного моменту.

Z = f (x) = S S C_ij´ X_ij

Задача збалансована, тобто наявнiсть вантажу дорiвнюi потреби у вантажу:

S X_ij = а_i, i = 1, 2, 3; - умова вивезення вантажу вiд кожного з трьох постачальникiв до 4 замовникiв;

S X_ij = в_j j тАУ 1, 2, 3, 4; - умова отримання кожним замовником необхiдноi кiлькостi вантажу.

Нефункцiональнi обмеження: х_ij ³ 0.

РозвтАЩязок задачi складаi:

х₁₁ = 25; х₁₂ = 5; х₁₄ = 20; х₁₃ = 0;

х₂₁ = 5; х₂₃ = 35; х₂₂ = 0; х₂₄ = 0;

х₃₁ = 20; х₃₂ = 0; х₃₃ = 0; х₃₄ = 0;

f (x)_min = 190т.км.

Приклад 3. Задача про рацiональний розкрiй.

Пiдприiмство одержуi прут сталевого прокату довжиною l = 800 см. Треба виготовити деталi трьох (i) рiзновидiв: l₁ = 250 см, а₁ = 150 штук; l₂ = 190 см, а₂ = 140 штук; l₃ = 100 см, а₃ = 48 штук.

Скласти рацiональний план розкрою вихiдного матерiалу (деталей) з найменшими виходами (залишками).

РозвтАЩязок задачi. Побудуiмо таблицю можливих варiантiв розкрою.

Таблиця

Позначимо:

- тАЬх_jтАЭ - кiлькiсть одиниць (пруткiв) первинного матерiалу, який буде розкроiно за тАЬjтАЭ варiантом (способом);

- а_i тАУ потрiбна кiлькiсть деталей тАЬiтАЭ-ого рiзновиду (l_i - довжини);

- с_j тАУ залишок при розкроi одиницi первинного матерiалу (прутка) за тАЬjтАЭ-тим способом (варiантом);

- b_ij тАУ кiлькiсть деталей тАЬiтАЭ-ого виду, яку отримують при виготовленi з одиницi первинного матерiалу (прутка) за тАЬjтАЭ-тим варiантом (способом).

Залишок за тАЬjтАЭ-тим способом вiд розкрою = c_j ´ x_j, загалом

Z = SC_j´X_jВоmin,

j=1

за умов:

S b_ij´ x_j³ a_j, i = 1,2,3тАжm;

j=1

x_j ³ 0, j = 1,2,3тАжn.

Найбiльш трудомiстка частина задачi тАУ визначення способiв (варiантiв) розкрою, яка здiйснюiться за формулою:

m

S l_i´ bij + C_j³ l, j = 1,2,3тАжn;

i=1

0 £ C_j £ min (l_i).

Цiльова функцiя:

Z = 50 ´ х₁ + 10 ´ х₂ + 0 ´ х₃ + 70 ´ х₄ + 60 ´ х₅ + 50 ´ х₆ + +40 ´ х₇ + 30 ´ х₈ + 20 ´ х₉ + 10 ´ х₁₀ + 0 ´ х₁₁; Во min;

обмеження:

3х₁ + 2х₂ + 3х₃ + 1х₄ + х₅ + х₆ ³ 150;

х₂ + 2х₄ + х₅ + 4х₇ + 3х₈ + 2х₉ + х₁₀ ³ 140;

х₂ + 3х₃ + х₄ + 3х₅ + 5х₆ + 2х₈ + 4х₉ + 6х₁₀ + 8х₁₁ ³ 48;

x_j ³ 0, j = 1,2,3тАж11.

РозвтАЩязок задачi складаi:

Z* = 2300, x* = (8; 48; 0; 0; 0; 0; 23; 0; 0; 0; 0;).

Приклад 4. Задача комплектного розкрою деталей.

На розкрiй поступають варiанти заготовок (t = 2) у обсязi тАЬb_iтАЭ (i = 1,2,3тАжm) кожного. Потрiбно виготовити комплекти деталей, якi налiчують по тАЬl_kтАЭ штук (l₁ = 1 деталь, l₂ = 2 деталi) деталей кожного рiзновиду деталей. Кожна одиниця тАЬiтАЭ-ого (одного з двох) рiзновидiв заготовки може бути розкроiна n_i (j = 1,2тАжn_i) рiзними способами. При розкроi одиницi тАЬtтАЭ-ого матерiалу заготовки тАЬjтАЭ-тим способом отримаiмо тАЬa_tjkтАЭ одиниць тАЬkтАЭ тАУ а деталi. Потрiбно скласти програму виготовлення якомога бiльше комплектiв деталей, маючи вказанi заготовки та задану комплектацiю. Дамо конкретнi данi: заготовки (t = 1) тАЬАтАЭ мають довжину 5 м, кiлькiсть b₁ = 100 штук; заготовки (t = 2) тАЬВтАЭ мають довжину 4 м, кiлькiсть b₂ = 175 штук; деталi D₁ мають довжину 2,0 м, деталi D₂ - довжину 1,25 м; до одного комплекту залучають одну (l₁ = 1) деталь D₁ та двi (l₂ = 2) деталi D₂. Треба виготовити якомога бiльше комплектiв деталей.

РозвтАЩязок задачi. Позначимо: x_tj - кiлькiсть одиниць тАЬtтАЭ-ого рiзновиду заготовок, якi розкроюваються тАЬjтАЭ-тим способом; х тАУ загальна кiлькiсть комплектiв. Побудуiмо таблицю варiантiв розкрою заготовок.

Таблиця

Цiльова функцiя: Z = x Во max;

обмеження:

по кiлькостi заготовок:

х₁₁ + х₁₂ + х₁₃ £ 100;

х₂₁ + х₂₂ + х₂₃ £ 175;

по комплектностi:

х₁₁ + 2×х₁₂ + 0×х₁₃ + 2×х₂₁ + х₂₂ + 0×х₂₃ ³ х;

2×х₁₁ + 0×х₁₂ + 4×х₁₃ + 0×х₂₁ + х₂₂ + 3×х₂₃ ³ 2х;

х_ij³ 0; х ³ 0.

Оптимальний план складаi:

Z* = 264; х* = (0; 0; 100; 132; 0; 43)

Приклад 5. Задача про складання сумiшi.

На пiдприiмствi потрiбно виготовити сумiш, якi мiстить 30% речовини П₁, 20% речовини П₂, 40% речовини П₃ та 10% речовини П₄. Для виготовлення сумiшi можливо використати три рiзновиди сировини М₁, М₂, М₃ з рiзними спiввiдношеннями речовин та рiзною вартiстю. Потрiбно скласти сумiш з мiнiмальною вартiстю та наданим складом речовин. РЖсходнi данi наведенi у таблицi.

Таблиця

РозвтАЩязок задачi. Позначимо тАЬx_iтАЭ - кiлькiсть використаноi сировини тАЬM_iтАЭ.

Цiльова функцiя:

Z = 4 x₁ + 2x₂ + 3x₃ Во min;

обмеження:

0,3х₁ + 0,1х₂ + 0,6х₃ ³ 0,3;

0,1х₁ + 0,2х₂ + 0,2х₃ ³ 0,2;

0,5х₁ + 0,6х₂ + 0,1х₃ ³ 0,4;

0,1х₁ + 0,1х₂ + 0,1х₃ ³ 0,1;

х_i ³ 0.

Оптимальний план х* = (0; 0,6; 0,4); Z* = 2,4.

Тема 2. Загальна задача лiнiйного програмування та деякi з методiв ii розвтАЩязування

У загальному виглядi розвтАЩязання задачi математичного програмування майже неможливо. Найдосконало вивченi задачi лiнiйного програмування. Це пояснюiться тим, що бiльшiсть реальних економiчних моделей зводиться до задачi лiнiйного програмування, внаслiдок чого i методи розвтАЩязку задач лiнiйного програмування найбiльш розвиненi.

Загальною задачею лiнiйного програмування зветься задача знаходження максимального (мiнiмального) значення функцii

Z = SC_j´X_j ,

j=1

(Z = С₀ + С₁Х₁ + С₂Х₂ + . . . + С_nХ_n);

За умов функцiональних обмежень:

Sa_ijx_j£b_i , де i = 1,2, . . . , k;

j=1

а₁₁х₁ + а₁₂х₂ + . . . + a_1nx_n £ b₁ ,

а₂₁х₁ + а₂₂х₂ + . . . + a_2nx_n £ b_{2 ,}

а_k1х₁ + а_k2х₂ + . . . + a_knx_n £ b_{k ,}

Sa_ijx_j= b_i , де i = k +1, k + 2, . . . , m;

j=1

a_k+1;1x₁ + a_k+1;2x₂ + . . . + a_k+1;nx_n = b_k+1 ,

a_k+2;1x₁ + a_k+2;2x₂ + . . . + a_k+2;nx_n = b_k+2 ,

a_m;1x₁ + a_m;2x₂ + . . . + a_m;nx_n = b_m

нефункцiональних обмежень:

x_j ³ 0 , де j = 1,2,3,. . . n;

а також a_ij; b_i; c_j тАУ заданi постiйнi величини, а ще k £ m.

Цiльову функцiю можливо оптимiзувати на тАЬmaxтАЭ, або на тАЬminтАЭ тАУ це не i принципово, бо у точцi х* функцiя Z = f (x*) тАУ досягаi мiнiмуму, а функцiя Z = - f (x*) тАУ досягаi максимуму. Таким чином ми завжди можемо мiнiмiзувати цiльову функцiю, не втрачаючи загальностi пiдходу.

Цiльова функцiя та усi функцiональнi обмеження, як ми вже бачили, мають лiнiйну форму вiдносно невiдомих x_j, що i даi цiй задачi математичного програмування назву тАУ лiнiйне програмування.

Невiдомi, якi присутнi у лiнiйнiй моделi, вiдповiдно нефункцiональним обмеженням невiдтАЩiмнi, що теж не обмежуi загальностi пiдходу, бо i можливiсть завжди перепозначити

x_j = - (x_j)^- , де (x_j)^- - вiдтАЩiмне.

В залежностi вiд вигляду функцiональних обмежень (нерiвностi або рiвностi) загальну задачу лiнiйного програмування подiляють на:

а) канонiчну, якщо k = 0; l = n, де усi функцiональнi обмеження мають вигляд рiвностей;

б) стандартну (симетричну), де k = m; l = n, де усi функцiональнi обмеження мають вигляд нерiвностей.

Будь-якi задачу лiнiйного програмування можливо звести до канонiчноi задачi шляхом перетворення функцiональних обмежень нерiвностей у обмеження рiвностi доданням до нерiвностей невiдомих невiдтАЩiмних величин:

a_i1x₁ + a_i2x₂ + . . . + a_inx_n + y_i = b_i ;

де y_i ³ 0; новим невiдомим дають назви вiдповiдно x_n+1; x_n+2; . . . ; х_n+m; та вiдповiдно x_j ³ 0 , де j = 1,2,3 . . . n; n + 1 . . . n + m;

функцiональнi обмеження набувають вигляд

Sa_ijx_j+ y_i = b_i , де i = 1, 2, 3 . . . , m;

j=1

a₁₁x₁ + a₁₂x₂ + . . . + a_1nx_n + x_n+1 = b₁ ,

a₂₁x₁ + a₂₂x₂ + . . . + a_2nx_n + x_n+2 = b₂ ,

a_m1x₁ + a_m2x₂ + . . . + a_mnx_n + x_n+m = b_m ,

кiлькiсть невiдомих моделi x_j³ 0 збiльшилась до n + m .

Слушне зауваження у пiдручнику тАУ якщо знак нерiвностi ³, так додатковi невiдомi треба вiднiмати вiд лiвоi частини нерiвностi.

Будь-яку задачу лiнiйного програмування можливо звести до стандартноi задачi лiнiйного програмування шляхом вiднiмання з лiвоi частини рiвняння додаткових невiдтАЩiмних невiдомих частин.

Таким чином ми навчились зводити задачу лiнiйного програмування вiд мiнiмiзацii до максимiзацii; переходити вiд функцiональних обмежень у виглядi нерiвностей до обмежень тАУ рiвностей i навпаки; замiнювати невiдомi змiннi вiдтАЩiмнi на невiдтАЩiмнi. Введенi додатковi невiдомi змiннi мають чiткий економiчний змiст. так, наприклад, якщо у обмеженнях задачi лiнiйного програмування (нерiвнiсть) вiдбиваються витрати ресурсу та iх наявнiсть, так додаткова змiна задачi (у формi рiвняння) дорiвнюi обсягу невитраченого вiдповiдного ресурсу. Слушне зауваження у пiдручнику тАУ якщо змiннi не i невiдтАЩiмною, так ii можливо замiнити на двi невiдтАЩiмнi:

x_i = u_i тАУ v_i .

Система обмежень у виглядi рiвностей сумiсна, якщо i хоча б одно рiшення; несумiсна, якщо ранг матрицi ½a_ij, i = 1,2,. . . n равен ( r ) , а ранг розширеноi матрицi (додан стовбець тАЬb_iтАЭ) бiльше нiж ( r ); надмiрна, якщо одне з рiвнянь можливо отримати як лiнiйну комбiнацiю iнших. У системi: n тАУ кiлькiсть невiдомих,

m тАУ кiлькiсть рiвнянь.

Якщо система сумiсна та не i надмiрною, так будемо вважати, що ранг ii дорiвнюi (m); тодi:

m тАУ базиснi змiннi,

(n тАУ m) тАУ вiльнi змiннi, m < n.

Система у даному випадку маi нескiнченну кiлькiсть розвтАЩязкiв, так як ми маiмо можливiсть надавати вiльним змiнним будь-якi значення.

Рiшення системи рiвнянь (обмежень) маi назву базисного рiшення, якщо усi вiльнi змiннi дорiвнюють нулевi. Сукупнiсть значень невiдомих (чисел) задачi математичного програмування, якi задовольняють усiм обмеженням задачi, мають назву припустимого рiшення або плану.

Сукупнiсть усiх припустимих рiшень системи рiвнянь i опукла множина. Або множина розвтАЩязкiв задачi лiнiйного програмування i опуклою.

Базисне припустиме рiшення задачi лiнiйного програмування вiдповiдаi однiй з вершин або граней множини розвтАЩязкiв.

Оптимальне рiшення задачi лiнiйного програмування вiдповiдаi одному з базисних припустимих рiшень, тобто досягаiться у вершинi множини розвтАЩязкiв, маi другу назву тАУ оптимальний план задачi лiнiйного програмування.

Геометрична iнтерпретацiя множини допустимих розвтАЩязкiв задачi лiнiйного програмування та графiчний метод ii розвтАЩязування./2/ стор. 165.

Розглянемо задачу лiнiйного програмування у формi стандартноi задачi тАУ з обмеженнями у виглядi нерiвностей. З метою наочностi розглянемо простiший випадок з двома невiдомими змiнними. Пригадаiмо задачу про планування випуску продукцii малим пiдприiмством.

Z = 10 x₁ + 20 x₂ ; Z Во max;

х₁ + 3,5 х₂ £ 350;

2 х₁ + 0,5 х₂ £ 240;

х₁ + х₂ £ 150;

х₁ + х₂ ³ 110;

10 х₁ + 20 х₂ ³ 1400;

х₁ ³ 0;

х₂ ³ 0.

Нерiвнiсть тАУ обмеження графiчно вiдображаiться пiвплощiною, а границя тАУ граничною прямою, рiвняння якоi утворюiться перетворенням нерiвностi на рiвняння.

l₁ Во x₁ + 3,5x₂ = 350 ;

x₁ = 0, x₂ = 350 / 3,5 = 100 ; x₂ = 0, x₁ = 350.

Щоб зтАЩясувати, яка напiвплощiна задовольняi нерiвностi, перевiримо, наприклад, чи включаi точку (0,0) 0 + 3,5 × 0 £ 350 напiвплощiна нижче граничноi прямоi тАУ нерiвнiсть виконуiться тАУ напiвплощiна нижче границi.

Таким же чином перевiримо та побудуiмо iншi нерiвностi:

l₂ Во 2x₁ + 0,5x₂ = 240 ;

x₁ = 0, x₂ = 240 / 0,5 = 480 ; x₂ = 0, x₁ = 240 / 2 = 120 ;

l₃ Во x₁ + x₂ = 150; x₁ = 0; x₂ = 150; x₂ = 0, x₁ = 150;

l₄ Во x₁ + x₂ = 110; x₁ = 0; x₂ = 110; x₂ = 0, x₁ = 110;

l₅ Во 10x₁ + 20x₂ = 1400;

x₁ = 0, x₂ = 1400 / 20 = 70; x₂ = 0, x₁ = 1400 / 10 = 140;

але точка (0,0) 10 × 0 + 20 × 0 = 0 ³ 1400 не вiдповiдаi нерiвностi, тому нам потрiбна пiвплощiна вище граничноi прямоi.

Таким чином отриманий многокутник розвтАЩязкiв, до речi тАУ опуклий, як завжди.

З метою знаходження максимуму цiльовоi функцii

Z = 10 x₁ + 20 x₂ побудуiмо лiнiю рiвня цiльовоi функцii, поклавши Z = 0 ,

10 x₁ + 20 x₂ = 10; x₁ = 0, x₂ = 40; x₂ = 0; x₁ = 80;

зростання цiльовоi функцii позначаi паралельне змiщення самiй собi догори, доки остання крапка не вийде на границю многокутника розвтАЩязкiв.

Ця точка вiдповiдаi перетину прямих

х₁ + 3,5 х₂ = 350; - l₁ ( × ) C (70; 80)

х₁ + х₂ = 250; - l₃

х₁ = 70, х₂ = 80,

Z_max (x) = 10 × x₁ + 20 × x₂ = 10 × 70 + 20 × 80 = 23000 грн.

Слушне зауваження у пiдручнику тАУ якщо було б потрiбно знайти мiнiмальне значення цiльовоi функцii, так лiнiю рiвня потрiбно змiщувати униз, доки остання крапка вийде на границю многокутника розвтАЩязкiв тАУ це l₅ , усi крапки якоi i розвтАЩязком задачi тАУ нескiнченна множина рiшень.

У розглянутому випадку многокутник розвтАЩязкiв не тiльки опуклий, а ще i i замкненим. Можливi варiанти опуклого многокутника розвтАЩязкiв, який i необмеженим.

У першому випадку можливо знайти максимальне значення цiльовоi функцii, а у другому випадку тАУ мiнiмальне значення. На наступному малюнку наведений приклад многокутника розвтАЩязкiв несумiсноi системи обмежень тАУ розвтАЩязок задачi математичного програмування вiдсутнiй.

Малюнок. Многокутник розвтАЩязкiв несумiсноi системи обмежень

задачi лiнiйного програмування

Тема 3. Симплексний метод розвтАЩязання задач лiнiйного програмування

Перша праця по лiнiйному програмуванню була надрукована Канторовичем у 1939 роцi, але лише пiсля вiдкриття Данцiгом у 1949 роцi симплекс-метода розв'язання задачi лiнiйного програмування до цього класу задач виникла зацiкавленiсть. Симплекс-метод даi аналiтичний розвтАЩязок лiнiйноi задачi математичного програмування.

Симплексний метод розвтАЩязання задачi лiнiйного програмування ТСрунтуiться на переходi вiд одного опорного плану до iншого таким чином, що кожного разу значення цiльовоi функцii зростаi (за умов, що задача маi оптимальний план, та кожний з опорних планiв не i надмiрним). Пiд опорним планом мають на увазi невiдтАЩiмний базисний розвтАЩязок задачi лiнiйного програмування. Нагадаiмо тАУ базисний план (розвтАЩязок) тАУ рiшення системи обмежень. у якому усi вiльнi змiннi дорiвнюють нулевi, тобто геометрично базисний план вiдповiдаi однiй з вершин або граней многокутника розвтАЩязкiв.

Розглянемо використання симплекс-методу для вирiшення задачi лiнiйного програмування на прикладi задачi про планування випуску продукцii малим пiдприiмством. У звтАЩязку з тим, що ця задача була розвтАЩязана ранiше, i ми зтАЩясували, що функцiональнi плановi обмеження виконуються автоматично, а також з метою спрощення пошуку, розглянемо тiльки функцiональнi обмеження ресурсiв.

х₁ + 3,5 х₂ £ 350;

2 х₁ + 0,5 х₂ £ 240;

х₁ + х₂ £ 150;

х₁ ³ 0;

х₂ ³ 0.

Z = f (x) = 10 x₁ + 20 x₂ ; Z Во max;

( -Z = - f (x) = - 10 x₁ - 20 x₂ - 0 × x₄ - 0 × x₅; Во min ).

РозвтАЩязок задачi. Перетворимо функцiональнi обмеження-нерiвностi на обмеження-рiвностi шляхом введення у обмеження-нерiвностi невiдтАЩiмних вiльних невiдомих y₁, y₂, y₃ (хоча можливо було б i х₃, х₄, х₅ ).

х₁ + 3,5 х₂ + у₁ = 350; (1)

2 х₁ + 0,5 х₂ + у₂ = 240; (2)

х₁ + х₂ + у₃ = 150; (3)

х₁ ³ 0; х₂ ³ 0; у₁³ 0; у₂³ 0; у₃³ 0.

Перед початком виробництва х₁ = х₂ = 0 , тодi

у₁ = 350; наявнiсть ресурсу тАУ шерсть;

у₂ = 240; наявнiсть ресурсу тАУ шовк;

у₃ = 150; наявнiсть ресурсу тАУ трудомiсткiсть.

Прибуток на початок справи Z = 10 × 0 + 20 × 0 = 0;

Кiлькiсть рiвнянь-обмежень m = 3; кiлькiсть невiдомих тАУ х₁, х₂, у₁, у₂, у₃ n = 5; кiлькiсть вiльних змiнних тАУ (n тАУ m) = 5 тАУ 3 = 2;

базисне припустиме рiшення задачi тАУ це таке, у якому усi вiльнi змiннi дорiвнюють нулевi (вершина або грань многокутника розвтАЩязкiв). Тому початковий опорний план складаi

х (1) = (0; 0; 350; 240; 150) ; Z ( х(1) ) = 0;

де : х₁ = 0; х₂ = 0 тАУ вiльнi змiннi, вiдповiдаi рiшенню задачi, коли продукцiя не виробляiться. Надамо цю iнформацiю у виглядi симплекс-таблицi

Таблиця

Z = 10х₁ + 20х₂ = 10 × 0 + 20 × 0 = 0; - Z = 0;

Виробництво чоловiчих костюмiв х₂ даi бiльший дохiд, так почнемо його збiльшувати, залишаючи х₁ = 0, але iснують обмеження. З першоi строки симплекс-таблицi (першого рiвняння-обмеження на наявнiсть шерстяноi тканини) чоловiчих костюмiв можливо виготовити 350 / 3,5 = 100; з другоi строки симплекс-таблицi (другого рiвняння-обмеження на наявнiсть шовковоi тканини) чоловiчих костюмiв можливо виготовити 240 / 0,5 = 480 штук; з третьоi строки симплекс-таблицi (третього рiвняння-обмеження на наявнiсть ресурсiв працi) чоловiчих костюмiв можливо виготовити 150 / 1 = 150 одиниць. Визначальним i обмеження на шерстяну тканину, тобто найбiльша кiлькiсть чоловiчих костюмiв (за умов вiдсутностi жiночих тАУ х₁ = 0) дорiвнюi найменшому з трьох значень 100; 480; 150; х₂ = 110. Визначальний елемент симплекс-таблицi тАУ коефiцiiнт у першому рiвняннi при другiй вiльнiй змiннiй (х₂), який дорiвнюi3,5; та маi назву центру (ключового елемента).

Як буде виготовлено 100 чоловiчих костюмiв, так х₂ = 100 i з першого рiвняння-обмеження отримаiмо (х₁ = 0)

у₁ = 350 тАУ 3,5х₂ тАУ х₁; (1)

у₂ = 240 тАУ 0,5х₂ тАУ 2х₁; (2)

у₃ = 150 тАУ х₂ тАУ х₁; (3)

що у₁ = 0, тобто ресурсiв шерстяноi тканини не буде; з другого рiвняння-обмеження отримаiмо у₂ = 240 тАУ 0,5 × 100 тАУ 2 × 0 = = 190 м шовковоi тканини у запасах; з третього рiвняння-обмеження отримаiмо у₃ = 150 тАУ 100 тАУ 0 = 50 людино - тижнiв трудомiсткостi у запасах.

Прибуток складаi Z = 10 × 0 + 20 × 100 = 2000 грн.; - Z = - 2000.

Цiльова функцiя Z = 10 × х₁ + 20 × х₂ через новi вiльнi змiннi (х₁ = 0; у₂ = 0) маi вираз

40 40 40 30

Z = 10 х₁ + 20 х₂ = 10 × х₁ + 2000 - ¾ у₁ - ¾ х₁ = 2000 - ¾ у₁ + ¾ х₁,

7 7 7 7

бо (з першого рiвняння-обмеження) маiмо:

х₂ = 100 тАУ у₁ / 3,5 тАУ х₁ / 3,5.

Перетворимо систему рiвнянь-обмежень, замiнюючи х₂ на його вираз:

х₁ + 3,5 (100 тАУ у₁ / 3,5 тАУ х₁ / 3,5) + у₁ = 350; (1¢)

2 х₁ + 0,5 (100 тАУ у₁ / 3,5 тАУ х₁ / 3,50) + у₂ = 240; (2¢)

х₁ + (100 тАУ у₁ / 3,5 тАУ х₁ / 3,50) + у₃ = 150; (3¢)

х₂ + у₁ / 3,5 + х₁ / 3,5 = 100 (4¢)

Другий опорний план задачи таким чином складаi

х(2) = (0; 100; 0; 190; 50; 100); Z (х(2) ) = 2000;

де: х₁ = 0; у₁= 0 тАУ вiльнi змiннi, вiдповiдаi розвтАЩязку задачi, якщо виробляються виключно чоловiчi костюми (х₂ = 100). Знов надамо цю iнформацiю у виглядi симплекс-таблицi.

Таблиця

Кожен з елементiв симплекс-таблицi маi своi значення:

тАУ у першому стовпцi (х₁) 13 / 7 тАУ потрiбна кiлькiсть шовковоi тканини, потрiбноi на один жiночий костюм; 5 / 7 тАУ потрiбна кiлькiсть працi на один жiночий костюм; 30 / 7 тАУ прибуток вiд одного жiночого костюма;

Дивлячись на цiльову функцiю

30 40

Z = 2000 + ¾ × х₁ - ¾ × у₁ ,

7 7

бачимо, що збiльшення виготовлення жiночих костюмiв може збiльшити прибуток, бо х₁ ³ 0 , а також 30 / 7 > 0.

Пригадуючи, що у₁ = 0, знайдемо значення новоi вiльноi змiнноi, яка задовольняi систему рiвнянь-обмежень (2¢), (3¢), (1¢¢), а також у₂ ³ 0 , у₃ ³ 0 , х₂ ³ 0 .

(2¢) даi, якщо у₂ = 0, х₁ В» 102;

(3¢) даi, якщо у₃ = 0, х₁ = 70;

(1¢¢) даi, якщо х₂ = 0, х₁ =350;

Визначальними i обмеження на ресурси працi: , х₁ = 70, у₃ = 0 з рiвняння (3¢).

Визначальний елемент симплекс-таблицi тАУ це коефiцiiнт у рiвняннi (3¢), якiй дорiвнюi (5/7), та вiдiграi роль нового центру, або ключового елементу.

Як буде виготовлено 70 жiночих костюмiв, так х₁ = 70 з рiвняння (3¢) отримаiмо у₃ = 0 (нова базова змiнна);

Третiй опорний план задачi складаi:

Х (3) = (70; 80; 0; 60; 0;); Z (3) = 2300 грн.;

Z (3) > Z (1);

де: у₁ = 0; у₃ = 0 - вiльнi змiннi, вiдповiдаi розвтАЩязку задачi, якщо виробляiться 70 жiночих та 80 чоловiчих костюмiв. Надамо цю iнформацiю у виглядi симплекс-таблицi.

Таблиця