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


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


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


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


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


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


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


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


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


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



Контакти
 


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






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

У загальному формулюванні зворотну задачу лінійного програмування (ЛП) можна записати так: знайти значення керованих змінних х1, х2, ..., хn , при котрих їх лінійна функція

С1 х1 + С2 х2 + ... + Сn хn

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

a11 х1 + а12 х2 + ... а1n xn £ в1,

a21 х1 + а22 х2 + ... а2n xn = в2,

………………………………

am1 х1 + аm2 х2 + ... аmn xn > вm,

хі ³ 0, і =1,n

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

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

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

Постійні в задачі лінійного програмування мають такі назви: Сі, і=1,n - оцінки задачі, тому що ці постійні немов би “оцінюють” значущість відповідних керованих змінних в цільовій функції; аіj, і=1,n, j=1,m - коефіцієнти задачі; вj, j=1,m - ресурси задачі.

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

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

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

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

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

- інтенсивність польотів на спрямній ділянці повітряної траси не повинна перевищувати допустиму;

- сумарна інтенсивність польотів на “паралельних” ділянках повинна бути не менше заданої (необхідної).

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

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

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

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

 

1.4 Графічне розв’язання задачі лінійного програмування

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

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

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

 

Тип повітряного судна
Кількість суден
Продуктивність одного судна протягом часу, що розглядається    
Прибуток за рахунок використання одного судна    

Аналітичний запис задачі:

30х1+15х2 ® max - цільова функція задачі,

 
 


3x1+2x2 £ 24,

x1 £ 6, обмеження

x2 £ 8 задачі

x1 ³ 0, x2 ³ 0

 

Графічним способом задача ЛП розв’язується у такому порядку.

В системі координат Х1ОХ2 (рис. 1.2) проводимо прямі лінії, що відповідають обмеженням задачі, спочатку враховуючи при цьому тільки знаки рівності. Потім, враховуючи в обмеженнях задачі знаки нерівностей, робимо штриховку з того боку кожної прямої, де розташовані допустимі значення змінних x1, x2. Так одержимо область допустимих значень змінних, яка на рисунку двічі заштрихована.

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

Очевидно, чим більше значення матиме цільова функція, тим далі справа розміститься пряма цільової функції, зміщуючись при цьому паралельно сама собі. Отже, з одного боку, бажано щоб ця пряма була розташована якнайдалі справа, а з іншого боку, вона при цьому повинна мати хоча б одну загальну точку з областю допустимих розв’язків задачі, координати якої і будуть оптимальним розв’язком. На малюнку бачимо, що точкою області допустимих розв’язків, яка максимально віддалена від прямої 30х1+15х2=90, є точка перетину прямих 3х1+2х2=24 і х1=6, вона означена А. Розв’язавши систему рівнянь цих двох прямих, визначимо координати точки А: х1=6, х2=3. При цьому цільова функція приймає значення 225.

Очевидно, можливий випадок, коли пряма цільової функції паралельна одному з відрізків, що обмежують область допустимих розв’язків задачі. Тоді говорять, що рівняння двох таких прямих лінійно залежні, тому що одне з них можна одержати, помноживши або розділивши ліву і праву частини іншого на певне число. Зокрема, у наведеному вище прикладі це мало б місце, якби ліва частина цільової функції мала вигляд 30х1+20х2, тобто була лінійно залежною з функцією-обмеженням задачі 3х1+2х2£24. При цьому оптимальним рішенням задачі були б координати будь-якої точки відрізка, що на малюнку означений АБ. У нашому прикладі це означало б, що перевезення виконувати було б однаково вигідно з використанням повітряних суден обох типів.


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

  1. IV. Закріплення й узагальнення знань
  2. IV. УЗАГАЛЬНЕННЯ І СИСТЕМАТИЗАЦІЯ ВИВЧЕНОГО
  3. IІI. Формулювання мети і завдань уроку. Мотивація учбової діяльності
  4. V. Систематизація і узагальнення нових знань, умінь і навичок
  5. VI. Узагальнення та систематизація знань
  6. АБСТРАГУВАННЯ УЗАГАЛЬНЕННЯ
  7. Алгоритм розв’язання задачі
  8. Алгоритм розв’язання розподільної задачі
  9. Алгоритм розв’язування задачі
  10. Алгоритм розв’язування задачі
  11. Алгоритм розв’язування задачі
  12. Алгоритм розв’язування задачі




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

<== попередня сторінка | наступна сторінка ==>
Основні способи формування цільової функції задачі | Основні положення, на яких базується симплекс-метод розв’язання задач лінійного програмування

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

 

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


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