Міністерство Освіти Російської Федерації
Тюменський Державний Нафтогазовий Університет філію в місті Ішимі
Курсова робота з програмування на тему:
Лінійне програмування: рішення задач графічним методом
Виконав:
студент 1 курсу
АМУ-02. Афанасьєв В. Ю.
Перевірив:
Андреенко О.В.
Дата здачі «» червня 2003р.
Оценка_______________
Подпісь______________
Ішим 2003
Зміст:
Вступ 3
Гол 1Математіческіе основи рішення задачі лінійного програмуванняграфічним способом 4
1.1 Математичний апарат 4
1.2 Геометрична інтерпретація задачі лінійного програмування. 5
1.3 Етапи рішення графічного методу задач лінійного програмування 7
Гол 2 Рішення завдань лінійного програмування графічним способом на ЕОМ
15
2.1 Опис роботи програми 15
2.1 Текст програми 20
Висновок 29
Література 31
Рецензія 33
Введення
Лінійне програмування - це наука про методи дослідження івідшукання найбільших і найменших значень лінійної функції, на невідоміякої накладено лінійні обмеження. Таким чином, задачі лінійногопрограмування відносяться до задач на умовний екстремум функції.
Здавалося б, що для дослідження лінійної функції багатьох змінних наумовний екстремум достатньо застосувати добре розроблені методиматематичного аналізу, однак неможливість їх використання можнадосить просто проілюструвати.
Дійсно, шлях необхідно дослідити на екстремум лінійнуфункцію
Z = С1х1 + С2х2 + ... + СNxN при лінійних обмеженнях a11x1 + a22x2 + ... + A1NХN = b1 a21x1 + a22x2 + ... + A2NХN = b2
. . . . . . . . . . . . . . . aМ1x1 + aМ2x2 + ... + AМNХN = bМ
Так як Z - лінійна функція, то Z = Сj, (j = 1, 2, ..., n), то всекоефіцієнти лінійної функції не можуть бути рівними нулю, отже,всередині області, утвореної системою обмежень, екстремальні точки неіснують. Вони можуть бути на межі області, але досліджувати точки кордонунеможливо, оскільки приватні похідні є константами.
Для вирішення задач лінійного програмування треба було створенняспеціальних методів. Особливо широке поширення лінійнепрограмування отримало в економіці, так як дослідження залежностейміж величинами, що зустрічаються в багатьох економічних завданнях, приводитьдо лінійної функції з лінійними обмеженнями, накладеними на невідомі.
Гол 1Математіческіе основи рішення задачі лінійного програмування графічним способом
1.1 Математичний апарат
Для розуміння всього подальшого корисно знати і уявляти собігеометричну інтерпретацію завдань лінійного програмування, якуможна дати для випадків n = 2 та n = 3.
Найбільш наочна ця інтерпретація для випадку n = 2, тобто для випадкудвох змінних і. Хай нам задана задача лінійногопрограмування в стандартній формі
| | (1.1 |
| | 9) |
Візьмемо на площині декартову систему координат і кожній парі чисел
поставимо у відповідність точку на цій площині.
Звернімо передусім увагу на обмеження і. Вони з усієїплощині вирізають лише її першу чверть (див. рис. 1). Розглянемо тепер,які області відповідають нерівностей виду. Спочатку розглянемообласть, що відповідає рівності. Як Ви, звичайно, знаєте, цепряма лінія. Будувати її простіше всього по двом точкам.
Нехай. Якщо взяти, то вийде. Якщо взяти, товийде. Таким чином, на прямий лежать дві точки і.
Далі через ці дві точки можна по лінійці провести пряму лінію (дивисьмалюнок 2).
Якщо ж b = 0, то на прямий лежить точка (0,0). Щоб знайти іншу точку,можна взяти будь-яке відмінне від нуля значення і обчислитивідповідне йому значення.
Ця побудована пряма розбиває всю площину на дві півплощини. Уоднієї її частини, а в іншій навпаки. Дізнатися, у якійпівплощини який знак має місце найпростіше подивившись, якомунерівності задовольняє якась точка площині, наприклад, початоккоординат, тобто точка (0,0).
1.2 Геометрична інтерпретація задачі лінійного програмування.
Розглянемо задачу ЛП у стандартній формі запису:
max f (X) = с1х1 + с2х2 + ... + Спхп (*) при обмеженнях а11х1 + а12х2 + ... + а1nхn? b1 а21х1 + а22х2 + ... + а2nхn? b2
... ... ... ... ... ... ... ... ... ... ... .. аm1х1 + аm2х2 + ... + аmnхn? bm ХJ? 0, j = 1, 2, ..., n.
Розглянемо це завдання на площині, тобто при п = 2. Нехай системанерівностей (**), (***) спільно (має хоча б одне рішення): а11х1 + а12х2? b1 а21х1 + а22х2? b2
... ... ... ... .. аm1х1 + аm2х2? bm x1? 0; х2? 0.
Кожне нерівність цієї системи геометрично визначає півплощиниз граничної прямий аi1х1 + аi2х2? bi i = 1, m. Умови точністьвизначають півплощини відповідно з граничними прямими x1 = 0; х2 =
0 .. Система спільно, тому півплощини, як опуклі множини,перетинаючись, утворюють загальну частину, що є опуклим множиною іявляє собою сукупність точок, координати кожної з якихскладають рішення даної системи. Сукупність цих точок називаютьбагатокутників рішень. Це може бути точка, відрізок, промінь, замкнутийбагатокутник, необмежена багатокутна область.
Якщо в системі обмежень (**) - (***) n = 3, то кожне нерівністьгеометрично представляє півпростір тривимірного простору,гранична площина якого аi1х1 + аi2х2 + аi3х1? bi, а умовиточність - півпростору з граничними площинамивідповідно xi = 0 (i = 1, 2, 3). Якщо система обмежень спільний, тоці півпростору, як опуклі множини, перетинаючись, утворюють утривимірному просторі спільну частину, яка називається багатогранниківрішень.
Нехай в системі (**) - (***) п> 3, тоді кожне нерівність визначаєпівпростір n-мірного простору з граничної гіперплоскостью аi1х1 +аi2х2 + ... + аinхn? bi i = 1, т, а умови точність --півпростору з граничними гіперплоскостямі xj = 0, j = 1, n.
Якщо система обмежень спільний, то за аналогією з тривимірнимпростором вона утворює спільну частину n-мірного простору, званубагатогранників рішень, тому що координати кожної його точки єрішенням.
Таким чином, геометрично задача лінійного програмуванняє відшукання такої точки багатогранника рішень, координатиякої доставляють лінійної функції мінімальне значення, причомудопустимими рішеннями служать всі крапки багатогранника рішень.
1.3 Етапи рішення графічного методу задач лінійного програмування
Графічний метод заснований на геометричній інтерпретації завданнялінійного програмування і застосовується в основному при вирішенні завданьдвовимірного простору і лише деяких завдань тривимірного простору,тому що досить важко побудувати багатогранник рішень, який утворюєтьсяв результаті перетину півпростір. Завдання простору розмірностібільше трьох зобразити графічно взагалі неможливо.
Нехай задача лінійного програмування задана в двовимірномупросторі, тобто обмеження містять дві змінні.
Якщо в ЗЛП обмеження задані у вигляді нерівностей з двома змінними,вона може бути вирішена графічно. Графічний метод розв'язання ЗЛП складається знаступних етапів.
Етап 1.
Спочатку на координатної площини x1Ox2 будується допустимабагатокутна область (область допустимих рішень, область визначення),відповідна обмежень:
| | (1.3 |
| | 1) |
Не наводячи суворих доказів, вкажемо ті випадки, які тут можутьвийде.
1. Основний випадок - виходять область має вигляд обмеженого опуклого багатокутника (рис. 3а )).
2. Неосновний випадок - виходить необмежений опуклий багатокутник, що має вигляд, подібний до зображеного на рис. 3.б. Подібна ситуація, наприклад, вийде, якщо в розглянутому вище прикладі прибрати обмеження. Решта буде необмеженим опуклим багатокутників.
Нарешті, можливий випадок, коли нерівності (1.31) суперечать одинодному, і допустима область взагалі порожня.
Розглянемо теорію на конкретному прикладі:
Знайти допустиму область задачі лінійного програмування,що визначається обмеженнями
| | (1.3 |
| | 2) |
Рішення:
1. Розглянемо пряму. При, а при. Таким чином, ця пряма проходить через точки (0,1) та (-1,0). Беручи отримаємо, що
-0 +0
