Алгоритм розв’язування задач лінійного
МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ ЕКОНОМІЧНИЙ УНІВЕРСИТЕТ
КРИВОРІЗЬКИЙ ЕКОНОМІЧНИЙ ІНСТИТУТ
МЕТОДИЧНІ ВКАЗІВКИ
до самостійного вивчення теми
“Графічний метод розв’язування задач
лінійного програмування”
з дисципліни
“Математичне програмування ”
ЗАТВЕРДЖЕНО
на засіданні кафедри
вищої математики
“____”__________2002 р.
Протокол № _____
Кривий Ріг
КЕІ КНЕУ – 2002
Методичні вказівки до самостійного вивчення теми “Графічний метод розв’язування задач лінійного програмування” з дисципліни “Математичне програмування”. /Укладачі: Щербак А.Ф., Глоба Н.Г., Кривий Ріг, Криворізький економічний інститут, 2002 – 20 с./
Укладачі: Щербак А.Ф., канд. техн. наук, доцент;
Глоба Н.Г., старший викладач.
Рецензент: Кондратенко Л.П., канд. фіз. – мат наук, доцент.
Зміст.
1. Основні поняття та означення……………………………………………….4
2. Алгоритм розв’язування задач лінійного програмування
графічним методом………………………..………………………………...6
3. Приклади………………………………………………………………………8
4. Завдання для самостійного розв’язування…………………………………16
Література ……………………………………………………………………….20
Основні поняття та означення.
Графічний метод розв’язування задач лінійного програмування грунтується на геометричному зображенні математичної моделі задачі в системі координат. Але його використання обмежене у міру зростання кількості змінних в задачі, оскільки таку 
- вимірну задачу графічно зобразити в просторі неможливо. Тому в основному цей метод використовується для задач, які мають дві – три змінні, або якщо різниця між кількістю змінних 
та кількістю обмежень задовольняє умові 
. У цьому разі математичну модель задачі потрібно перетворити так, щоб вона мала вигляд двовимірної.
|
|
|
Основна перевага графічного методу полягає в простому зображенні та наочності ходу розв’язування.
Графічний метод реалізується в два етапи:
1. етап: побудова ОПР (області припустимих розв’язків).
2. етап: знаходження оптимального розв’язку.
Зауважимо, що в процесі побудови ОПР можливі такі випадки:
§ 
Порожня область (рис. 1). При цьому обмеження в математичній моделі несумісні і згідно з цим задача не має розв’язку.
 |
0 
Рис. 1.
§ Опуклий многогранник(рис. 2). При цьому обмеження сумісні та зображують область, до якої входять допустимі розв’язки. В цьому випадку задача має як мінімум, так і максимум.
|
|
|
 | |||
 | |||
0
Рис. 2.
§ Необмежена область з одного боку (рис. 3). При цьому існує тільки мінімум або максимум, або взагалі розв’язку не існує.
 |
0
Рис. 3.
При розв’язуванні задач лінійного програмування графічним методом використовують градієнт цільової функції. Слід нагадати, що градієнтом функції називається вектор, координатами якого є частинні похідні цієї функції. Градієнт функції в будь – якій точці вказує в якому напрямку знаходиться точка, в якій функція набуває найбільшого значення.
Алгоритм розв’язування задач лінійного
Дата добавления: 2021-03-18; просмотров: 65; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!