![]()
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів
Контакти
Тлумачний словник Авто Автоматизація Архітектура Астрономія Аудит Біологія Будівництво Бухгалтерія Винахідництво Виробництво Військова справа Генетика Географія Геологія Господарство Держава Дім Екологія Економетрика Економіка Електроніка Журналістика та ЗМІ Зв'язок Іноземні мови Інформатика Історія Комп'ютери Креслення Кулінарія Культура Лексикологія Література Логіка Маркетинг Математика Машинобудування Медицина Менеджмент Метали і Зварювання Механіка Мистецтво Музика Населення Освіта Охорона безпеки життя Охорона Праці Педагогіка Політика Право Програмування Промисловість Психологія Радіо Регилия Соціологія Спорт Стандартизація Технології Торгівля Туризм Фізика Фізіологія Філософія Фінанси Хімія Юриспунденкция |
|
||||||||||||||||||||||||||||||||||||||||||
Геометрична інтерпретація ЗЛП. Графічний метод розв’язуванняДля того, щоб краще зрозуміти суть розв’язування ЗЛП, яка записана в симетричній формі, з’ясуємо геометричний зміст системи лінійних нерівностей з двома невідомими. Визначення 1.4. Множина Розглянемо спочатку одну лінійну нерівність з двома невідомими Для визначення конкретної півплощини вибираємо довільну точку і перевіряємо чи правильна нерівність. Для зручності вибираємо Наприклад, розв’язком нерівності Рис.1.2
Рис.1.3 В першому випадку шукана півплощина лежить нижче прямої В найпростішому випадку система лінійних нерівностей з двома невідомими складається з двох нерівностей Ця система називається сумісною, якщо існують такі числові значення невідомих
Рис.1.4 В свою чергу, розв’язком системи нерівностей
Рис. 1.5 Припустимо тепер, що задана деяка система лінійних нерівностей з невідомими
Сукупність розв’язків кожної з нерівностей цієї системи геометрично зображається множиною точок деякої півплощини, а сукупність всіх розв’язків системи (1.2) представляє собою деяку множину точок перетину (спільну частину) цих півплощин, границя якої складається з відрізків відповідних прямих. Оскільки півплощина є опуклою множиною, то і множина розв’язків теж є опуклою. Назвемо її многокутною областю. Її також називають областю розв’язків системи нерівностей (1.2), або многокутником розв’язків. Зауважимо, що область розв’язків може бути многокутником, нескінченною множиною, смугою, що міститься між двома паралельними прямими, прямою, променем, відрізком, точкою, або порожньою множиною.
Приклад 1.2. Побудувати многокутник розв’язків системи нерівностей: Розв’язок. Записуємо рівняння граничних прямих
Рис.1.6 Враховуючи вищенаведені зауваження, переходимо до розв’язування прикладу 1.1. Записуємо рівняння граничних прямих: Підставляючи в кожну нерівність системи (1.1) Враховуючи умови невід’ємності, отримаємо, що перетин (спільна частина) розглянутих півплощин представляє собою многокутник ОАВСD (рис.1.7)
Рис.1.7 Будуємо вектор Отже, максимальна сума, отримана від реалізації прикрас, дорівнює 10 тис.грн. З них: Цей метод розв’язування називається графічним і використовується для випадку, коли кількість невідомих Сформулюємо тепер ЗЛП з двома змінними і вкажемо алгоритм її розв’язування. Отже, ЗЛП в симетричній формі формулюється так: знайти найбільше значення функції
при обмеженнях
Як зазначалося вище, область розв’язків задачі (1.3) – (1.5) може бути многокутником, нескінченною областю, смугою, що міститься між двома паралельними прямими, точкою або порожньою множиною. Функція (1.3) представляє собою на площинні · єдиний розв’язок – координати точки А (рис.1.10.a); · нескінченну множину розв’язків – координати будь-якої точки, що належить відрізку АВ (рис.1.10.б); · функція а) б) в) г) Рис. 1.8 Рис.1.9 а) б) в) Рис.1.10 Розв’язування ЗЛП графічним методом проводиться в наступній послідовності: 1) записують рівняння граничних прямих 2) визначають півплощину, яка відповідає вихідним обмеженням-нерівностям. Для цього беруть будь-яку точку і її координати підставляють в ліву частину обмеження-нерівності. Якщо вона при цьому перетворюється в правильну, то шуканою буде півплощина, яка містить цю точку, якщо ні, то шуканою буде півплощина, якій дана точка не належить; 3) виділяють область допустимих розв’язків задачі як спільну частину 4) будують вектор 5) визначаємо точку екстремуму на многокутнику розв’язків шляхом паралельного переміщення допоміжної прямої 6) знаходимо координати точки екстремуму і значення функції
Контрольні запитання та задачі 1. Назвіть основні типи планово-виробничих і економічних задач та дайте їх коротку характеристику. 2. Що називають математичною моделлю задачі? 3. Які змінні називають керованими? 4. Яка функція називається цільовою? 5. В чому суть керування економічним процесом (в термінах цільової функції)? 6. Як економічна задача зводиться до задачі на знаходження екстремального значення деякої функціональної залежності? 7. Дайте визначення допустимого та оптимального розв’язку? 8. Які задачі відносяться до ЗЛП? 9. Які ви знаєте форми запису ЗЛП? Дайте їх коротку характеристику. 10. Як відбувається перехід від однієї форми запису ЗЛП до іншої? 11. Чому для розв’язування ЗЛП не можна застосовувати методи диференціального числення? 12. Яка множина називається опуклою? 13. Який вигляд може мати область допустимих розв’язків ЗЛП з двома змінними? 14. Що представляє собою на площині 15. Що собою може представляти множина розв’язків ЗЛП? 16. Вкажіть основні етапи розв’язування ЗЛП графічним методом. 17. Їдальня реалізує три види власної продукції, використовуючи ресурси А1, А2, А3. Для виготовлення однієї партії виробів першого виду потрібно відповідно 3, 2, 4 одиниці ресурсів А1, А2, А3; для виготовлення однієї партії виробів другого виду – 2, 5, 3; третього виду — 6, 3, 5. Запаси ресурсів відповідно рівні: А1 – 76, А2 – 73, А3 – 83 одиниці. Прибуток від реалізації одиниці виробу першого, другого і третього видів становить 30, 40, 45 коп. Скласти математичну модель для визначення плану виробництва, що забезпечує максимальний прибуток, і записати задачу в канонічній формі. 18. Щоденно в місто привозять 20 т картоплі з трьох господарств: з першого – за ціною 650 грн., з другого – 660 грн., з третього – 610 грн. за тонну. Для своєчасного постачання картоплі необхідно затратити 9 год. 10 хв. на її навантаження. Відомо, що на навантаження 1 т картоплі в першому господарстві витрачається 20 хв., в другому – 30 хв., в третьому – 40 хв. Скласти математичну модель задачі мінімізації вартості завезеної картоплі, якщо з першого господарства можна завезти не більше 10 т, з другого – 6 т, з третього – 8 т, і записати задачу в канонічній формі. 19. Скласти математичну модель для визначення оптимального добового раціону відгодівлі свиней, якщо раціон однієї голови повинен містити 2,4 кг кормових одиниць, 360 г білка, 10 мг каротину. Раціон складається з трьох видів кормів: ячменю, бобів і трав’яної муки. В 1 кг ячменю міститься 0,8 кг кормових одиниць, 80 г білка, 2 мг каротину; в 1 кг бобів відповідно 0,9 кг, 180 г і 3 мг; в 1 кг муки – 0,6 кг, 100 г і 5 мг. Ціна 1 кг ячменю – 50 коп., бобів – 80 коп., муки – 65 коп. Критерій оптимальності – мінімум вартості раціону. Представити задачу в канонічній формі. 20. Для виготовлення виробів двох видів придбано 100 кг металу. На виготовлення виробу першого виду витрачається 2 кг металу; а другого –4 кг. Прибуток від реалізації виробу першого виду складає 3 грн., а другого – 2 грн., причому виробів першого виду потрібно виготовити не більше 40 штук, а другого – не більше 20 штук. Скласти математичну модель отримання максимального прибутку від реалізації виробів обох видів і представити задачу в канонічному вигляді. 21. Кондитерська фабрика для виготовлення трьох видів карамелі А, Б, В використовує три основні види сировини: цукор, патоку і фруктове пюре. Норми затрат цукру на виготовлення 1 т карамелі кожного виду відповідно рівні: 0,8; 0,5; 0,6 т; патоки – 0,4; 0,4; 0,3 т; фруктового пюре – 0; 0,1; 0,1 т. Запаси цукру – 80 т, патоки – 60 т, фруктового пюре – 12 т. Прибуток від реалізації карамелі виду А становить 1080 грн., виду Б – 1120 грн., виду В – 1260 грн. Скласти математичну модель для визначення плану виробництва, що забезпечує максимальний прибуток від діяльності фабрики, і записати задачу в симетричній формі. 22. Зобразити півплощини, які задаються нерівностями: а) 3х1–4х2+10 23. Знайти область розв’язків системи нерівностей:
24. Знайти найбільше та найменше значення функції f при умові, що змінні
1.3. Опорні плани ЗЛП Розглянутий в 1.2 графічний метод застосовується до досить вузького класу ЗЛП. Універсальним методом розв’язування ЗЛП є симплексний метод. Перш ніж перейти до його розгляду, введемо нові поняття. Визначення 1.5. Впорядкована система Координати числового вектора можна розміщувати в рядок Два числові вектори називаються рівними, якщо рівні їх відповідні координати. При додаванні двох числових векторів відповідні координати додаються, а при множенні числового вектора на число кожна координата множиться на це число. Визначення 1.6. Система векторів Визначення 1.7. Рангом Визначення 1.8. Якщо ранг системи векторів З n-вимірними числовими векторами ми зустрічатимемось при розв’язуванні лінійних рівнянь з n-невідомими, а також систем Справді, лінійне рівняння з Визначення 1.9. Розв’язком системи називається кожний n-вимірний числовий вектор Систему рівнянь, яка має хоча б один розв’язок, називають сумісною, яка не має жодного розв’язку – несумісною. Сумісна система рівнянь, яка має один розв’язок, називається визначеною, а яка має безліч розв’язків – невизначеною. Згідно з теоремою Кронекера-Капеллі сумісна система рівнянь є невизначеною, якщо ранг матриці системи менший від кількості невідомих. Завдяки введеному поняттю n-вимірного числового вектора, ЗЛП записану в загальній, симетричній та канонічній формах, можна записувати в векторній формі. Зокрема, канонічна задача в векторній формі має вигляд: знайти найбільше значення функції
де Зауваження 1.2. Для того, щоб можна було говорити про відшукання оптимального розв’язку вищенаведеної ЗЛП, треба, щоб система (1.6) була сумісною і мала безліч розв’язків. А це можливо в випадку, коли ранг Нехай Визначення 1.10. Змінні, що відповідають Припустимо, що один із базисів утворюють перші r векторів
в якому базисні змінні Запис (1.7) задає загальний розв’язок системи (1.6). Надаючи вільним змінним Визначення 1.11. Частинний розв’язок, одержаний із загального при нульових значеннях вільних змінних, назвемо базисним розв’язком системи (1.6). В цьому випадку з (1.7) знаходимо Оскільки кількість базисів не перевищує Визначення 1.12.Якщо в базисному розв’язку всі базисні змінні приймають невід’ємні значення, то його називають опорним розв’язком або опорним планом. З даного визначення випливає, що опорний план не може містити більше ніж r додатних компонент. Визначення 1.13. Опорний план, який містить рівно r відмінних від нуля компонент, називається невиродженим, якщо хоча б одна з базисних компонент дорівнює нулю, опорний план називається виродженим. Сформулюємо ряд теорем, які обґрунтовують існування опорного плану для ЗЛП. Теорема 1.1. Для існування хоча б одного опорного плану ЗЛП необхідно і досить, щоб ранг її сумісної системи обмежень, включаючи і обмеження змінних по знаку, дорівнював n. Теорема 1.2. Якщо ЗЛП має розв’язок і серед планів цієї задачі є опорний, то хоча б один з них буде оптимальним. Теорема 1.3. Якщо ЗЛП має хоча б один план і шуканий екстремум лінійної форми обмежений на множині планів, така ЗЛП має хоча б один оптимальний план. Теорема 1.4. Якщо множина планів ЗЛП є непорожньою, то серед них є хоча б один опорний план, причому опорних планів може бути не більше, ніж Для того, щоб дати геометричну інтерпретацію опорних планів, нам будуть потрібні деякі відомості з теорії систем лінійних нерівностей з Сукупність Множина всіх точок Відстань між двома точками
Точковий лінійний Нехай Нехай Геометричне місце точок Множина Зв’язна відкрита множина Точка Нехай Визначення1.14. Якщо кожній точці Розглянемо тепер нерівність Тоді область розв’язків системи
представляє деяку область Область Таким чином, плани ЗЛП трактують як точки многогранника планів, а опорні плани є його вершинами. Має місце Теорема1.5. Кожному опорному плану ЗЛП відповідає вершина многогранника планів, і, навпаки, кожній вершині многогранника планів відповідає опорний план ЗЛП. Наведена теорема встановлює відповідність між опорними планами ЗЛП і вершинами многогранника планів. Зокрема, з неї випливає, що сукупність опорних планів співпадає з системою вершин многогранника планів. Оскільки опорних планів не більше ніж Визначення1.15. Точка Вершиною (крайньою кутовою точкою) опуклої множини Вершини опуклого многогранника мають властивість: будь-яку точку Розглянуту властивість вершин сформулюємо мовою планів: будь-який план ЗЛП можна представити як опуклу лінійну комбінацію її опорних планів. Із цього випливає, що для дослідження множини планів ЗЛП достатньо вивчати лише опорні плани. Теорема1.6. Лінійна функція, визначена на опуклому n-вимірному многограннику, досягає найбільшого значення в вершині цього многогранника. Якщо лінійна функція досягає найбільшого значення більш ніж в одній вершині, то вона досягає такого ж значення в будь-якій точці, яка є опуклою лінійною комбінацією цих вершин. Якщо функцію Оскільки кожній вершині многогранника відповідає опорний план, то можна сказати, що оптимальний план розв’язуваної ЗЛП співпадає принаймні з одним з її опорних планів. Вектор Враховуючи вищесказане, можна дати наступну геометричну інтерпретацію ЗЛП: знайти точку Контрольні запитання та задачі 1. Дайте визначення n-вимірного числового вектора. 2. Яка система векторів 3. Що називається рангом системи векторів? 4. Що називається базисом системи векторів? 5. Що називають розв’язком лінійного рівняння з 6. Що називають розв’язком системи 7. Яку систему рівнянь називають сумісною (несумісною), визначеною (невизначеною)? 8. В якому випадку система рівнянь є невизначеною? 9. Як записується канонічна ЗЛП в векторній формі? 10. Які змінні називають базисними, а які – вільними? 11. Який розв’язок називають загальним, частинним, базисним і опорним? 12. Який опорний план називається невиродженим, а який виродженим? 13. Сформулюйте необхідну і достатню умову існування опорного плану. 14. Яке рівняння визначає гіперплощину в просторі 15. Що собою представляє множина розв’язків системи 16. Дайте геометричну інтерпретацію плану і опорного плану ЗЛП 17. Дайте визначення опуклої комбінації точок 18. Дайте визначення вершини опуклої множини. Читайте також:
|
|||||||||||||||||||||||||||||||||||||||||||
|