ляді системи двох нерівностей
ЦФ при фіксованому значенні визначає на площині пряму лінію. Змінюючи значення L, ми отримаємо сімейство паралельних прямих, званих лініями рівня.
Це пов'язано з тим, що зміна значення L спричинить зміну лише довжини відрізка, що відсікається лінією рівня на осі (початкова ордината), а кутовий коефіцієнт прямої залишиться постійним. Тому для вирішення буде досить побудувати одну з ліній рівня, довільно вибравши значення L.
Вектор з координатами з коефіцієнтів ЦФ при і перпендикулярний до кожної з ліній рівня (див. рис. 2.1). Напрям вектора збігається з напрямком зростання ЦФ, що є важливим моментом для вирішення завдань. Напрямок убування ЦФ протилежно напрямку вектора.
Суть графічного методу полягає в наступному. У напрямку (проти напрямку) вектора в ОДР проводиться пошук оптимальної точки. Оптимальною вважається точка, через яку проходить лінія рівня, відповідна найбільшому (найменшому) значенню функції. Оптимальне рішення завжди знаходиться на кордоні ОДР, наприклад, в останній вершині багатокутника ОДР, через яку пройде цільова пряма, або на всій його боці.
При пошуку оптимального рішення задач лінійного програмування можливі такі ситуації: існує єдине рішення задачі; існує нескінченна безліч рішень (альтернативний оптіум); ЦФ не обмежена; область допустимих рішень - єдина точка; задача не має рішень.
4. Методика розв'язування задач лінійного програмування графічним методом
У обмеженнях задачі (1.2) замінити знаки нерівностей знаками точних рівностей і побудувати відповідні прямі.
Знайти і заштрихувати півплощині, дозволені кожним з обмежень-нерівностей задачі (1.2). Для цього потрібно підставити в конкретне нерівність координати якої-небудь точки [наприклад, (0; 0)], і перевірити істинність отриманого нерівності.
Якщо нерівність істинне,
то треба заштрихувати полуплоскость, що містить дану точку;
інакше (нерівність помилкове) треба заштрихувати полуплоскость, що не містить дану точку.
Оскільки і повинні бути невід'ємними, то їх допустимі значення завжди будуть знаходитися вище осі і правіше осі, тобто в I-му квадранті.
Обмеження-рівності дозволяють тільки ті точки, які лежать на відповідній прямій. Тому необхідно виділити на графіку такі прямі.
Визначити ОДР як частина площини, що належить одночасно всім дозволеним областям, і виділити її. При відсутності ОДР задача не має рішень.
Якщо ОДР - не порожнє безліч, то потрібно побудувати цільову пряму, тобто будь-яку з ліній рівня (де L - довільне число, наприклад, кратне і, тобто зручне для проведення розрахунків). Спосіб побудови аналогічний побудові прямих обмежень.
Побудувати вектор, який починається в точці (0; 0) і закінчується в точці. Якщо цільова пряма і вектор побудовані, вірно, то вони будуть перпендикулярні.
При пошуку максимуму ЦФ необхідно пересувати цільову пряму в напрямку вектора, при пошуку мінімуму ЦФ - проти напрямку вектора. Остання по ходу руху вершина ОДР буде точкою максимуму або мінімуму ЦФ. Якщо такої точки (точок) не існує, то можна зробити висновок про необмеженість ЦФ на безлічі планів зверху (при пошуку максимуму) або знизу (при пошуку мінімум).
Визначити координати точки max (min) ЦФ і обчислити значення ЦФ. Для обчислення координат оптимальної точки необхідно вирішити систему рівнянь прямих, на перетині яких знаходиться.
5. Лінійне програмування в електронній таблиці Excel
Пошук рішення.
В електронних таблицях Excel за допомогою функції пошуку рішення можна вести пошук значення в цільовій комірці, зміни значення змінних. При цьому для кожної змінної можна задати обмеження, наприклад верхню межу. Перед тим як запустити пошук рішення, необхідно чітко сформулювати в моделі решаемую проблему, тобто визначити умови, що виконуються при оптимізації.
відправлень точкою при пошуку оптимального рішення є модель обчислення, створена в робочому листі. Програмі пошуку рішення при цьому необхідні наступні дані.
. Цільова осередок - це осередок в моделі обчислення, значення в якій повинно бути максимізувало, мінімізовано або ж рівнятися певного вказаною значенню. Вона повинна містити формулу, яка прямо чи опосередковано посилається на змінювані комірки, або ж самій бути змінною.
. Значення в змінюваних осередках будуть послідовно (методом ітерацій) змінюватися доти, поки не буде отримано потрібне значення в цільовій комірці. Ці осередки, отже, прямо або побічно повинні впливати на значення цільової осередки.
. Ви можете задати як для цільової, так і для змінюваних осе...
