Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


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


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






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

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

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

Загальна лінійна економіко-математична модель економічних процесів та явищ – так звана загальна задача лінійного програмування подається у вигляді:

(3.1)

за умов:

(3.2)

(3.3)

Отже, потрібно знайти значення змінних x1, x2, …, xn, які задовольняють умови (3.2) і (3.3), і цільова функція (3.1) набуває екстремального (максимального чи мінімального) значення.

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

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

Вектор Х = (х1, х2, …, хn), координати якого задовольняють систему обмежень (3.2) та умови невід’ємності змінних (3.3), називається допустимим розв’язком (планом) задачі лінійного програмування.

Допустимий план Х = (х1, х2, …, хn) називається опорним планом задачі лінійного програмування, якщо він задовольняє не менше, ніж m лінійно незалежних обмежень системи (3.2) у вигляді рівностей, а також обмеження (3.3) щодо невід’ємності змінних.

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

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

Задачу (3.1)—(3.3) можна легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (3.2) всі bi (i = 1, 2, …, m) невід’ємні, а всі обмеження є рівностями.

Якщо якесь bi від’ємне, то, помноживши i-те обмеження на
(– 1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності аi1х1+аi2х2+…+аinxnbi, то останню завжди можна звести до рівності, увівши додатковузмінну xn+1:

ai1x1+ai2x2+…+ ain xn + xn + 1 = bi.

Аналогічно обмеження виду аk1x1 + ak2x2 + … + aknxnbk зводять до рівності, віднімаючи від лівої частини додаткову змінну хn+2, тобто:

ak1x1 + ak2x2 + … + aknxnxn + 2 = bk (хn+1 ≥ 0, хn+2 ≥ 0).

Задачу лінійного програмування зручно записувати за допомогою знака суми «S». Справді, задачу (3.1)-(3.3) можна подати так:

 

за умов:

(3.4)

Ще компактнішим є запис задачі лінійного програмування у векторно-матричному вигляді:

max(min) Z = CX

за умов:

АХ = А0; (3.5)

Х ≥ 0,

де

 

є матрицею коефіцієнтів при змінних;

— вектор змінних; — вектор вільних членів;

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

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

max(min)Z = CX

за умов:

A1x1 + A2x2 + … + Anxn = A0; (3.6)

X ≥0,

де

 

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

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

(3.7)

 

Кожна нерівність цієї системи геометрично визначає півплощину з граничною прямою ai1x1 + ai2x2 = bi (i=1,2, ..., т). Умови невід’ємності змінних визначають півплощини з граничними прямими х1 = 0 та х2 = 0. Система сумісна, тому півплощини як опуклі множини, перетинаючись, утворюють спільну частину, що є опуклою множиною і являє собою сукупність точок, координати кожної з яких є розв’язком даної системи (рис.3.1).

 

Рисунок 3.1

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

Якщо в системі обмежень (3.7) буде три змінних, то кожна нерівність геометрично визначатиме півпростір тривимірного простору, граничними площинами котрого будуть ai1x1 + ai2x2 + ai3x3 = bi (i = 1, 2, ..., т), а умови невід’ємності – півпростори з граничними площинами хj=0 (j = 1, 2, 3), де і – номер обмеження, а j–— номер змінної. Якщо система обмежень сумісна, то ці півпростори як опуклі множини, перетинаючись, утворять у тривимірному просторі спільну частину, що називається багатогранником розв’язків. Він може бути точкою, відрізком, променем, багатокутником, багатогранником, багатогранною необмеженою областю.

Нехай у системі обмежень (3.7) кількість змінних більша, ніж три: х1, х2,… хn; тоді кожна нерівність визначає півпростір n-вимірного простору з граничною гіперплощиною аi1x1 + ai2x2 + ai3x3 + … +ainxn = bi (i = 1, 2, ..., т). Кожному обмеженню виду (3.7) відповідають гіперплощина та напівпростір, який лежить з одного боку цієї гіперплощини, а умови невід’ємності — півпрос­тори з граничними гіперплощинами хj = 0 (j=1, 2, 3, ..., n).

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

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

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

 

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

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

Таблиця 2.3 – Показники вирощування сільськогосподарських культур

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

 

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

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

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

х2 — шукана площа посіву цукрових буряків, га.

Задача лінійного програмування має такий вигляд:

max Z = 0,7x1 + x2 (3.8)

за умов:

x1 + x2 ≤20; (3.9)

5x1 + 25x2 ≤270; (3.10)

2x1 + 8x2 ≤80; (3.11)

x2 ≥5; (3.12)

x1 ≥0, x2 ≥0. (3.13)

Геометричну інтерпретацію задачі зображено на рис.3.2.

 

Рисунок 3.2 – Область допустимих розв’язків задачі

Область допустимих розв’язків цієї задачі дістаємо так. Кожне обмеження, наприклад х1 + х2 20, задає півплощину з граничною прямою х1 + х2 = 20. Будуємо її і визначаємо півплощину, яка описується нерівністю х1 + х2 20. З цією метою в нерівність х1+х2 20 підставляємо координати характерної точки, скажімо, х1=0 і х2=0. Переконуємося, що ця точка належить півплощині х1+х2 20. Цей факт на рис.3.2 ілюструємо відповідною напрямленою стрілкою. Аналогічно будуємо півплощини, які відповідають нерівностям (3.10)—(3.13). У результаті перетину цих півплощин утворюється область допустимих розв’язків задачі (на рис.3.2 – чотирикутник ABCD). Цільова функція Z = 0,7x1 + x2 являє собою сім’ю паралельних прямих, кожна з яких відповідає певному значенню Z. Зокрема, якщо Z=0, то маємо 0,7х1 + х2 = 0. Ця пряма проходить через початок системи координат. Коли Z=3,5, то маємо пряму 0,7х1 + х2 = 3,5.


Читайте також:

  1. Алгоритм розв’язання задачі
  2. Алгоритм розв’язання розподільної задачі
  3. Алгоритм розв’язування задачі
  4. Алгоритм розв’язування задачі
  5. Алгоритм розв’язування задачі
  6. Алгоритм розв’язування задачі
  7. Алгоритм розв’язування задачі
  8. Алгоритм розв’язування задачі
  9. Алгоритм розв’язування задачі оптимізації в Excel
  10. Аналіз інформації та постановка задачі дослідження
  11. Аналіз та інтерпретація інформації
  12. Аналіз та інтерпретація одержаних даних




Переглядів: 2925

<== попередня сторінка | наступна сторінка ==>
 | Графічний метод розв’язування задач лінійного програмування

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.036 сек.