Розв'язання задач математичного програмування

Размещено на http://www.allbest.ru/

78

1. Предмет та об'єкти математичного програмування

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

Математичне програмування -- один із напрямків прикладної математики, предметом якого є задачі на знаходження екстремуму деякої функції за певних заданих умов.

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

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

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

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

Норми витрат на одиницю продукції	Вид продукції	Загальний запас ресурсу на місяць
	Морозильна камера	Електрична плита
робочого часу, люд.-год.	9,2	4	520
листового заліза, м2	3	6	240
скла, м2	0	2	40
Ціна одиниці продукції, ум. од.	300	200

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

Ресурс робочого часу (520 люд.-год.) дає змогу виготовляти 520 : 9,2 = 56 морозильних камер.

Наявна кількість листового заліза забезпечує виготовлення 240 : 3 = 80 морозильних камер.

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

Отже, щомісяця можна випускати 56 морозильних камер, що дасть виручку 56•300=16 800 ум. од.

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

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

На виробництво 20 електроплит буде використано таку кількість ресурсів:

	буде використано	залишок
робочий час:	20 · 4 = 80 (люд.-год.)	520 - 80 = 440 (люд.-год.)
листове залізо:	20 · 6 = 120 (м2)	240 - 120 = 120 (м2)
скло:	20 · 2 = 40 (м2)	Немає

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

Отже, друга виробнича програма уможливлює виробництво 20 електроплит та 40 морозильних камер. Виручка становитиме:

20 · 200 + 40 · 300 = 16 000 ум. од.

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

Зрозуміло, що розглянуті програми не вичерпують усіх можливих варіантів. Наприклад, доцільно було б розглянути програму виробництва 41 морозильної камери та можливої кількості електроплит; 42 морозильних камер та можливої кількості електроплит; 43 морозильних камер та можливої кількості електроплит і т. д.

2. Математична постановка задачі математичного програмування

Подамо схематично довільну економічну систему у такому вигляді (рис. 1.1):

Рис. 1.1 Схема економічної системи

Параметри с_k (k = 1, 2,..., l) - кількісні характеристики системи. можуть бути сталими величинами, або змінними

Вхідні змінні економічної системи бувають двох видів:

керовані x_j (j = 1, 2,..., n), значення яких можна змінювати в деякому інтервалі; і некеровані змінні y_i (і = 1, 2,..., m), значення яких не залежать від волі людей і визначаються зовнішнім середовищем.

Функцію F називають цільовою функцією, або функцією мети.

F = f (x₁, x₂,..., x_n; y₁, y₂,..., y_m; c₁, c₂,..., c_l). (1.1)

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

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

. (1.2)

Можливості вибору x_j завжди обмежені зовнішніми щодо системи умовами, параметрами виробничо-економічної системи тощо.

(1.3)

Система (1.3) називається системою обмежень, або системою умов задачі.

Для економічних систем змінні x_j мають бути невід'ємними:

. (1.4)

Залежності (1.2)--(1.4) утворюють економіко-математичну модель економічної системи.

Будь-який набір змінних x₁, x₂,..., x_n, що задовольняє умови (1.3) і (1.4), називають допустимим планом, або планом. Очевидно, що кожний допустимий план є відповідною стратегією економічної системи, програмою дій. Кожному допустимому плану відповідає певне значення цільової функції, яке обчислюється за формулою (1.1).

Сукупність усіх розв'язків системи обмежень (1.3) і (1.4), тобто множина всіх допустимих планів утворює область існування планів.

План, за якого цільова функція набуває екстремального значення, називається оптимальним. Оптимальний план є розв'язком задачі математичного програмування (1.2)--(1.4).

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

Позначимо через х₁ кількість вироблених морозильних камер, а через х₂ -- електроплит.

Умови задачі, описані в прикладі 1.1, можна подати такою економіко-математичною моделлю:

,

за умов: ;

;

;

.

Розв'язавши задачу відповідним методом математичного програмування, дістаємо такий розв'язок: для максимальної виручки від реалізації продукції необхідно виготовляти морозильних камер -- 50 штук, електроплит -- 15 (х₁ = 50, х₂ = 15).

Перевіримо виконання умов задачі:

;

;

.

Виручка становитиме: ум. од.

3. Історична довідка

Початком математичного програмування в сучасному розумінні вважають праці радянського вченого Л. В. Канторовича. (монографія «Математичні методи організації і планування виробництва»).

1947 року Дж. Данцигом також був розроблений основний метод розв'язування задач лінійного програмування -- симплексний метод.

Наступним кроком стали праці Дж. Неймана (1947 р.) щодо розвитку концепції двоїстості.

Термін «лінійне програмування» був введений 1951 року, у працях американських вчених Дж. Данцига та Г. Кумпанса.

1951 року -- праця Г. Куна і А. Таккера, в якій наведено необхідні та достатні умови оптимальності нелінійних задач;

1954 року -- Чарнес і Лемке розглянули наближений метод розв'язання задач з сепарабельним опуклим функціоналом та лінійними обмеженнями;

1955 року -- ряд робіт, присвячених квадратичному програмуванню.

У п'ятдесятих роках сформувався новий напрямок математичного програмування -- динамічне програмування, значний вклад у розвиток якого вніс американський математик Р. Белман.

Серед радянських вчених того періоду слід виокремити праці В. С. Немчинова, В. В. Новожилова, Н. П. Федоренка, С. С. Шаталіна, В. М. Глушкова, В. С. Михалевича, Ю. М. Єрмольєва та ін.

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

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

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

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

Як детерміновані, так і стохастичні задачі можуть бути статичними (однокроковими) або динамічними (багатокроковими).

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

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

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

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

5. Приклади економічних задач МП та їх моделей

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

Критерії оптимальності: максимум прибутку, максимум товарної продукції, мінімум витрат ресурсів.

Загальна математична постановка

n - видів продукції за умови найкращого способу використання її наявних ресурсів.

m - ресурсів: сировина, трудові ресурси, технічне оснащення тощо.

-загальні запаси ресурсів,

- норми витрат і-го ресурсу на виробництво одиниці j-ої продукції

- прибуток з одиниці j-ої реалізованої продукції.

Критерій оптимальності: максимум прибутку.

Позначимо через х₁, х₂, …, х_n обсяги виробництва відповідно першого, другого і т. д. видів продукції.

за умов:

.

На ринок поставляється картопля з трьох фермерських господарств за цінами відповідно 80, 75 та 65 коп. за 1 кг.

На завантаження 1 т картоплі в господарствах відповідно витрачається по 1, 6 та 5 хвилин.

Замовлено 12 т картоплі, і для своєчасної доставки необхідно, щоб на її завантаження витрачалося не більше 40 хвилин.

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

Побудова економіко-математичної моделі.

Позначимо:

х₁ -- кількість картоплі, що буде закуплена у першому господарстві (т);

х₂, х₃ -- кількість картоплі, закупленої відповідно у другого та третього фермерів (т).

Економіко-математична модель задачі має вигляд:

за умов:

Задача про «дієту» (або про суміш): деякий раціон складається з кількох видів продуктів. Відомі вартість одиниці кожного компонента, кількість необхідних організму поживних речовин та потреба в кожній речовині, вміст в одиниці кожного продукту кожної поживної речовини. Необхідно знайти оптимальний раціон -- кількість кожного виду продукту, що враховує вимоги забезпечення організму необхідною кількістю поживних речовин.

Критерій оптимальності -- мінімальна вартість раціону.

Загальна математична постановка

n видів продуктівз яких складається деякий раціон.

вартість одиниці кожного продукту

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

потреба в кожній i-ій речовині

одиниці j-го продукту міститься в поживної речовини i.

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

Критерій оптимальності -- мінімальна вартість раціону.

Позначимо через x₁, x₂, …, x_n -- кількість відповідного j-го виду продукту .

Економіко-математична модель матиме вигляд:

за умов:

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

Стандартом передбачається, що октанове число бензину А-76 має бути не нижчим 76, вміст сірки -- не більшим, ніж 0,3 %.

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

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

Таблиця 2.1

Техніко-економічні показники компонент бензину

Показник	Компонента бензину
	№ 1	№ 2	№ 3	№4
Октанове число	68	72	80	90
Вміст сірки, %	0,35	0,35	0,30	0,20
Наявний обсяг, т	700	600	500	300
Вартість, грош. од./т	40	45	60	90

Необхідно визначити, скільки тонн кожного компонента потрібно використати для того, щоб отримати 1000 т бензину А-76 з мінімальною собівартістю.

Побудова економіко-математичної моделі.

Позначимо через х_j кількість j-го компонента в суміші (т), j = 1,2,3,4.

Економіко-математична модель задачі має вигляд:

.

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

Критерії оптимальності: мінімальна сумарна вартість перевезень, мінімальні сумарні витрати часу.

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

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

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

Критерій оптимальності: максимальний сумарний ефект від виконання робіт.

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

Критерій оптимальності: мінімальна сумарна вартість (відстань) пересування по маршруту.

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

6. Загальна економіко-математична модель задачі лінійного програмування (ЛП)

Загальна лінійна економіко-математична модель

(2.1)

за умов:

(2.2)

(2.3)

Вектор Х = (х₁, х₂, …, х_n), координати якого задовольняють систему обмежень (2.2) та умови невід'ємності змінних (2.3), називається допустимим розв'язком (планом) задачі лінійного програмування.

Допустимий план Х = (х₁, х₂, …, х_n) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (2.2) у вигляді рівностей, а також обмеження (2.3) щодо невід'ємності змінних.

Опорний план Х = (х₁, х₂, …, х_n), називається невиродженим, якщо він містить точно m додатних змінних, інакше він вироджений.

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

Задачу (2.1)--(2.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2.2) всі b_i (i = 1, 2, …, m) невід'ємні, а всі обмеження є рівностями.

Якщо якесь b_i від'ємне, то, помноживши i-те обмеження на
(- 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності

а_i1х₁ + а_i2х₂ + … + а_inx_n ? b_i,

то її можна звести до рівності, увівши додаткову змінну x_{n + 1}:

a_i1x₁ + a_i2x₂ + … + + a_in x_n + x_{n + 1} = b_i.

Аналогічно обмеження виду

а_k1x₁ + a_k2x₂ + … + a_knx_n ? b_k

зводять до рівності, віднімаючи від лівої частини додаткову змінну х_{n + 2}, тобто:

a_k1x₁ + a_k2x₂ + … + a_knx_n - x_{n + 2} = b_k (х_n+1 ? 0, х_n+2 ? 0).

Розглянемо лінійну нерівність з n невідомими:

(2.4)

Для зведення нерівності (2.4) до рівняння необхідно до її лівої частини додати деяку невід'ємну величину х_{n + 1} ? 0. У результаті дістаємо лінійне рівняння, яке містить n+1 змінну:

a₁x₁ + a₂x₂ + … + a_nx_n + x_{n + 1} = b. (2.5)

Теорема 2.1. Кожному розв'язку нерівності (2.4) відповідає єдиний розв'язок рівняння (2.5), який одночасно є розв'язком нерівності (2.4), і, навпаки, кожному розв'язку рівняння (2.5) і нерівності (2.4) відповідає єдиний розв'язок нерівності (2.4).

Доведення: Нехай X^* -- розв'язок нерівності (2.4), тоді підстановкою нерівність виконується:

.

Перенесемо ліву частину даної нерівності в праву і позначимо вираз у правій частині через , тобто:

Отже, розв'язок задовольняє рівняння (2.5) і водночас нерівність (2.4). Дійсно, і при підстановці в рівняння маємо:

Навпаки, нехай Y^* задовольняє рівняння (2.5) і нерівність (2.4)

і .

Тоді, відкидаючи в лівій частині рівності невід'ємну величину , отримаємо нерівність:

.

7. Форми запису задач лінійного програмування

1. За допомогою знака суми «».

(2.6)

2. У векторно-матричному вигляді:

max(min) Z = CX

АХ = А₀; (2.7)

Х ? 0,

Де

, ,

матриця коефіцієнтів; вектор змінних; вектор вільних членів;

С = (с₁, с₂, …, с_п) -- вектор коефіцієнтів при змінних у цільовій функції.

3. У векторній формі:

max(min)Z = CX

A₁x₁ + A₂x₂ + … + A_nx_n = A₀; (2.8)

X ?0,

Де

є векторами коефіцієнтів.

8. Геометрична інтерпретація задачі лінійного програмування

Розглянемо на площині х₁Оx₂ сумісну систему лінійних нерівностей:

(2.9)

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

Якщо в системі обмежень (2.9) буде три змінних, то спільну частину називають багатогранником розв'язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (2.9) кількість змінних більша, ніж три: х₁, х₂,… х_n, якщо система обмежень сумісна, то за аналогією з тривимірним простором вона утворює спільну частину в n-вимірному просторі -- опуклий багатогранник допустимих розв'язків.

Цільову функцію

в п-вимірному просторі основних змінних можна геометрично інтерпретувати як сім'ю паралельних гіперплощин, положення кожної з яких визначається значенням параметра Z.

Приклад:

Нехай фермер прийняв рішення вирощувати озиму пшеницю і цукрові буряки на площі 20 га, відвівши під цукрові буряки не менше як 5 га. Показники вирощування цих культур у табл.

Показник (із розрахунку на 1 га)	Озима пшениця	Цукрові буряки	Наявний ресурс
Затрати праці, людино-днів	5	25	270
Затрати праці механізаторів, людино-днів	2	8	80
Урожайність, тонн	3,5	40	--
Прибуток, тис. грн.	0,7	1	--

Критерієм оптимальності є максимізація прибутку.

Позначення:

х₁ -- площа посіву озимої пшениці, га;

х₂ -- площа посіву цукрових буряків, га.

max Z = 0,7x₁ + x₂ (2.10)

за умов: x₁ + x₂ ? 20; (2.11)

5x₁ + 25x₂ ? 270; (2.12)

2x₁ + 8x₂ ? 80; (2.13)

x₂ ? 5; (2.14)

x₁ ? 0, x₂ ? 0. (2.15)

9. Основні властивості розв'язків задачі лінійного програмування

Теорема 2.2. Множина всіх планів задачі лінійного програмування опукла.

Доведення. Необхідно довести, що коли X₁ та X₂ -- плани задачі лінійного програмування (2.1)--(2.3), то їх опукла комбінація X = л₁X₁ + л₂X₂, л₁ ? 0, л₂ ? 0, л₁ + л₂ = 1 також є планом задачі.

Так як X₁ і X₂ -- плани задачі, то виконуються такі співвідношення:

AX₁ = A₀, X₁ ? 0; AX₂ = A₀, X₂ ? 0.

Якщо підставити в систему обмежень значення X, то отримаємо:

AX = A(л₁X₁ + л₂X₂) = л₁AX₁ + л₂AX₂ = л₁A₀ + л₂A₀ = (л₁ + л₂)A₀ = A₀.

Отримали, що X задовольняє систему обмежень задачі лінійного програмування (2.2), і оскільки Х₁ ? 0, Х₂ ? 0, л₁ ? 0, л₂ ? 0, то й Х ? 0, тобто задовольняють і умову (2.3). У такий спосіб доведено, що Х -- план задачі лінійного програмування.

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

Рис. 2.3 Багатокутник розв'язків задачі у двовимірному просторі

Доведення. 1) Припустимо, що багатогранник розв'язків задачі обмежений і має скінченну кількість кутових точок. Позначимо кутові точки через Х₁, Х₂,..., Х_р, а оптимальний план -- Х₀

Для значення Х₀ виконується нерівність F(X₀) ? F(X). Припустимо, що Х₀ не є кутовою точкою.

Отже, її можна подати як опуклу лінійну комбінацію кутових точок множини Q, тобто

X₀ = л₁X₁ + л₂X₂ + … + л_pX_p,

.

F(X) -- лінійна функція:

(2.16)

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

.

За припущенням Х₀ -- оптимальний план, отже, з одного боку, F(X₀) ? F(X_k) = m, а з другого, доведено, що F(X₀) ? m, значить, F(X₀) = m = F(X_k), де X_k -- кутова точка. Отже, лінійна функція досягає максимального значення в кутовій точці (X_k).

2) Припустимо, що F(X) набирає максимальних значень більше, ніж в одній кутовій точці,

наприклад у точках

Х₁, Х₂,..., Х_q, (1 ? q ? p),

тоді F(X₁) = F(X₂) = … = F(X_q) = m.

Якщо Х опукла лінійна комбінація цих кутових точок, то:

тобто лінійна функція F набирає максимальних значень у довільній точці Х, яка є опуклою лінійною комбінацією кутових точок Х₁, Х₂,..., Х_q.

Рис. 2.4 Багатокутник розв'язку задачі у двовимірному просторі з необмеженою областю

Зауваження. Якщо багатокутник розв'язків -- необмежена область (рис. 2.4), то не кожну точку можна подати у вигляді опуклої лінійної комбінації її кутових точок. У такому разі введемо в систему додаткове обмеження

х₁ + х₂ ? L,

де L -- достатньо велике число. Введення цього обмеження означає відтинання прямою х₁ + х₂ = L від багатокутної необмеженої області обмеженого багатокутника, для якого виконується наведена теорема.

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

Теорема 2.4. Якщо відомо, що система векторів (k ? n) у розкладі , лінійно незалежна і така, що

,

де всі xj ? 0, то точка X = (x1, x2, …, xk, 0, …, 0) є кутовою точкою багатогранника розв'язків.

Доведення. Припустимо, що точка Х не є кутовою. Тоді вона може бути виражена опуклою лінійною комбінацією двох інших точок Х₁ та Х₂ багатокутника розв'язків, тобто:

Компоненти векторів Х₁ та Х₂, значення л₁ і л₂ невід'ємні і останні n - k компонентів вектора Х дорівнюють нулю, тому відповідні n - k компонент векторів Х₁ та Х₂ також мають дорівнювати нулю, тобто

,

.

Оскільки Х₁ та Х₂ -- плани, то

,

.

Віднімаючи від першого рівняння друге, отримаємо:

.

За припущенням вектори лінійно незалежні, тому останнє співвідношення виконується, якщо

.

Звідси:

Отже, Х неможливо подати як опуклу лінійну комбінацію двох інших точок багатокутника розв'язків. Значить, Х -- кутова точка.

Теорема 2.5. Якщо -- кутова точка багатогранника розв'язків, то вектори в розкладі , , що відповідають додатним , є лінійно незалежними.

Доведення. Не порушуючи загальності, можна вважати нерівними нулю перші k елементів вектора Х, отже,

.

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

.

За умовою

.

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

,

.

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

.

Всі х_і > 0, тому число можна вибрати настільки малим, що всі перші компоненти та набуватимуть додатних значень, тоді та -- плани. При цьому , тобто Х -- опукла лінійна комбінація точок Х₁ та Х₂, що суперечить умові теореми, оскільки Х -- кутова точка.

Припущення стосовно лінійної залежності векторів привело до суперечності. Отже, воно є неправильним, а система векторів -- лінійно незалежна.

Наслідок 1. Оскільки вектори мають розмірність m, то кутова точка багатокутника розв'язків має не більше, ніж m додатних компонентів .

Наслідок 2. Кожній кутовій точці багатокутника розв'язків відповідає лінійно незалежних векторів системи .

З наведених властивостей можна висновувати:

якщо функціонал задачі лінійного програмування обмежений на багатограннику розв'язків, то:

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

кожний опорний план відповідає кутовій точці багатогранника розв'язків.

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

10. Графічний метод розв'язування задач лінійного програмування

Розглянемо задачу.

Знайти

(2.17)

за умов:

(2.18)

. (2.19)

Припустимо, що система (2.18) за умов (2.19) сумісна і багатокутник її розв'язків обмежений.

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

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

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

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

4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі.

5. Будуємо пряму с₁х₁ + с₂х₂ = const, перпендикулярну до вектора .

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

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

У разі застосування графічного методу для розв'язування задач лінійного програмування можливі такі випадки:

1. Цільова функція набирає максимального значення в єдиній вершині А багатокутника розв'язків (рис. 2.5).

2. Максимального значення цільова функція досягає в будь-якій точці відрізка АВ (рис. 2.6). Тоді задача лінійного програмування має альтернативні оптимальні плани.

3. Задача лінійного програмування не має оптимальних планів: якщо цільова функція необмежена згори (рис. 2.7) або система обмежень задачі несумісна (рис. 2.8).

Рис. 2.5 Рис. 2.6

Рис. 2.7 Рис. 2.8

4. Задача лінійного програмування має оптимальний план за необмеженої області допустимих розв'язків (рис. 2.9 і 2.10). На рис. 2.9 у точці В маємо максимум, на рис. 2.10 у точці А -- мінімум, на рис. 2.11 зображено, як у разі необмеженої області допустимих планів цільова функція може набирати максимального чи мінімального значення у будь-якій точці променя.

Рис. 2.9 Рис. 2.10

Рис. 2.11

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

Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць -- А та В. Полиці обох видів виготовляють на верстатах 1 та 2. Тривалість обробки деталей однієї полиці кожної моделі подано в табл. (2.4).

Тривалість виготовлення книжкових полиць

Верстат	Тривалість обробки полиці моделі, хв.	Ресурс робочого часу верстатів, год. на тиждень
	А	В
1	30	15	40
2	12	26	36

Прибуток фірми від реалізації однієї полиці моделі А дорівнює 50 у. о., а моделі В -- 30 у. о. Вивчення ринку збуту показало, що тижневий попит на книжкові полиці моделі А ніколи не перевищує попиту на модель В більш як на 30 одиниць, а продаж полиць моделі В не перевищує 80 одиниць на тиждень.

Визначити обсяги виробництва, що максимізують прибуток.

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

х₁ -- кількість полиць моделі А, виготовлених за тиждень, а

х₂ -- кількість полиць моделі В.

Цільова функція задачі -- максимум прибутку.

max Z = 50х₁ + 30х₂ (2.20)

за умов:

Лише дві змінні, і тому - графічно.

Розв'язання.

Рис. 2.14

Вектор градієнт цільової функції .

Побудуємо лінію, що відповідає Z = 0

50х₁ + 30х₂ = 0, перпендикулярна до вектора .

Пересуватимемо пряму 50х₁ + 30х₂ = 0 паралельно самій собі згідно з напрямом вектора доти, доки не визначимо вершину багатокутника. Останньою спільною точкою прямої цільової функції та багатокутника OABCDE є точка С, координати якої

звідси маємо:

х₁ = 50; х₂ = 60.

Отже, Х^* = (50; 60);

Це означає, що коли фірма щотижня виготовлятиме 50 збірних книжкових полиць моделі А та 60 -- моделі В, то вона отримає максимальний прибуток -- 4300 у. о. Це потребуватиме повного використання тижневих ресурсів робочого часу верстатів 1 та 2.

Для невеликої птахоферми потрібно розрахувати оптимальний кормовий раціон на 1000 курчат, яких вирощують з 4-х до 8-тижневого віку. Нехтуючи тим, що потижневі витрати кормів для курчат залежать від їхнього віку, вважатимемо, що за 4 тижні курча споживає не менше 500 г суміші. Крім цього, кормовий раціон курчат має задовольняти певні вимоги щодо поживності. Сформулюємо ці вимоги у спрощеному вигляді, беручи до уваги лише дві поживні речовини: білок і клітковину, що містяться у кормах двох видів -- зерні та соєвих бобах. Вміст поживних речовин у кожному кормі та їх вартість маємо у табл. 2.5.

Поживність та вартість кормів

Корм	Вміст поживних речовин в 1 кг корму, %	Вартість 1 кг корму, у. о.
	Білку	клітковини
Зерно	10	2	0,40
Соєві боби	50	8	0,90

Готова кормова суміш має містити не менше як 20 % білка і не більш як 5 % клітковини.

Визначити масу кожного з двох видів кормів, що утворюють кормову суміш мінімальної вартості, водночас задовольняючи вимоги до загальної маси кормової суміші та її поживності.

Побудова економіко-математичної моделі.

х₁ -- маса зерна, а

х₂ -- соєвих бобів (в кг) у готовій кормовій суміші.

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

min Z = 0,40х₁ + 0,90х₂ (2.26)

за умов:

(2.30)

Розв'язання. Графічну інтерпретацію задачі подано на рис. 2.15. Множина допустимих її розв'язків необмежена.

Для вектора = (0,4; 0,9) можна змінити масштаб, наприклад, = (200; 450).

Найменшого значення цільова функція Z досягає в точці А, що лежить на перетині граничних прямих, які відповідають обмеженням (2.27) та (2.28). Визначимо її координати:

Отже, Х^* = (375; 125); min Z = 0,4 · 375 + 0,9 · 125 = 262,5.

Згідно з відшуканим оптимальним планом задачі для того, щоб отримати 500 кг кормової суміші мінімальної вартості (262,50 у. о.), потрібно взяти 375 кг зерна та 125 кг соєвих бобів.

За такого співвідношення компонентів кормової суміші вимоги до її поживності виконуватимуться:

0,10 · 375 + 0,50 · 125 = 100 кг білка, що становить рівно 20 % загальної маси суміші;

0,02 · 375 + 0,08 · 125 = 17,5 кг клітковини в кормовій суміші, що становить 3,5% її маси і не перевищує 5%.

Рис. 2.15

12. Графічний метод для задач ЛП n-вимірного простору при

Нехай кількість змінних n

число обмежень m,

.

Дві з n змінних, наприклад х₁ та х₂ вільні, інші m базисні

рівнянь вигляду:

Оскільки , то