державних освітніх УСТАНОВА
В«ПРИДНІСТРОВСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ ім. Т.Г. ШЕВЧЕНКО В»
Рибницького ФІЛІЯ
КАФЕДРА В«ФІЗИКИ, МАТЕМАТИКИ ТА ІНФОРМАТИКИВ»
Курсова робота
з дисципліни
"Дослідження операцій "
на тему:
" Рішення задач лінійного програмування геометричним методом "
Виконала:
студентка III курсу
спеціальності "Інформатика з дод. спец. англійська мова "
Ністор А.Г.
Перевірила:
викладач Панченко Т.А.
р. Рибниця
2008
ЗМІСТ
Введення. 3
I. ТЕОРЕТИЧНИЙ РОЗДІЛ .. 4
1.1 Лінійне програмування. 4
1.2 Формулювання завдання. 5
1.3 Основні поняття лінійної алгебри та опуклого аналізу, що застосовуються в теорії математичного програмування. 7
1.4 Математичні основи рішення задачі лінійного програмування графічним способом. 9
1.4.1 Математичний апарат. 9
1.4.2 Геометрична інтерпретація задачі лінійного програмування. 11
1.4.3 Етапи рішення графічного методу задач лінійного програмування 13
II. ПРАКТИЧНИЙ РОЗДІЛ .. 18
Задача № 1. 18
Задача № 2. 21
Задача № 3. 24
Завдання № 4. 27
Завдання № 5. 30
Висновок. 33
Список літератури .. 34
ВСТУП
Лінійне програмування - це наука про методи дослідження та
відшукання найбільших і найменших значень лінійної функції, на невідомі якої накладено лінійні обмеження. Таким чином, задачі лінійного програмування відносяться до завданням на умовний екстремум функції. Здавалося б, що для дослідження лінійної функції багатьох змінних на умовний екстремум досить застосувати добре розроблені методи математичного аналізу, однак неможливість їх використання можна досить просто проілюструвати.
Для вирішення завдань лінійного програмування знадобилося створення спеціальних методів. В даній курсовій роботі буде розглянуто геометричний метод розв'язування задач лінійного програмування. Геометричний метод застосовується в основному при вирішенні завдань двовимірного простору і тільки деяких завдань тривимірного простору, так як досить важко побудувати багатогранник рішень, який утворюється в результаті перетину півпросторів. Задачу простору розмірності більше трьох зобразити графічно взагалі неможливо.
Таким чином, метою даної курсової роботи є: освоїти навички використання геометричного методу для розв'язання задач лінійного програмування. Для цього були поставлені наступні завдання:
1) Вивчити теоретичні відомості, необхідні для рішення задач лінійного програмування геометричним методом.
2) Розібрати алгоритм розв'язання ЗЛП геометричним методом.
3) Вирішити поставлені завдання, використовуючи розглянутий метод рішення задач лінійного програмування.
I. ТЕОРЕТИЧНИЙ РОЗДІЛ
1.1 Лінійне програмування
Лінійне програмування - математична дисципліна, присвячена теорії і методам вирішення завдань про екстремуму лінійних функцій на множинах n-мірного векторного простору, задаються системами лінійних рівнянь і нерівностей.
Лінійне програмування є окремим випадком математичного програмування. Одночасно воно - основа декількох методів вирішення завдань цілочисельного і нелінійного програмування.
Багато властивостей задач лінійного програмування можна інтерпретувати також як властивості многогранників і таким чином геометрично формулювати і доводити їх.
Термін В«програмуванняВ» потрібно розуміти в сенсі В«плануванняВ». Він був запропонований в середині 1940-х років Джорджем Данцигом, одним із засновників лінійного програмування, ще до того, як комп'ютери були використані для вирішення лінійних задач оптимізації.
Математичне формулювання задачі лінійного програмування
Потрібно максимізувати
при умовах при i = 0, 1, 2,. . . , M.
Іноді на x i також накладається деякий набір обмежень у вигляді рівностей, але від них можна позбутися, послідовно висловлюючи одну змінну через інші і підставляючи її в усіх інших рівностях і нерівностях (а також у функції f).
Таке завдання називають "основний" або "стандартної" в лінійному програмуванні.
1.2 Формулювання завдання
Дано лінійна функція Z = С 1 х 1 + С 2 х 2 + ... + С N x N (1.1)
і система лінійних обмежень
a 11 x 1 + a 22 x 2 + ... + A 1N Х N = b 1
a 21 x 1 + A 22 x 2 + ... + A 2N Х N = b 2
. . . . . . . . . . . . . . .
a i1 x 1 + A i2 x 2 + ... + A iN Х N = b i (1.2). . . . . . . . . . . . . . .
a M1 x 1 + A M2 x 2 + ... + A MN Х N = b M
x j 0 (J = 1, 2, ..., n) (1.3)
де а ij , b j і С j - задані постійні величини.
Знайти такі невід'ємні значення х 1 , х 2 , ..., х n , які задовольняють системі обмежень (1.2) і доставляють лінійної функції (1.1) мінімальне значення.
Загальна задача має кілька форм запису.
Векторна форма запису. Мінімізувати лінійну функцію Z = СХ при обмеженнях А 1 х 1 + А 2 x 2 + ... + А N x N = А про , X 0 (1.4)
де С = (с 1 , з 2 , ..., з N ); Х = (х 1 , х 2 , ..., Х N ); СХ - скалярний добуток; вектори A 1 = A 2 =, ..., A N складаються відповідно з коефіцієнтів при невідомих і вільних членах.
Матрична форма записи . Мінімізувати лінійну функцію, Z = СХ при обмеженнях АХ = А 0 Х 0 , де С = (с 1 , з 2 , ..., З N ) - матриця-дані для; А = (а ij ) - матриця системи; Х = (x ij ) - матриця-стовпець, А 0 = (а i ) матриця-стовпець
Запис з допомогою знаків підсумовування. Мінімізувати лінійну функцію Z = С j х j при обмеженнях
0пределеніе 1. Планом або допустимим рішенням задачі лінійного програмування називається Х = (Х 1 , х 2 , ..., х N ), задовольняє умовам (1.2) і (1.3).
0пределеніе 2. План Х = (х 1 , х 2 , ..., х N ) називається опорним, якщо вектори А (i = 1, 2, ..., N), що входять до розкладання (1.4) з позитивними коефіцієнтами х, є лінійно незалежними.
Так як вектори А є N-мірними, то з визначення опорного плану випливає, що число його позитивних компонент не може перевищувати М.
0пределеніе 3. Опорний план називається невироджених, якщо він містить М позитивних компонент, в іншому випадку опорний план називається виродженим.
0пределеніе 4. Оптимальним планом або оптимальним рішенням задачі лінійного програмування називається план, який доставляє найменше (найбільше) значення лінійної функції.
В подальшому розглянуто рішення задач лінійного програмування, пов'язаних з перебуванням мінімального значення лінійної функції. Там, де необхідно знайти максимальне значення лінійної функції, достатньо замінити на...
