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

Геометрична інтерпретація задач лінійного програмування. Застосування графічного методу для розв’язування двовимірних та деяких тривимірних задач та обмеження щодо його використання. Вивчення алгоритму графічного методу та прикладів розв’язування ЗЛП.

Рубрика Математика
Вид реферат
Язык украинский
Дата добавления 14.12.2013
Размер файла 114,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

Міністерство освіти і науки, молоді та спорту України

Коледж вищого навчального закладу

"Київський університет ринкових відносин"

Реферат на тему:

Графічний метод розв'язування ЗЛП

Виконала:

Студентка 3 курсу

Групи КОВ 01/11

Пінчук Олександра

Київ - 2013

План

1. Геометрична інтерпретація ЗЛП

2. Графічний метод розв'язування ЗЛП

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

1. Геометрична інтерпретація ЗЛП

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

(1)

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

Рис. 1.

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

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

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

2. Графічний метод розв'язування ЗЛП

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

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

Знайти

(2)

за умов:

(3)

(4)

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

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

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

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

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

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

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

Знаходимо багатокутник розв'язків ЗЛП.

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

Будуємо пряму =const, перпендикулярну до вектора .

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

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

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

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

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

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

4. ЗЛП має оптимальний план за необмеженої області допустимих розв'язків.

Розв'язувати графічним методом можна також ЗЛП n-вимірного простору, де n>3, якщо при зведенні системи нерівностей задачі д системи рівнянь шляхом введення додаткових змінних кількість змінних n на дві більше, ніж число обмежень m, тобто n-m=2.

Тоді, як відомо з курсу вищої математики, можна дві з n змінних, наприклад x1 та x2, вибрати як вільні, а інші m зробити базисними і виразити через вільні. Припустимо, що це зроблено. Отримаємо m= n-2 рівнянь вигляду:

Оскільки всі значення , то мають виконуватись умови:

(5)

Припустимо, що в задачі потрібно знайти максимальне значення функції:

Підставивши вирази для з (5) у цей функціонал, зведемо подібні доданки отримаємо вираз лінійної функції F всіх n змінних лише через дві вільні змінні х1 та х2:

де - вільний член, якого в початковому вигляді функціонала не було.

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

графічний лінійний програмування

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

Розв'язати графічним методом ЗЛП

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

Маємо n=7 - кількість змінних, m=5 - кількість обмежень. Виберемо як вільні змінні х1 та х2 і виразимо через них всі інші базисні змінні. З першого рівняння маємо:

(*)

З третього рівняння:

, (**)

а з четвертого:

(***)

Підставляючи (*) в друге рівняння системи і (***) в останнє, розв'язуємо їх відносно х4 та х7. Отримаємо:

Далі за алгоритмом беремо х1=0 та х2=0 - координатні осі; інші обмежуючі прямі знаходимо, узявши х3=0, х4=0, х5=0, х6=0, х7=0. Багатокутник допустимих розв'язків зобразимо на рис.

Знайдемо вигляд функціонала, вираженого через х1 та х2. Для цього знайдені щойно вирази для х3, х4, х5, х6 та х7 через вільні змінні х1 і х2 підставимо у функціонал і, звівши подібні члени, отримаємо: . Відкидаючи вільний член, маємо: . Будуємо вектор (-5,-2), перпендикулярно до нього - пряму . Рухаючи пряму в напрямку, протилежному (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму - А.

У точці А перетинаються 2 обмежуючі прямі: х6=0 та х7=0.

Отже для відшукання її координат необхідно розв'язати систему рівнянь:

Розв'язком системи є х*1=8,5; х*2=5. Підставивши ці значення у відповідні вирази, знайдемо оптимальні значення базисних змінних:

х*3=0,5; х*4=16,5; х*5=17,5; х*6=0; х*7=0.

Підстановкою значень х*1 та х*2 в лінійну функцію отримуємо значення цільової функції:

Размещено на Allbest.ru

...

Подобные документы

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

    курсовая работа [739,5 K], добавлен 05.05.2011

  • Дослідження предмету і сфери застосування математичного програмування в економіці. Класифікація задач цієї науки. Загальна задача лінійного програмування, деякі з методи її розв’язування. Економічна інтерпретація двоїстої задачі лінійного програмування.

    курс лекций [59,9 K], добавлен 06.05.2010

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

    дипломная работа [7,5 M], добавлен 20.08.2010

  • Послідовність графічного розв'язання задачі лінійного програмування. Сумісна система лінійних нерівностей, умови невід'ємності, визначення півплощини з граничними прямими. Графічний метод для визначення оптимального плану задачі лінійного програмування.

    задача [320,6 K], добавлен 31.05.2010

  • Дослідження історії виникнення та розвитку координатно-векторного методу навчання розв'язування задач. Розкриття змісту даного методу, розгляд основних формул. Розв'язання факультативних стереометричних задач з використанням координатно-векторного методу.

    курсовая работа [2,5 M], добавлен 10.04.2011

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

    контрольная работа [298,3 K], добавлен 20.11.2009

  • Історія виникнення методу координат та його розвиток. Канонічні рівняння прямої. Основні векторні співвідношення і формули, які використовуються для розв'язування стереометричних задач. Розробка уроку з використанням координатно-векторного методу.

    дипломная работа [2,5 M], добавлен 05.05.2011

  • Розгляд теоретичних основ рівнянь з параметрами. Основні види даних рівнянь. Аналітичний та графічний методи розв’язування задач із використанням формул, властивостей функцій. Ознайомлення із системою розв’язування задач з параметрами для 9 класу.

    курсовая работа [605,9 K], добавлен 29.04.2014

  • Теоретичні основи розв’язування рівнянь з параметрами. Функція пряма пропорційність. Загальне поняття про аналітичний та графічний метод. Дробово-раціональні рівняння з параметрами, що зводяться до лінійних. Система розв’язування задач для 9 класу.

    курсовая работа [596,8 K], добавлен 21.03.2013

  • Задача Коші і крайова задача. Двоточкова крайова задача для диференціального рівняння другого порядку. Види граничних умов. Метод, заснований на заміні розв’язку крайової задачі розв’язком декількох задач Коші. Розв'язування систем нелінійних рівнянь.

    презентация [86,2 K], добавлен 06.02.2014

  • Розв'язання системи лінійних рівнянь методом повного виключення змінних (метод Гаусса) з використанням розрахункових таблиць. Будування математичної моделі задачі лінійного програмування. Умови для застосування симплекс-методу. Розв'язка спряженої задачі.

    практическая работа [42,3 K], добавлен 09.11.2009

  • Основні етапи розв'язування алгебраїчних рівнянь: аналіз задачі, пошук плану розв'язування та його здійснення; перевірка та розгляд інших способів виконання. Раціоналізація розв'язування алгебраїчних рівнянь вищих степенів методом заміни змінних.

    курсовая работа [229,8 K], добавлен 13.05.2013

  • Теорія графів та її використання у різних галузях. У фізиці: для побудови схем для розв’язання задач. У біології: для розв’язання задач з генетики. Спрощення розв’язання задач з електротехніки за допомогою графів. Математичні розваги і головоломки.

    научная работа [2,1 M], добавлен 10.05.2009

  • Поняття та значення симплекс-методу як особливого методу розв'язання задачі лінійного програмування, в якому здійснюється скерований рух по опорних планах до знаходження оптимального рішення. Розв'язання задачі з використанням програми Simplex Win.

    лабораторная работа [264,1 K], добавлен 30.03.2015

  • Теорема Куна-Такера. Побудування функції Лагранжа. Задача квадратичного програмування. Узагальнення симплексного метода лінійного програмування згідно методу Біла. Правила переходу від однієї таблиці до іншої. Система обмежень у допустимої області.

    курсовая работа [252,9 K], добавлен 08.05.2014

  • Суть принципу Діріхле та найпростіші задачі, пов’язані з ним. Використання методів розв’язування математичних задач олімпіадного характеру при вивченні окремих тем шкільного курсу математики та на факультативних заняттях. Індукція в геометричних задачах.

    дипломная работа [239,7 K], добавлен 15.03.2013

  • Поняття математичної та арифметичної задачі, ступені у навчанні розв’язування. Аналіз системи математичних задач, які вивчаються в початкових класах. Математична задача як засіб активізації учіння. Індивідуальний підхід до дитини і диференціація завдань.

    курсовая работа [46,9 K], добавлен 25.12.2014

  • Неперервність функцій в точці, області, на відрізку. Властивості неперервних функцій. Точки розриву, їх класифікація. Знаходження множини значень функції та нулів функції. Розв’язування рівнянь. Дослідження функції на знак. Розв’язування нерівностей.

    контрольная работа [179,7 K], добавлен 04.04.2012

  • Методи зведення до канонічної форми задач лінійного програмування. Визначення шляхів знаходження екстремумів функцій графічним способом. Побудова початкового опорного плану методом "північно-західного" напрямку. Складання двоїстої системи матриць.

    контрольная работа [262,0 K], добавлен 08.02.2010

  • Опис одного з поширених ітераційних методів, методу хорда — ітераційного методу знаходження кореня рівняння, який ще має назви метод лінійного інтерполювання, метод пропорційних частин, або метод хибного положення. Задачі для самостійного розв’язування.

    реферат [336,8 K], добавлен 04.12.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.