Деякі завдання оптимізації в економіці

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Федеральне агентство з освіти
Державна освітня установа вищої професійної освіти
Вятський державний гуманітарний університет
Математичний факультет
Кафедра математичного аналізу і методики викладання математики
Випускна кваліфікаційна робота
Деякі завдання оптимізації в економіці
Виконала:
студентка V курсу математичного факультету
Голомідова Ірина Віталіївна
Науковий керівник:
Ст. викладач кафедри математичного аналізу і МПМ
С. А. Фалелеева.
Рецензент:
кандидат педагогічних наук, ст. викладач кафедри математичного аналізу і МПМ
Л.В. Караулова.
Допущена до захисту в державної атестаційної комісії
«___» __________2005 Р. Зав. кафедрою М.В. Крутіхін
«___»___________ 2005 Декан факультету В.І. Варанкіна
Кіров
2005

Зміст
Введення ................................................. .................................................. 3
1. Математичні моделі в економіці .............................................. ... 4
2. Деякі поняття функцій кількох змінних ...................... 6
3. Завдання математичного програмування
1) Загальна постановка задачі ............................................. ................. 8
2) Завдання лінійного програмування і способи її вирішення ..... 9
3) Двоїста задача .............................................. ...................... 19
4) Завдання нелінійного програмування ..................................... 26
5) Завдання на умовний екстремум ............................................ ........ 31
4. Завдання споживчого вибору.
1) Функція корисності. Бюджетне обмеження. Формулювання завдання споживчого вибору .............................................. ............................ 34
2) Рішення задачі споживчого вибору і його властивості ......... 36
3) Загальна модель споживчого вибору ................................... 39
4) Модель Стоуна .............................................. .............................. 40
Висновок ................................................. ............................................ 42
Бібліографічний список ................................................ ................... 43

Введення
Сучасна математика характеризується інтенсивним проникненням в інші науки, багато в чому цей процес відбувається завдяки поділу математики на ряд самостійних областей. Математика стала для багатьох галузей знань не тільки знаряддям кількісного розрахунку, але також методом точного дослідження й засобом гранично чіткого формулювання понять і проблем. Без сучасної математики з її розвиненим логічним і обчислювальним апаратом був би не можливий прогрес в різних областях людської діяльності.
Економіка як наука про об'єктивні причини функціонування і розвитку суспільства користується різноманітними кількісними характеристиками, а тому увібрала в себе велику кількість математичних методів.
Актуальність даної теми полягає в тому, що в сучасній економіці застосовуються оптимізаційні методи, які становлять основу математичного програмування, теорії ігор, мережевого планування, теорії масового обслуговування та інших прикладних наук.
Вивчення економічних програм математичних дисциплін, що складають основу актуальної економічної математики, дозволяє придбати деякі навички вирішення економічних завдань і розширити знання в цій області.
Метою даної роботи є вивчення деяких оптимізаційних методів, що застосовуються при вирішенні економічної завдань.
При написанні дипломної роботи були поставлені наступні завдання:
· Розгляд деяких економічних завдань і складання математичних моделей.
· Вивчення деяких математичних методів, застосовуваних для вирішення оптимізаційних завдань в економіці.
· Практичне розв'язання завдань.

1. Математичні моделі в економіці
Сучасна економічна теорія включає як природний, необхідний елемент математичні моделі та методи. Використання математики в економіці дозволяє, по-перше, виділити і формально описати найбільш важливі, істотні зв'язки. По-друге, з чітко сформульованих вихідних даних і співвідношень можна зробити висновки, адекватні об'єкту, що вивчається в тій же мірі, що й зроблені передумови. По-третє, методи математики дозволяють індуктивним шляхом отримувати нові знання про об'єкт: оцінити форму та параметри залежностей його змінних, найбільшою мірою відповідні наявними спостереженнями. По-четверте, використання мови математики дозволяє точно і компактно викладати положення економічної теорії, формулювати її поняття.
Математичні моделі використовувалися з ілюстративними дослідженнями ще Ф. Кене (1758г., «Економічна таблиця»), А. Смітом (Класична макроекономічна модель), Д. Ріккардо (Модель міжнародної торгівлі). У XIX столітті великий внесок в моделювання ринкової економіки внесли математики Л. Вальрас, О. Курно, В. Парето та інші. У XX столітті математичні методи моделювання застосовувались дуже широко, з їх використанням пов'язані практично всі роботи, удостоєні Нобелівської премії з економіки (Р. Солоу, В. Леонтьєв, Л. Канторович та інші). Розвиток макроекономіки, мікроекономіки, прикладних дисциплін пов'язано з усе більш високим рівнем їх формалізації. Основу для цього заклав прогрес в області прикладної математики. У Росії на початку XX століття великий внесок у математичне моделювання економіки внесли В.К. Дмитрієв та Є.Є. Слуцький. У 1960-ті - 80-і роки економіко-математичний напрямок було пов'язано, в основному, зі спробами формально описати «систему оптимального функціонування соціалістичної економіки» (Н. П. Федоренко, С. С. Шаталін). Будувалися багаторівневі системи моделей народно - господарського планування, оптимізаційні моделі областей і підприємств.
Математична модель економічного об'єкту - це його гомоморфну ​​відображення у вигляді сукупності рівнянь, нерівностей, логічних відносин, графіків. Іншими словами, модель - це умовний образ об'єкта, побудований для спрощення його дослідження. Передбачається, що вивчення моделі дає нові рішення в тій або іншій ситуації.
Можна виділити 3 етапи проведення математичного моделювання в економіці:
1. ставляться цілі і завдання дослідження, проводиться якісний опис об'єкта у вигляді економічної моделі.
2. формується математична модель досліджуваного об'єкта, здійснюється вибір методів дослідження. Далі досліджується модель з допомогою цих методів.
3. здійснюється обробка та аналіз отриманих результатів.
Математичні моделі, що використовуються в економіці, можна підрозділити на класи за рядом ознак, що відносяться до особливостей модельованого об'єкта, мети моделювання і використовуваного інструментарію: моделі макро-і мікроекономічні, теоретичні та прикладні, оптимізаційні та рівноважні, статичні і динамічні.
Ми будемо розглядати деякі оптимізаційні моделі. До оптимізаційним моделям відносять наступні: модель лінійного програмування, нелінійного, динамічного, мережеві моделі. Будемо розглядати моделі лінійного та нелінійного програмування.

2. Деякі поняття функцій кількох змінних
Багатьом економічним явищам притаманна багатофакторна залежність, тому при вивченні процесів в економіці вводять функції декількох змінних.
Змінна y називається функцією декількох змінних x 1, x 2, ..., x n, якщо існує відображення f: R n → R. Безліч усіх точок М, що беруть участь в цьому відображенні, називається областю визначення функції, де М (x 1, x 2, ..., x n).
Найбільш часто зустрічається функція двох змінних. В економіці для її вивчення широко застосовуються лінії рівня.
Лініями рівня функції двох змінних y = f (x 1, x 2) називається проекція перетину графіка функції y = f (x 1, x 2) з горизонтальною площиною на площину Ох 1 х 2, причому лінія перетину знаходиться від площини Ох 1 х 2 на висоті С. Рівняння лінії рівня має вигляд f (x 1, x 2) = С. Число С у цьому випадку називається рівнем.
Як і у випадку однієї змінної, функція y = f (x 1, x 2) має вузлові, що визначають структуру графіка, крапки. У першу чергу це точки екстремуму. Точки екстремуму функції двох змінних визначаються аналогічно точкам екстремуму функції однієї змінної
Сформулюємо необхідна умова екстремуму - багатовимірний аналог теореми Ферма: Нехай точка ( ) - Є точка екстремуму диференціюється y = f (x 1, x 2). Тоді приватні похідні ( ), ( ) В цій точці дорівнюють нулю.
Точки, в яких виконані необхідні умови екстремуму функції y = f (x 1, x 2), тобто приватні похідні дорівнюють нулю, називаються стаціонарними.
Рівність нулю приватних похідних висловлює лише необхідна умова, але недостатня умова екстремуму функції кількох змінних.
у
х 1
х 2
М ( )
На малюнку зображено сідлова точка М ( ). Приватні похідні   ( ), ( ) Дорівнюють нулю, але екстремуму в точці М ( ) Немає. Такі сідлові точки є двовимірними аналогами точок перегину функцій однієї змінної. Потрібно відділити їх від точок екстремуму. Іншими словами, потрібно знати достатня умова екстремуму.
Достатня умова екстремуму функції двох змінних. Нехай функція y = f (x 1, x 2):
a) визначена в деякому околі стаціонарної точки ( ), В якій ( ) = 0 і ( ) = 0;
b) має в цій точці безперервні приватні похідні другого поряке ( ) = А, ( ) = ( ) = В, ( ) = С.
Тоді, якщо = АС-У 2 > 0, то в точці ( ) Функція має екстремум, причому, якщо А> 0 мінімум, А <0 - максимум. У випадку = АС-У 2 <0, функція y = f (x 1, x 2) екстремуму не має. Якщо = АС-У 2 = 0, то питання про наявність екстремуму залишається відкритим. Потрібні інші методи визначення екстремуму. [11]
В економічних задачах частіше зустрічаються завдання на умовний екстремум. Перейдемо до розгляду таких завдань.

3. Завдання математичного програмування (ЗМП).
1) Загальна постановка задачі
У теорії екстремуму на незалежні змінні x 1, x 2, ..., х n   не накладаються ніякі додаткові умови, тобто не потрібно, щоб змінні задовольняли деяким додатковим обмеженням.
Розглянемо іншу задачу. Знайти максимум (мінімум) функції y = f (x 1, x 2, ..., х n), за умови, що незалежні змінні x 1, x 2, ..., х n задовольняють системі обмежень:
g 1 (x 1, x 2, ..., х n) ≤ b 1,
... ... ... ... ... ... ... ... ... ...
g m (x 1, x 2, ..., х n) ≤ b m,
g m +1 (x 1, x 2, ..., х n) ≥ b m +1,
... ... ... ... ... ... ... ... ... ...
g k (x 1, x 2, ..., х n) ≥ b k,                                                                                                                                           (3.1)
g k +1 (x 1, x 2, ..., х n) = B k +1,
... ... ... ... ... ... ... ... ... ...
       g p (x 1, x 2, ..., х n) = B p,
x 1, x 2, ..., х n ≥ 0.
Функцію y = f (x 1, x 2, ..., х n) прийнято називати цільовий, тому що її максимізація (мінімізація) часто є вираз якоїсь мети, систему обмежень (3.1) - спеціальними обмеженнями ЗМП, нерівності x 1 ≥ 0, x ≥ 0 2, ..., х n ≥ 0 - загальними обмеженнями ЗМП. Безліч всіх допустимих рішень ЗМП j ≥ 0, j = ) Називається допустимим безліччю цього завдання.
Точка ( ) Називається оптимальним рішенням для функції двох змінних, якщо, по-перше, вона є допустиме рішення цієї ЗМП, а по-друге, на цій точці цільова функція досягає максимуму (мінімуму) серед усіх точок, які відповідають обмеженням (3.1), причому
f ( ) ≥ f (x 1, x 2) (у разі виконання завдання на відшукання максимуму),
f ( ) ≤ f (x 1, x 2) (у разі виконання завдання на відшукання мінімуму).
Якщо в ЗМП всі функції f (x 1, x 2, ..., х n), g i (x 1, x 2, ..., х n) лінійні, то маємо задачу лінійного програмування (ЗЛП), якщо хоча б одна з функцій нелінійна, маємо задачу нелінійного програмування (ЗЛП). Розглянемо ЗЛП.
2) ЗЛП і способи її вирішення.
ЗЛП має вигляд F = c 1 x 1 + c 2 x 2 + ... + c n x n + c 0 → min (max). При цьому змінні повинні задовольняти обмеженням:
а 11 х 1 + а 12 х 2 + ... + а 1 n х n ≤ b 1
... ... ... ... ... ... ... ... ... ...
а m 1 х 1 + а m 2 х 2 + ... + a mn x n ≤ b m
а m +11 х 1 + а m +12 х 2 + ... + а m +1 n х n ≥ b m +1
... ... ... ... ... ... ... ... ... ...
а k 1 х 1 + а k 2 х 2 + ... + а kn х n ≥ b k                                                                                                                         (3.2)
а k 1 +1 х 1 + а k +12 х 2 + ... + а k +1 n х n = b k +1
... ... ... ... ... ... ... ... ... ....
а p 1 х 1 + а p 2 х 2 + ... + а pn х n = b p
x 1, x 2, ..., х n ≥ 0.
ЗЛП може бути записана в різних формах:
Загальний вигляд: знайти мінімум (максимум) цільової функції F при обмеженнях (3.2) і умови невід'ємності змінних.
Стандартний вигляд: знайти мінімум (максимум) цільової функції F і обмеженнях, заданих у вигляді нерівностей і додані умови про невід'ємності змінних.
Канонічний вигляд: вид, в якому потрібно знайти мінімум (максимум) цільової функції F, де всі обмеження задані у вигляді рівностей і є умова невід'ємності змінних.
Стандартну завдання можна привести до канонічного виду, шляхом введення додаткових невід'ємних змінних. Тобто звести до системи m лінійних рівнянь з n змінними.
Будь-які m змінних системи m лінійних рівнянь з n змінними (m <n) називаються основними (або базисними), якщо визначник матриці коефіцієнтів при них відмінний від нуля. Тоді інші mn змінних називаються неосновними або (вільними).
Базисним рішенням системи m лінійних рівнянь з n змінними називають рішення, в якому всі mn неосновних змінних дорівнюють нулю.
Для обгрунтування властивостей ЗЛП і методів її вирішення, розглянемо 2 види запису канонічної задачі.
1 вид - матрична форма запису: С = (c 1, c 2 ... c n, c 0).
Х = А = В = (3.3)
F = CX → min (Max)
AX = B, X ≥ 0
2 вид - векторна форма запису:
F = CX → min (Max)
р 1 x 1 + р 2 x 2 + ... + р n x n = р. Х ≥ 0.
р 1 = р 2 = ... Р n = .
Для того щоб розглянути теоретичні основи методу лінійного програмування, визначимо поняття опуклого безлічі точок, давши йому визначення в аналітичній формі:
Безліч точок є опуклим, якщо воно разом з будь-якими своїми двома точками містить їх довільну лінійну комбінацію. Точка Х є опуклою лінійною комбінацією точок Х 1, Х 2, ... Х n, якщо виконуються умови Х = α 1 x 1 + α 2 x 2 + ... + α n x n, α j ≥ 0, (j = 1, ..., n), .
Теорема 1. Опуклий лінійний багатогранник є опуклою лінійною комбінацією своїх кутових точок. (Приймемо без доведення).
Теорема 2. Безліч всіх допустимих рішень системи обмежень ЗЛП є опуклим.
□ Нехай Х 1 = (x , X , ..., Х ) Та Х 2 = (x , X , ..., Х ) - Два допустимих рішення задачі (3.3), заданої в матричній формі. Тоді АХ 1 = В і АХ 2 = В. розглянемо опуклу лінійну комбінацію рішень Х 1 і Х 2, тобто Х = α 1 Х 1 + α 2 Х 2 при α 1 ≥ 0, α 2 ≥ 0 і α 1 + α 2 = 1. Покажемо, що вона також є допустимим розв'язком системи АХ = В. У самому справі, АХ = А (α 1 Х 1 + α 2 Х 2) = α 1 АХ 1 + (1 - α 1) АХ 2 = α 1 У + (1 - α 1) В = В, тобто . рішення задовольняє системі обмежень. Але тому що Х 1 ≥ 0, Х 2 ≥ 0, α 1 ≥ 0, α 2 ≥ 0, то і Х ≥ 0, тобто рішення Х задовольняє умові (3.3). ■
Отже, доведено, що множина всіх допустимих рішень ЗЛП є опуклим, яке будемо називати багатогранником рішень.
Відповідь на питання, в якій точці багатогранника рішень можливе оптимальне рішення ЗЛП, дає наступна теорема.
Теорема 3. Якщо ЗЛП має оптимальне рішення, то лінійна функція F приймає максимальне (мінімальне) значення в одній із кутових точок багатогранника рішень. Якщо лінійна функція приймає максимальне значення більш ніж в одній кутовій точці, то вона приймає його в довільній точці, що є опуклою лінійною комбінацією цих точок.
Х 1
Х 2
х 1
х 2
х 3
х 4
x p
x j
□ Будемо вважати, що багатогранник рішень є обмеженим. Позначимо його кутові точки через Х 1, Х 2, ..., Х n , А   оптимальне рішення через Х *. Тоді F (Х *) ≥ F (X), для всіх точок багатогранника рішень. Якщо Х * кутова, то перша частина теореми доведено. Припустимо, що Х * не є кутовий точкою, тоді Х *, на підставі теореми 1, можна представити як опуклу лінійну комбінацію кутових точок багатогранника рішень, тобто Х * = α 1 x 1 + α 2 x 2 + ... + α р x р, α j ≥ 0, (j = 1, ..., n), . Оскільки
F (Х *) = F (α 1 x 1 + α 2 x 2 + ... + α р x р) = α 1 F (x 1) + α 2 F (x 2) + ... + α р F (x р ). (3.4)
У цьому виразі серед значень F (X j) (j = 1,2, ..., p) виберемо максимальне. Позначимо його через М, тобто М = max F (X j). Тоді
α 1 F (x 1) + α 2 F (x 2) + ... + α р F (x р) ≤ α 1 М + α 2 М + ... + α р М = М (α 1 + α 2 + ... + α р) = М.
Значить F (Х *) ≤ М. Нехай М = F (X k), тобто відповідає кутовій точці X k (1 ≤ до ≤ р).
Тоді F (Х *) ≤ F (X k). Але за припущенням Х * - оптимальне рішення, тому F (Х *) ≥ F (X k) = М, отже, F (Х *) = М = F (X k), де X k - кутова точка. Отже, існує кутова точка X k, в якій лінійна функція приймає максимальне значення.
Для доказу другої частини теореми допустимо, що F (Х) приймає максимальне значення більш ніж в одній кутовій точці, наприклад в точках Х 1, Х 2, ... Х q, де 1 ≤ q ≤ р; тоді F (Х 1) = F (Х 2) = ... = F (Х n) = M.
Нехай Х опукла лінійна комбінація цих кутових точок, тобто Х = α 1 Х 1 + α 2 Х 2 + ... + α q Х q, α j ≥ 0, (j = 1, ..., q), . У цьому випадку, враховуючи, що функція F (Х) - лінійна, отримаємо F (Х) = F (α 1 Х 1 + α 2 Х 2 + ... + α q Х q) = α 1 F (Х 1) + + α 2 F (Х 2) + ... + α q F (Х q) = α 1 M + α 2 M + ... + α q M = M = M, тобто лінійна функція F приймає максимальне значення у довільній точці Х, яка є опуклою лінійною комбінацією кутових точок Х 1, Х 2, ... Х q
Зауваження. Вимога обмеженості багатогранника рішень в теоремі є істотним, тому що у разі необмеженої багатогранної області не кожну точку можна уявити опуклої лінійної комбінацією її кутових точок.
Доведена теорема є фундаментальною, тому що вона вказує принциповий шлях рішення ЗЛП.
Розглянемо геометричний метод розв'язання ЗЛП у випадку функції двох змінних.
Було доведено, що оптимальне рішення ЗЛП знаходиться, принаймні, в одній з кутових точок багатогранника рішень.
Розглянемо завдання в стандартній формі з двома змінними.
F = c 1 x 1 + c 2 x 2 + з 0 → min (max),
При обмеженнях а 11 х 1 + а 12 х 2 ≤ b 1,
а 21 х 1 + а 22 х 2 ≤ b 2,
... ... ... ... ... ...
                                      a n 1 х 1 + а n 2 х 2 ≤ b n ,
за умови, що x 1 ≥ 0, x 2 ≥ 0.
Нехай геометричним зображенням системи обмежень є багатокутник ABCDE. Необхідно серед точок цього багатокутника знайти таку точку, в якій лінійна функція F = c 1 x 1 + c 2 x 2 + з 0 приймає максимальне (або мінімальне) значення. Розглянемо лінії рівня функції F або
х 1
х 2
0
А
B
C
D
E
c 1 x 1 + c 2 x 2 = З (3.5).
Це рівняння прямої. Лінії рівня функції F паралельні, тому що їх кутові коефіцієнти визначаються тільки співвідношенням між коефіцієнтами c 1 і c 2 і, отже, рівні. Т.ч., лінії рівня функції F - це своєрідні «паралелі», розташовані зазвичай під кутом до осей координат.
Важлива властивість ліній рівня лінійної функції полягає в тому, що при паралельному зсуві лінії в одну сторону рівень тільки зростає, а при зсуві в іншу сторону - тільки убуває. При фіксованому З розглянемо лінійну функцію. Чим більше значення С, тим більше значення лінійної функції. Визначивши напрям зростання лінійної функції, знайдемо точку, що належить багатокутнику, в якій функція приймає максимальне або мінімальне значення.
Геометричним зображенням системи обмежень може служити і багатокутна область. Розглянемо таку задачу.
1.В добовий раціон включають два продукти харчування П 1 і П 2, причому продукту П 1 повинне увійти в денний раціон не більше 200 од. Вартість поживних речовин в 1 од. продукту, мінімальні норми споживання вказані в таблиці. Визначити оптимальний раціон харчування, вартість якого буде найменшою.
Живильні
речовини
Мінімальна норма
споживання
Вміст поживних
речовин в 1 од. продукту.
П 1
П 1
А
У
120
160
0,2
0,4
0,2
0,2
Рішення.
Позначимо х 1 - кількість продукту харчування П 1,
х 2 - кількість продукту харчування П 2.
F = 2 х 1 +4 х 2 → min. (Сумарна вартість) При обмеженнях
х 1 ≤ 200,
0,2 х 1 +0,2 х 2 ≥ 120,
0,4 х 1 +0,2 х 2 ≥ 160.
П 1
П 2
200
400
600
200
0
А
Графічним рішенням системи обмежень є безліч точок площини, зване областю допустимих рішень (ОДР). Лінії рівня 1 +4 х 2 = 0 х 2 =- х 1.
Отримуємо, що мінімальне значення, при заданих обмеженнях на змінні, досягається в точці А (200; 400). F (A) = 2000.
Відповідь: найменша вартість 2000 буде при раціоні 200 од. продукту П 1 і 400 од. продукту П 2.
Не завжди буває єдине оптимальне рішення. Розглянемо іншу задачу.
2. F = 4 x 1 +4 x 2 → max. При обмеженнях
2 x 1 + x 2 ≥ 7,
   x 1 -2 x 2 ≥ -5,
   x 1 + x 2 ≤ 14,
2 x 1 - x 2 ≤ 18.
Вирішивши, систему обмежень знайдемо ОДР. Лінія рівня буде мати вигляд 4 x 1 +4 x 2 = 0 x 2 =- x 1.
Х 1
Х 2
4
9
2
I
II
III
IV
У цьому завданню лінія рівня з максимальним рівнем збігається з граничною лінією багатокутника рішень. Знайдемо точку перетину лінії II з лінією III:

х 1 = .
Знайдемо точку перетину лінії III з лінією IV: 14 - х 1 = 2 х 1 -18. Звідси х 1 = . Отже, x 1 = c, x 2 = 14 - c, c [ ; ]. Нехай х 1 = 9 [ ; ], Х 2 = 5.
F = 4.9 +4 · 5 = 56.
Відповідь: F max = 56 при безлічі оптимальних рішень х 1 = c, x 2 = 14 - c, де c [ ; ].
Розглянутий геометричний метод розв'язання ЗЛП має ряд переваг. Він простий, наочний, дозволяє швидко та легко отримати відповідь.
Однак є й недоліки. Виникають «технічні» похибки, які неминуче виникають при наближеному побудові графіків. Другий недолік геометричного методу полягає в тому, що багато величини, що мають чіткий економічний зміст (наприклад, такі, як залишки ресурсів виробництва), не виявляються при геометричному вирішенні завдань. Його можна застосовувати тільки в тому випадку, коли число змінних в стандартній задачі дорівнює двом. Тому необхідні аналітичні методи, що дозволяють вирішувати ЗЛП з будь-яким числом змінних і виявити економічний сенс, що входять до них величин.
Одним з таких методів є симплексний метод.
У даному пункті була розглянута теорема, з якої випливає, що якщо ЗЛП має оптимальне рішення, то воно відповідає хоча б одній кутовій точці багатогранника рішень. Тому рішення ЗЛП може бути наступним: перебрати кінцеве число всіх кутових точок багатогранника рішень і вибрати серед них ту, на якій функція мети приймає оптимальне рішення. Проте, практичне здійснення такого перебору пов'язано з труднощами, бо число рішень може бути надзвичайно велике.
Х 1
Х 2
G
F
D
C
B
A
H
0
Нехай ОДР зображується багатокутником ABCDEGH. Припустимо,
що його кутова точка відповідає вихідному допустимому рішенню. При безладному наборі довелося б перебирати всі 7 кутових точок багатогранника. Однак, з креслення видно, що після вершини А вигідно перейти до сусідньої вершині У, а потім - до оптимальної точці С. Замість семи перебрали 3 вершини, послідовно покращуючи лінійну функцію.
Ідея послідовного поліпшення рішення лягла в основу універсального методу розв'язання ЗЛП - симплексного методу. Для використання симплексного методу ЗЛП повинна бути приведена до канонічного вигляду. Для реалізації симплексного методу необхідно освоїти 3 основних елементи:
· Спосіб визначення будь - якого початкового допустимого рішення
· Правило переходу до кращому вирішенню
· Критерій перевірки оптимальності знайденого рішення.
Алгоритм конкретної реалізації цих елементів розглянемо на прикладі.
Практичні розрахунки при вирішенні реальних завдань симплексним методом виконуються в даний час за допомогою комп'ютера, однак, якщо розрахунки виконуються без ЕОМ, то зручно використовувати симплексних таблиці.
Алгоритм складання симплексних таблиць:
1. Система обмежень приводиться до канонічного виду.
Для знаходження початкового базисного рішення змінні розбиваються на основні і неосновні. Оскільки визначник, складений з коефіцієнтів при додаткових змінних відмінний від нуля, то ці змінні можна взяти в якості основних. При виборі основних змінних не обов'язково складати визначник, достатньо скористатися таким правилом: в якості основних змінних слід вибрати такі, кожна з яких входить тільки в одне з рівнянь системи обмежень, при цьому немає таких рівнянь системи, в які не входить ні одне з цих змінних .
2. Складають таблицю, де в останньому рядку зазначаються коефіцієнти функції з протилежним знаком. У лівому стовпчику таблиці записують основні змінні, в першому рядку - всі змінні, в останньому стовпці вільні члени системи.
3. Перевіряють виконання критерію оптимальності - наявність в останньому рядку негативних коефіцієнтів. Якщо таких немає, то рішення оптимально, досягнуто, наприклад, максимум функції (у правому нижньому куті таблиці), основні змінні при цьому беруть значення b i, а неосновні змінні дорівнюють нулю, тобто виходить оптимальне базисне рішення.
4. Якщо критерій оптимальності не виконаний, то найбільший за модулем від'ємний коефіцієнт в останньому рядку визначає дозволяє стовпець S. Складають оціночні обмеження за такими правилами:
· ∞, якщо b i і а is мають різні знаки;
· ∞, якщо b i = 0 і а is <0;
· ∞, якщо а is = 0;
· 0, якщо b i = 0 і а is> 0;
· , Якщо b i і а is мають однакові знаки.
Визначають min . Якщо кінцевого мінімуму немає, то завдання не має кінцевого оптимуму. Далі вибирають рядок з номером q, на якій він досягається (будь-яку, якщо їх декілька), і називають її роздільної рядком. На перетині роздільної рядки і що дозволяє стовпця знаходиться дозволяє елемент а qs.
5. Переходимо до наступної таблиці за правилами:
а) у лівому стовпці записують новий базис: замість основною змінною х q   - Змінну х s, а геометрично відбудеться перехід до сусідньої вершині багатокутника, де значення лінійної функції «краще». Значення лінійної функції збільшиться, тому що змінна, що входить у вираз функції, стане основною, тобто буде приймати не нульовий, а позитивне значення;
b) новий рядок з номером q отримують зі старої поділом на дозволяє елемент а qs;
c) всі інші елементи обчислюють за правилом багатокутника:
;
Далі переходимо до пункту 3 алгоритму.
Зауваження: при знаходженні мінімуму функції Z, вважаємо, що F =- Z і враховуємо, що Z min =- F max.
Вирішимо задачу симплексним методом.
Для виробництва трьох виробів А, В і С використовуються три види ресурсів. Кожен з них використовується в обсязі, що не перевищує 180, 210 і 236 кг. Норми витрат кожного з видів ресурсів на один виріб і ціна одиниці виробів наведені в таблиці.
Вид ресурсу
Норми витрат ресурсів на 1 виріб, кг
А
У
З
1
2
3
4
3
1
2
1
2
1
3
5
Ціна виробу, у.о.
10
14
12
Визначити план випуску виробів, що забезпечує отримання оптимального доходу.
Рішення. Х 1 - кількість виробів, що випускаються А
х 2 - кількість виробів, що випускаються У
х 3 - кількість виробів, що випускаються С.
Тоді цільова функція буде мати вигляд: F = 10 x один +14 x 2 +12 х 3 → max
при обмеженнях: 4 x 1 +2 x 2 + х 3 ≤ 180
3 x 1 + x 2 +3 х 3 ≤ 210
                                         x 1 +2 x 2 +5 х 3 ≤ 236
Наведемо систему до канонічного вигляду:
4 x 1 +2 x 2 + х 3 + х 4 = 180
3 x 1 + x 2 +3 х 3 + х 5 = 210
                                       x 1 +2 x 2 +5 х 3 + х 6 = 236.
Складаємо таблицю
х 1
х 2
х 3
х 4
х 5
х 6
Вільний член
х 4
х 5
х 6
4
3
1
2
1
2
1
3
5
1
0
0
0
1
0
0
0
1
180
210
236
F '
-10
-14
-12
0
0
0
0
Визначимо провідний елемент: min . Далі виконуємо дії, слідуючи алгоритму.
х 1
х 2
х 3
х 4
х 5
х 6
Вільний член
х 2
х 5
х 6
2
1
-3
1
0
0
1 / 2
5 / 2
4
1 / 2
-1 / 2
-1
0
1
0
0
0
1
90
120
56
F '
18
0
-5
7
0
0
1260
min
                    
х 1
х 2
х 3
х 4
х 5
х 6
Вільний член
х 2
х 5
х 3
19 / 8
23 / 8
-3 / 4
1
0
0
0
0
1
5 / 8
1 / 8
-1 / 4
0
1
0
-1 / 8
-5 / 8
1 / 4
83
85
14
F '
54 / 4
0
0
23 / 4
0
5 / 4
1330
Відповідь: Щоб отримати оптимальний дохід, потрібно випускати 83 од. виробу В, 14 од. вироби С, а виріб А не випускати. Оптимальний дохід складе 1330 у.о. За рішенням завдання бачимо, що у підприємства залишаються вільними 85 кг. другого виду ресурсів, 1 і 3 вид повністю витрачаються [5]
3) Двоїста задача.
Кожній задачі лінійного програмування відповідає інша задача, звана двоїстої або сполученої по відношенню до початкової. Теорія двоїстості корисна для проведення якісних досліджень ЗЛП. У розділі I пункті 2) розглянута завдання про використання ресурсів. Припустимо, що деяка організація вирішила закупити ресурси і необхідно встановити оптимальні ціни на ці ресурси y 1, y 2, y 3. Очевидно, що
купує організація зацікавлена ​​в тому, щоб витрати на всі ресурси Z в кількостях 180, 210, 236 за цінами відповідно до y 1, y 2, y 3 були мінімальними, тобто Z = 180 y +1 +210 y два +236 y 3 → min. З іншого боку, підприємство, що продає ресурси, зацікавлене в тому, щоб отримана виручка була не менше тієї суми, яку підприємство може отримати при переробці ресурсів у готову продукцію. На виготовлення одиниці продукції А витрачається 4кг. ресурсу 1, 3кг. ресурсу 2, 1кг. ресурсу 3 за ціною відповідно y 1, y 2, y 3. Тому, для задоволення вимог продавця витрати на ресурси, що споживаються при виготовленні одиниці продукції, повинні бути не менше її ціни 10у.е., Тобто 4 y 1 +3 y 2 + y 3 ≥ 10.
Аналогічно можна скласти обмеження у вигляді нерівностей по кожному виду продукції. Економіко-математична модель вихідної задачі і отриманої двоїстої завдання наведені в таблиці.
Завдання I (вихідна)
Завдання II (двоїста)
F = 10 x +1 +14 x 2 +12 x 3 → max
При обмеженнях:
1 +2 х 2 + х 3 ≤ 180
1 + х 2 +3 х 3 ≤ 210
х 1 +2 х 2 +5 х 3 ≤ 236
і умова невід'ємності змінних x 1 ≥ 0, x 20, х 3 ≥ 0.
Для виробництва трьох виробів А, В, С використовуються три види сировини. кожен з них використовується в обсязі, що не перевищує 180, 210 і 236кг. Визначити план випуску виробів, що забезпечує отримання оптимального доходу за умови, що споживання ресурсів за кожним видом продукції не перевершить наявних запасів.
Z = 180 y +1 +210 y 2 +236 y 3 → min
При обмеженнях:
4 y 1 +3 y 2 + y 3 ≥ 10
   2 y 1 + y 2 +2 y 3 ≥ 14
     y 1 +3 y 2 +5 y 3 ≥ 12
і умова невід'ємності змінних y 1 ≥ 0, у 20, у 3 ≥ 0.
Знайти такий набір цін ресурсів, при якому загальні витрати на ресурси будуть мінімальними за умови, що витрати на ресурси при виробництві кожного виду продукції будуть не менш прибутку від реалізації цієї продукції.
Обидва завдання, представлені в таблиці мають наступні властивості:
1. У одному завданню шукають максимум лінійної функції, в іншій мінімум.
2. Коефіцієнти при змінних в лінійній функції однієї задачі є вільними членами системи обмежень в іншій.
3. Кожна із завдань задана в стандартній формі, причому в задачі максимізації - всі нерівності виду «≤», а в задачі мінімізації - всі нерівності виду «≥».
4. Матриці коефіцієнтів при змінних в системах обмежень обох завдань є транспонований один до одного.
Для задачі I А = , Для задачі II А =
5. Число нерівностей в системі обмежень однієї задачі співпадає з числом змінних в іншої задачі.
6. Умови невід'ємності змінних є в обох завданнях.
Дві завдання I і II лінійного програмування, що володіють вказаними властивостями, називаються симетричними взаімодвойственнимі завданнями.
Виходячи з визначення, можна запропонувати наступний алгоритм складання двоїстої задачі.
1. Приводять всі нерівності системи обмежень вихідної задачі до одного глузду: якщо у вихідній завдань шукають максимум лінійної функції, то всі нерівності системи обмежень призводять до виду «≤», а якщо мінімум - до виду «≥».
2. Складають розширену матрицю системи А 1, в яку включають матрицю коефіцієнтів при змінних, стовпець вільних членів системи обмежень і рядок коефіцієнтів при змінних в лінійній функції.
3. Знаходять матрицю А , Транспоновану до матриці А 1.
4. Формулюють двоїсту задачу на підставі отриманої матриці А і умови невід'ємності змінних.
Зв'язок між оптимальними рішеннями двоїстих задач встановлюється за допомогою теорем подвійності. Спочатку розглянемо допоміжне твердження.
Основне нерівність теорії двоїстості. Нехай є пара двоїстих задач I і II. Покажемо, що для будь-яких допустимих рішень Х = (x 1, x 2, ..., х n) і У = (y 1, y 2, ..., y m) вихідної і двоїстої задачі справедливо нерівність F (X) ≤ Z (Y ) або (3.6)
□ Візьмемо нерівності системи обмежень вихідної задачі b i і помножимо відповідно на змінні y 1, y 2, ..., y m і, склавши праві і ліві частини отриманих нерівностей, маємо
. (3.7)
Аналогічно множимо систему обмежень двоїстої задачі на змінні x 1, x 2, ..., х n, отримаємо
(3.8)
Оскільки ліві частини нерівностей (3.7) і (3.8) представляють одне і теж вираз у j, то в силу транзитивності нерівностей отримаємо доказуване нерівність (3.6). ■
Тепер доведемо ознака оптимальності рішень.
Достатній ознака оптимальності.
Якщо X * = (x , X , ..., X ) І У * = (у , У , ..., У ) - Допустимі рішення взаємно двоїстих задач, для яких виконується рівність
F (X *) = Z (Y *) (3.9)
то Х * оптимальне рішення вихідної задачі I, а У * - двоїстої задачі II.
□ Нехай Х 1 будь допустиме рішення вихідної задачі I. Тоді на підставі основного нерівності (3.6) отримаємо F (X 1) ≤ Z (Y *). Однак Х 1 - довільне рішення задачі I. Аналогічно доводиться, що рішення У * оптимально для задачі II. ■
Чи завжди для кожної пари двоїстих задач є одночасно оптимальні рішення; чи можливі ситуації, коли одна з двоїстих завдань має рішення, а інша ні?
Відповідь на ці запитання дає наступна теорема.
Перша (основна) теорема подвійності. Якщо одна з взаємно двоїстих завдань має оптимальне рішення, то його має й інша, причому оптимальні значення їх лінійних функцій дорівнюють:
F max = Z min або F (X *) = Z (Y *) (3.10)
Якщо лінійна функція одним із завдань не обмежена, то система обмежень іншої задачі суперечлива.
З першої частини твердження теореми випливає, що рівність (3.9) є не тільки достатньою, а й необхідною ознакою оптимальності взаємно двоїстих задач.
□ Доведемо твердження другої частини методом від протилежного. Припустимо, що у вихідній задачі лінійна функція не обмежена, тобто F max = ∞, а умови двоїстої завдання не є суперечливими, тобто існує хоча б одне допустиме рішення У = (y 1, y 2, ..., y m). Тоді в силу основного нерівність теорії двоїстості (3.6) F (X) ≤ Z (Y), що суперечить умові необмеженість F (X). Отже, при F max = ∞ у вихідній задачі, допустимих рішень у двоїстої завданню бути не може. ■
Економічний зміст першої теореми двоїстості полягає в наступному: план виробництва X * = (x , X , ..., X ) І набір цін ресурсів У * = (у , У , ..., У ) Виявляються оптимальними тоді і тільки тоді, коли прибуток від продукції, знайдена при цінах з 1, с 2, ..., с n, «зовнішніх» (відомих заздалегідь), дорівнює витратам на ресурси з «внутрішнім» (визначеним тільки з рішення задачі) цінами y 1, y 2, ..., y m. Для всіх же інших планів Х і У обох завдань у відповідності з основним нерівністю (3.6) теорії подвійності прибуток (виручка) від продукції завжди менше (або дорівнює) витрат на ресурси.
Економічний зміст першої теореми двоїстості можна інтерпретувати і так: підприємству байдуже, виробляти чи продукцію з оптимального плану X * = (x , X , ..., X ) І отримувати максимальний прибуток F max або продавати ресурси за оптимальними цінами У * = (у , У , ..., У ) І відшкодувати від продажу рівні їй мінімальні витрати на ресурси Z min.
Зв'язок між двома взаємно подвійними завданнями проявляється не тільки в рівності оптимальних значень їх лінійних функцій.
Нехай дано дві взаємно суперечливі завдання I і II. Якщо кожну з них вирішувати симплексним методом, то необхідно привести їх до канонічного вигляду, для чого в систему обмежень задачі I слід ввести m невід'ємних змінних x n +1, x n +2, ..., x n + m, а в систему обмежень задачі II - n невід'ємних змінних y m +1, y m +2, ..., y m + n. Системи обмежень двоїстих задач приймуть вигляд:
+ X n + i = b i, i = 1, ..., m (3.11) -Y m + j = c j, j = 1, ..., n (3.12).
встановимо відповідність між первинними змінними однієї з двоїстих задач і додатковими змінними іншої задачі.
Змінні вихідної завдання I
Початкові
Додаткові
x 1 x 2 ... x j             ... Х n
↕ ↕ ↕ ↕
y m +1      y m +2 ... y m + j ... y m + n
x n +1          x n +2 ... x n + I ...   x n + m
↕ ↕ ↕                         
y 1                     y 2          ... Y j y m
Додаткові
Початкові
Змінні вихідної задачі II
Теорема. Позитивним (ненульовим) компонентів оптимального вирішення однієї з взаємно двоїстих задач відповідають нульові компоненти оптимального вирішення іншої задачі, тобто для будь-яких i = 1,2, ..., m і j = 1,2, ..., n: якщо > 0, то = 0; якщо > 0, то = 0, і аналогічно, якщо > 0, то = 0; якщо > 0, то = 0.
□ Висловимо додаткові змінні із системи обмежень (3.11) вихідної задачі I і (3.12) двоїстої задачі, представлених у канонічному вигляді:
x n + i = b i - , I = 1,2, ..., m (3.13)
y m + j = -C j, j = 1, ..., n. (3.14)
Множачи кожне рівність системи (4.9) на відповідні змінні у j ≥ 0 і складаючи отримані рівності, знайдемо
x n + i y i = b i y i - y i (3.15)
Аналогічно, множачи кожне нерівність системи (4.10) на відповідні змінні x j ≥ 0 і складаючи отримані рівності, знайдемо
y m + j = y i - c j .                                           (3.16)
Рівності (4.11) і (4.12) будуть справедливі для будь-яких допустимих значень змінних, в тому числі і для оптимальних значень , , , . У силу першого теореми подвійності (3.10) F (X *) = Z (Y *) або = , Тому із запису правих частин рівності (3.15) і (3.16) випливає, що вони повинні відрізнятися тільки знаком. З іншого боку, з неотрицательности виразів x n + i y i і y m + j, що входять у вирази (3.15) і (3.16), випливає, що праві частини цих рівностей повинні бути ненегативні.
Ці умови можуть виконуватися одночасно лише при рівності цих правих частин для оптимального значення змінних нулю:
= 0,
= 0. (3.17)
У силу умови невід'ємності змінних кожне з доданків в рівності (4.13) має дорівнювати нулю:
= 0, i = 1,2, ..., m
= 0, j = 1,2, ..., n
Звідки і випливає висновок теореми. ■
З доведеної теореми випливає, що введене раніше відповідність між змінними двоїстих задач являє відповідність між основними (як правило не рівними нулю) змінними однієї з двоїстих задач і неосновними (рівними нулю) змінними іншого завдання, коли вони утворюють допустимі базисні рішення.
Розглянута теорема є наслідком наступної теореми.
Друга теорема подвійності. Компоненти оптимального рішення двоїстої задачі рівні абсолютним значенням коефіцієнтів при відповідних змінних лінійної функції вихідної задачі, вираженої через неосновні змінні її оптимального рішення.
Метод, при якому спочатку симплексним методом вирішується двоїста задача, а потім оптимум і оптимальне рішення вихідної задачі знаходяться за допомогою теорем подвійності, називається двоїстим симплексним методом. Цей метод буває вигідно застосовувати, коли перше базисне рішення вихідної задачі неприпустиме або, наприклад, коли число її обмежень m більше числа змінних n.
За допомогою теорем подвійності знайдемо рішення задачі II. Отримуємо наступний набір цін ресурсів ( ), При якому мінімальні витрати складуть 1330. [5]
4) Завдання нелінійного програмування. (ЗНП)
Розглянемо ЗНП і способи її вирішення. Математична модель ЗНП в загальному вигляді формулюється наступним чином:
f = (x 1, x 2, ..., х n) → min (max). При цьому змінні повинні задовольняти обмеженням:
g 1 (x 1, x 2, ..., х n) ≤ b 1,
... ... ... ... ... ... ... ... ... ...
g m (x 1, x 2, ..., х n) ≤ b m,
g m +1 (x 1, x 2, ..., х n) ≥ b m +1,
... ... ... ... ... ... ... ... ... ...
g k (x 1, x 2, ..., х n) ≥ b k,
g k +1 (x 1, x 2, ..., х n) = b k +1,
... ... ... ... ... ... ... ... ...
g p (x 1, x 2, ..., х n) = b p.
x 1, x 2, ..., х n ≥ 0, де хоча б одна з функцій f, g i нелінійна.
Для ЗЛП немає єдиного методу рішення. Залежно від виду цільової функції і системи обмежень розроблені спеціальні методи рішення, до яких належать метод множників Лагранжа, градієнтні методи, наближені методи рішення, графічний метод.
Розглянемо основні ідеї графічного методу.
Максимум і мінімум досягається в точках дотику лінії рівня з областю допустимих рішень (ОДР), яка задається системою обмежень. Наприклад, якщо лінії рівня - прямі, то точки дотику можна визначити, використовуючи геометричний зміст похідної.
Розглянемо на прикладах рішення ЗНП.
1. Знайти екстремуми функції L (x 1, x 2) = x 1 +2 x 2 при обмеженнях
, .
А
5
0
х 1
х 2
5
Рішення. ОДР - це частина кола з радіусом 5, розташована в I чверті. Знайдемо лінії рівня функції L: x 1 +2 x 2 = C. Висловимо x 2 = . Лініями рівня будуть паралельні прямі з кутовим коефіцієнтом, рівним - . Мінімум функції досягається у точці (0; 0), L min = 0, тому градієнт (1,2) спрямований вгору праворуч. Максимум досягається в точці дотику кривої х 2 = і лінії рівня. Оскільки кутовий коефіцієнт дотичної до графіка функції дорівнює - , Знайдемо координати точки дотику, використовуючи геометричний зміст похідної.
= - ; ( ) = - ;
= - ; x 0 = ; X 2 = 2 .
Тоді L = +2 ∙ 2 = 5 .
Відповідь: Мінімум досягається в точці О (0; 0), глобальний максимум, що дорівнює 5 , У точці А ( , 2 ).
2. Знайти екстремуми функції L = (x 1 -6) 2 + (x 2 -2) 2 при обмеженнях

x 1 + x 2 ≤ 8
3 x 1 + x 2 ≤ 15
                     x 1 + x 2 ≥ 1
.
А
У
D
4
З
8
F
E
З = 36
О 1
Рішення. ОДР - багатокутник ABCDE. Лінії рівня представляють собою кола (x 1 -6) 2 + (x 2 -2) 2 = С з центром в точці О 1 (6, 2). Візьмемо, наприклад, С = 36, бачимо, що максимум досягається в точці А (0; 4), яка лежить на колі найбільшого радіусу, що перетинає ОДР. L (A) = (0-6) 2 + (4-2) 2 = 40. Мінімум - у точці F, що знаходиться на перетині прямої 3 x 1 + x 2 = 15 і перпендикуляра до цієї прямої, проведеного з точки О 1. Оскільки кутовий коефіцієнт дорівнює -3, то кутовий коефіцієнт перпендикуляра дорівнює . З рівняння прямої, що проходить через цю точку О 1 з кутовим коефіцієнтом , Одержимо (x 2 -2) = (X 1 -6). Знайдемо координати точки Е
х 1-3х 2 = 0
3 x 1 + x 2 = 15.
Вирішивши систему, отримуємо Е (4.5; 1.5).
L (E) = (4.5-6) ​​2 + (1.5-2) 2 = 2. 5.
Відповідь: Принаймні, рівний 2.5 досягається в точці (4.5; 1.5), максимум, рівний 40, в точці (0; 4).
3. Знайти екстремуми функції L = (x 1 -1) 2 + (x 2 -3) 2
при обмеженнях , .
А
5
0
х 1
О 1
х 2
Рішення: ОДР є частина кола, з центром у початку координат, з радіусом 5, розташована в I чверті. Лінії рівня - це кола з центром в точці О 1 і радіуса С, тому що (x 1 -1) 2 + (x 2 -3) 2 = С. Точка О 1 - це вироджена лінія рівня, який відповідає мінімальному значенню С = 0. глобальний максимум досягається в точці А, що лежить на перетині ОДР з лінією рівня найбільшого радіуса. При цьому
L (A) = (5-1) 2 + (0-3) 2 = 25.
Відповідь: Принаймні, рівний 0, досягається в точці (1, 3),
Максимум, який дорівнює 25, - у точці А (5; 0).
4. Підприємець вирішив виділити на розширення своєї справи 150 тис.руб. відомо, що якщо на придбання нового обладнання затратити х тис. руб., а на зарплату новоприйнятих працівників у тис. руб., то приріст обсягу продукції складе Q = 0.001 x 0.6 · y 0.4. Як слід розподілити виділені грошові ресурси, щоб приріст обсягу продукції був максимальним.
Рішення: Цільова функція має вигляд 0.001 x 0.6 · y 0.4 → max при обмеженнях x + y ≤ 150,
.
ОДР - трикутник.
150
150
0
х
у
Лінії рівня матимуть вигляд 0.001 x 0.6 · y 0.4 = С. Висловивши звідси у, отримаємо у = . Оскільки максимум досягається в точці дотику лінії рівня з ОДР, то умова торкання має вигляд =- 1. Знайшовши похідну, отримуємо = -1. Висловивши х, отримаємо х = . У = = .
Відповідь: Фактори х і у слід розподілити щодо 2:3.
5. Підприємство випускає вироби А і Б, при виготовленні яких використовується сировина S 1 і S 2. Відомі запаси b i (i = 1,2) сировини, норми його витрати на одиницю виробу a ij (j = 1,2), оптові ціни p j на вироби та їх планова собівартість із . Як тільки обсяг продукції, що випускається перестає відповідати оптимальному розміру підприємства, подальше збільшення випуску х j веде до підвищення собівартості продукції b, в першому наближенні фактична собівартість із j описується функцією з j = з + З х j, де з j - деяка постійна. Всі числові дані наведені у таблиці
b 1
b 2
a 11
a 12
a 21
a 22
p 1
p 2
з
з
з
з
90
88
13
6
8
11
12
10
7
8
0.2
0.2
Знайти план випуску виробів, що забезпечує підприємству найвищу прибуток в умовах порушення балансу між обсягом і оптимальним розміром підприємства.
Рішення: З залишимо математичну модель задачі.
Нехай Z - прибуток, одержуваний підприємством після реалізації х 1 випущених виробів А і х 2 виробів Б.
Z = (12 - (7 + 0,2 х 1)) х 1 + (10 - (8 + 0,2 х 2)) х 2 → max,
при обмеженнях 13 х 1 + 6 х 2 ≤ 90,
8 х 1 + 11 х 288,

Перетворюючи цільову функцію, отримаємо:
Z = 5х 1 -0,2 х +2 Х 2 -0,2 х → max
ОДР - багатокутник ОАВD. Для побудови ліній рівня функції, наведемо функцію до наступного вигляду:
1 -12,5) 2 + (х 2 -5) 2 = 181,25-5 Z.
Лініями рівня будуть кола з центром в точці О 1 (12,5; 5) і радіуса . Окружність найбільшого радіуса буде проходити через точку М, що знаходиться на перетині прямий ВD і прямої O 1 М, перпендикулярної до BD. Знайдемо координати точки М.
13х 1 + 6х 2 = 90
х 2 -5 = 6 / 13 (х 1 -12,5). Вирішивши систему, одержимо, М (6; 2).
Z (М) = 30-7,2-2,8 +4 = 26.
Відповідь: Для отримання підприємством максимального прибутку, що становить 26 ден.ед., слід випустити 6 од. виробу А та 2 од. вироби Б.  
5) Завдання на умовний екстремум.
Якщо система обмежень (3.1) задана у вигляді рівностей, то це завдання на умовний екстремум. У випадку функції n незалежних змінних (x 1, x 2, ..., х n) завдання на умовний екстремум формулюється наступним чином:
L = f (x 1, x 2, ..., х n) → max (min)
за умов: g i (x 1, x 2, ..., х n) = 0, i = . (M <n).
У кінці XVIII століття Лагранж запропонував дотепний метод розв'язання задачі на умовний екстремум. Суть методу Лагранжа полягає в побудові функції L (x 1, x 2, ..., х n) = f (x 1, x 2, ..., х n) + g i (x 1, x 2, ..., х n), де λ i невідомі постійні, і знаходження екстремуму функції L.
Верна наступна теорема: якщо точка ( ) Є точкою умовного екстремуму функції f (x 1, x 2, ..., х n) за умови g (x 1, x 2, ..., х n) = 0, то існує значення λ i такі, що точка ( ) Є точкою екстремуму функції L ( ).
Розглянемо метод Лагранжа для функції двох змінних.
L (x 1, x 2, λ) = f (x 1, x 2) + λ g (x 1, x 2)
Таким чином, для знаходження умовного екстремуму функції f (x 1, x 2) за умови g (x 1, x 2) = 0 потрібно знайти рішення системи
                                     L = F (X 1, x 2) + λg (X 1, x 2) = 0, (3.18)
L = F (X 1, x 2) + λg (X 1, x2) = 0,
L = G (x 1, x 2) = 0. [4]
Є й достатні умови, при виконанні яких рішення (x 1, x 2, λ) системи (3.18) визначає точку, в якій функція f досягає екстремуму, для цього потрібно обчислити значення і скласти визначник
=- .
Якщо <0, то функція має в точці ( ) Умовний максимум, якщо > 0 - то умовний мінімум.
Вирішимо задачу методом множників Лагранжа.
Загальні витрати виробництва задані функцією Т = 0,5 х 2 +0,6 ху +0,4 у 2 + +700 Х +600 у +2000, де х і у відповідно кількість товарів А і В. Загальна кількість виробленої продукції має дорівнювати 500 одиниць. Скільки одиниць товару А і В потрібно виробляти, щоб витрати на їх виготовлення були мінімальними?
Рішення: складемо функцію Лагранжа.
L (x, y, λ) = 0,5 х 2 +0,6 ху +0,4 у 2 + +700 Х +600 у +2000 + λ (х + у-500). Прирівнюючи до нуля її частинні похідні, одержимо
х +0,6 у +700 + λ = 0,
0,6 х +0,8 у +600 + λ = 0,
х + у-500 = 0.
Вирішивши систему, знайдемо (0, 500, -1000).
Скористаємося достатньою умовою для визначення знайденого значення L (X 0, y 0) = 1, L (X 0, y 0) = 0.8, L (X 0, y 0) = 0.6. Функція g = х + у-500. G = 1, g = 1.
= - (0 · L · L + G · L · G + G · G · L - G · L · G -0 · L · L - G · G · L ) = 0,6> 0
Значить, у точці (0; 500) функція L має умовний мінімум.
Відповідь: Вигідно робити тільки 500 од. товару В, а товар А не виробляти.
Найбільш простим способом знаходження умовного екстремуму функції двох змінних є зведення задачі до відшукання екстремуму функції однієї змінної. Нехай рівняння g (x 1, x 2) = 0 вдалося вирішити відносно однієї із змінних, наприклад, висловити х 2 через х 1: х 2 = φ (х 1). Підставивши отриманий вираз у функцію, отримаємо y = f (x 1, x 2) = y = f (x 1, φ (х 1)), тобто функцію однієї змінної. Її екстремум і буде умовний екстремум функції y = f (x 1, x 2).
Проілюструємо цей метод на конкретному завданні.
Фірма реалізує автомобілі двома способами: через роздрібну та оптову торгівлю. При реалізації х 1 автомобілів в роздріб витрати на реалізацію складають (4 х 1 + х ) У. е., а при продажу х 2 автомобілів оптом - х у. е. Знайти оптимальний спосіб реалізації автомобілів, що мінімізують сумарні витрати, якщо загальне число, призначених для продажу автомобілів складає 200шт.
Рішення: Складемо функцію L (х 1, х 2) = 4 х 1 + х + Х і будемо знаходити її мінімум. Оскільки для продажу призначено 200 автомобілів, то x 1 + х 2 = 200. Дозволимо даної рівняння відносно змінної х 2: х 2 = 200-х 1. Підставимо отриманий вираз у функцію L, отримаємо L = 4 х 1 + х + (200 - х 1) 2 = 2х - 396 х 1 +40000, х 1 0.
Знайдемо екстремум даної функції.
min
х 1
f
-
+
99
L = 4 х 1 -396.
Прирівнявши її до нуля, отримаємо х 1 = 99.
Відповідь: оптимальний спосіб реалізації автомобілів - це 99 автомобілів в роздріб і 101 автомобіль оптом 2 = 200-99). Витрати складуть 20398 р.
В економічних задачах, в яких відшукується оптимум функції f = (x 1, x 2, ..., х n), де n 2, вважають, що знайдене єдине рішення, яке задовольняє необхідній умові екстремуму, є оптимальним.

4. Завдання споживчого вибору.
1) Функція корисності. Бюджетне обмеження. Формулювання завдання споживчого вибору.
Будемо вважати, що споживач має в своєму розпорядженні доходом Q, який він повністю витрачає на придбання благ (продуктів) Враховуючи структуру цін, дохід і власні переваги, споживач купує певну кількість благ, і математична модель такої його поведінки називається моделлю споживчого вибору.
У деяких завданнях виділяють один продукт, а другим вважають всі інші. Тому спочатку розглянемо модель з двома видами продуктів. Споживчий набір - це вектор (x 1, x 2), координата x 1 якого дорівнює кількості одиниць першого продукту, а координата x 2 дорівнює кількості одиниць другого продукту.
Вибір споживача характеризується відношенням переваги, суть якого полягає в наступному. Вважається, що споживач про кожні два набори може сказати, що або один з них більш бажаний, ніж інший, або споживач не бачить між ними різниці. Відношення переваги транзитивно, тобто якщо набір А = (а 1, а 2) ​​переважніше набору B = (b 1, b 2), а набір B = (b 1, b 2) переважніше набору С = (з 1, с 2), то набір А = (а 1, а 2) ​​переважніше набору С = (з 1, с 2).
На безлічі споживчих наборів (x 1, x 2) визначена функція u (x 1, x 2) (звана функцією корисності споживача), значення u (x 1, x 2) якої на споживчому наборі (x 1, x 2) одно споживчої оцінці індивідуума для цього набору. Споживчу оцінку u (x 1, x 2) набору (x 1, x 2) прийнято називати рівнем (або ступенем) задоволення споживчого індивідуума, якщо він купує або споживає даний набір (x 1, x 2). Кожен споживач має, взагалі кажучи , свою функцію корисності. Якщо набір А переважніше набору В, то u (А)> u (В).
Функція корисності задовольняє наступним властивостям:
1. Зростання споживання одного продукту при постійному споживанні іншого продукту веде до зростання споживчої оцінки, тобто якщо x > X , То u (x , X 2)> u (x , X 2);
якщо x > X , То u (x 1, x )> U (x 1, x ).
Інакше кажучи, u (X 1, x 2) = u > 0, u (X 1, x 2) = u > 0.
Перші приватні похідні u і u називаються граничними полезностями першого і другого продуктів відповідно.
2. Гранична корисність кожного продукту зменшується, якщо обсяг його споживання зростає (закон спадання граничної корисності). З властивості другої похідної випливає, що u (X 1, x 2) <0, u (X 1, x 2) <0.
3. Гранична корисність кожного продукту збільшується, якщо зростає кількість іншого продукту. У цьому випадку продукт, кількість якого фіксоване, виявляється щодо дефіцитним. Якщо блага можуть заміщати один одного в споживанні, властивість не виконується. U (X 1, x 2) = u 12> 0, u (X 1, x 2) = u 21> 0.
Лінія, що з'єднує споживчі набори (x 1, x 2), що мають один і той же рівень задоволення потреб називається лінією байдужості. Лінія байдужості є не що інше, як лінія рівня функції корисності. Безліч ліній байдужості називається картою ліній байдужості. Лінії байдужості, що відповідають різним рівням задоволення потреб не перетинаються і не стосуються. Чим вище і правіше розташована лінія байдужості, тим більшого рівня задоволення потреб вона відповідає. Умови 1-3 означають, що лінія байдужості убуває і є опуклою вниз.
Завдання споживчого вибору полягає у виборі такого споживчого набору , Х ), Який максимізує його функцію корисності при заданому бюджетному обмеженні.
Бюджетне обмеження означає, що грошові витрати на продукти не можуть перевищувати грошового доходу, тобто p 1 x 1 + p 2 x 2 ≤ Q, де p 1 і p 2 - ринкові ціни, а Q - дохід споживача, який він готовий витратити на придбання першого і другого продуктів. Величини p 1, p 2 і Q задані.
Завдання споживчого вибору має вигляд:
u (x 1, x 2) → max
при обмеженні p 1 x 1 + p 2 x 2 ≤ Q
і умова x 1 ≥ 0, x 2 ≥ 0.
Допустиме безліч (тобто безліч наборів продуктів, доступних для споживача) представляє собою трикутник, обмежений осями координат і бюджетної прямої. На цій множині потрібно знайти точку, що належить кривій байдужості з максимальним рівнем корисності. Пошук цієї точки можна інтерпретувати графічно як послідовний перехід на лінії все більш високого рівня корисності до тих пір, поки ці лінії ще мають спільні точки з допустимим безліччю.
бюджетна пряма
Лінії байдужості
X 1


SHAPE \ * MERGEFORMAT
X 2

2) Рішення задачі споживчого вибору і його властивості.
Набір , Х ), Який є рішенням задачі споживчого вибору, прийнято називати оптимальним для споживача.
Розглянемо деякі властивості завдання споживчого вибору. По - перше, рішення задачі , Х ) Зберігається при будь-якому монотонному (тобто зберігає порядок значенні) перетворенні функції корисності u (x 1, x 2). Оскільки значення u (х , Х ), Було максимальним на всьому допустимому безлічі, воно залишається таким і після монотонного перетворення функції корисності (припустиме безліч, визначається бюджетним обмеженням, залишається незмінним). Таким монотонним перетворенням може бути множення функції корисності на деяке позитивне число, зведення її в позитивну ступінь, логарифмування.
По - друге, рішення задачі споживчого вибору не зміниться, якщо всі ціни і дохід збільшуються (зменшуються) в одне і те ж число раз λ. (Λ> 0)
Це рівнозначно множенню на позитивне число λ обох частин бюджетного обмеження p 1 x 1 + p 2 x 2 ≤ Q, що дає нерівність, еквівалентну вихідному. Оскільки ні ціни, ні дохід Q не входять у функцію корисності, завдання залишається тією ж, що й спочатку.
Якщо на якому - то споживчому наборі (x 1, x 2) бюджетне обмеження p 1 x 1 + p 2 x 2 ≤ Q буде виконуватися у вигляді строгої нерівності, то ми можемо збільшити споживання будь - якого з продуктів і тим самим збільшити функцію корисності . Отже, набір , Х ), Максимізує функцію корисності, повинен звертати бюджетне обмеження в рівність, тобто p 1 х + P 2 х = Q.
Графічно це означає, що рішення , Х ) Завдання споживчого вибору повинно лежати на бюджетній прямій, яка проходить через точки перетину з осями координат, де весь дохід витрачатися на один продукт: (0, ) І ( , 0).
Отже, завдання споживчого вибору можна замінити завданням на умовний екстремум (бо рішення , Х ) Цих двох завдань одне й те саме)
u (x 1, x 2) → max
за умови p 1 x 1 + p 2 x 2 = Q.
Для вирішення цього завдання застосуємо метод Лагранжа. Виписуємо функцію Лагранжа L (x 1, x 2, λ) = u (x 1, x 2) + λ (p 1 x 1 + p 2 x 2 - Q), знаходимо її приватні похідні за змінними x 1, x 2 і λ і прирівнюємо до нуля:
L = U + Λ p 1 = 0,
L = U + Λ p 2 = 0,
L = P 1 x 1 + p 2 x 2-Q = 0.
Виключивши з отриманої системи невідому λ, отримаємо систему двох рівнянь з двома невідомими x 1, і x 2
= ,
p 1 x 1 + p 2 x 2 = Q .
Рішення , Х ) Цієї системи є критична точка функції Лагранжа. Підставивши рішення , Х ) У ліву частину рівності
= ,
отримаємо, що в точці , Х ) Відношення граничних корисностей u , Х ) І u , Х ) Продуктів дорівнює відношенню ринкових цін p 1 і p 2 на ці продукти:
= . (5.1)
У зв'язку з тим, що ставлення одно граничній нормі заміни першого продукту другим у точці локального ринкової рівноваги , Х ), З (5.1) випливає, що ця гранична норма дорівнює відношенню ринкових цін на продукти. Наведений результат грає важливу роль в економічній теорії.
Геометрично рішення , Х ) Можна інтерпретувати як точку дотику лінії байдужості функції корисності u (x 1, x 2) з бюджетної прямої p 1 x 1 + p 2 x 2 = Q. Це визначається тим, що ставлення =- показує тангенс кута нахилу лінії рівня функції корисності, а відношення - представляє тангенс кута нахилу бюджетної прямої. Оскільки в точці споживчого вибору вони рівні, в цій точці відбувається дотик даних двох ліній.
Вирішимо задачу споживчого вибору.
Оптимальний набір споживача складає 6 од. продукту х 1 і 8 од. продукту х2. Визначте ціни споживаних благ, якщо відомо, що дохід споживача дорівнює 240 руб. Функція корисності споживача має вигляд: u (x 1, x 2) = x x .
Рішення. Виходячи з принципу рішення, отримуємо систему рівнянь:
= , = , = ,
p 1 x 1 + p 2 x 2 = 240. p 1 x 1 + p 2 x 2 = 240. p 1 x 1 + p 2 x 2 = 240.
Підставивши, замість х 1 - 6 од., Замість х 2 - 8 од., Отримаємо: p 1 = 10 руб., P 2 = 22.5 руб.
3) Загальна модель споживчого вибору.
Була розглянута модель споживчого вибору з двома продуктів та її рішення за допомогою методу множників Лагранжа. Зараз розглянемо властивості завдання споживчого вибору з довільним числом продуктів і цільовою функцією загального вигляду.
Нехай задана цільова функція переваги споживача u (x 1, x 2, ..., х n), де х i - кількість i-го продукту, вектор цін p i = (p 1, p 2, ..., p n), і дохід Q . Записавши бюджетне обмеження і обмеження на неотрицательности, отримуємо завдання
u (x) → max (5.2)
за умови px ≤ Q, x ≥ 0
(Тут x = (x 1, x 2, ..., х n), p = (p 1, p 2, ..., p n), px = (p 1 x 1 + ... + p n x n)).
Будемо вважати, що невід'ємності змінних забезпечується властивостями цільової функції та бюджетного обмеження. У цьому випадку можна записати функцію Лагранжа і дослідити її на безумовний екстремум.
L (x, λ ) = U (x) + λ (px - Q).
Необхідна умова екстремуму - рівність нулю приватних похідних: L = U + Λ p i = 0 для всіх i [1; n] і L = Px - Q = 0. Звідси випливає, що для всіх i в точці х ринкової рівноваги виконується рівність
(5.3)
яке виходить після перенесення друге доданків, необхідних умов в праву частину і діленням i-го рівності на j-та. Отже, в точці оптимуму відношення граничних корисностей будь-яких двох продуктів дорівнює відношенню їх ринкових цін. Рівність (5.3) можна переписати і в іншій формі:
(5.4)
Це означає, що корисність, що припадає на одиницю грошових витрат, у точці оптимуму однакова по всіх видах благ. Якби це було не так, то принаймні одну грошову одиницю можна було б перерозподілити так, щоб зріс добробут (значення функції корисності) споживача. Якщо для деяких i, j
,
то деяку кількість грошей можна було б перерозподілити від i-го продукту до j-му, збільшивши рівень добробуту.
4) Модель Стоуна. Виведемо тепер функцію попиту для конкретної функції споживчої переваги, званою функцією Р. Стоуна. Ця функція має вигляд
u (x) = → max                               (5.5)
Тут а i - мінімально необхідну кількість i-го продукту, що придбавається в будь-якому випадку і не є предметом вибору. Для того щоб набір {a i} міг бути повністю придбаний, необхідно, щоб дохід Q був більше - Кількість грошей, необхідного для купівлі цього набору. Коефіцієнти ступеня а i> 0 характеризують відносну «цінність» продуктів для споживача.
Додавши до цільової функції (5.5) бюджетні обмеження ≤ Q, х i ≥ 0, отримаємо задачу, звану моделлю Стоуна. Як було сказано на стор 36, бюджетне обмеження повинно звертатися в рівність. Складемо функцію Лагранжа L (x 1, x 2, ..., х n, λ ) = U (x) + λ (p 1 x 1 + ... + p n x n - Q).
Знайдемо приватні похідні функції Лагранжа і прирівняємо їх до нуля L = A 1 (x 1 - a 1) ∙ (x 2 - a 2) ∙ ... ∙ (x n - a n) + Λ p 1.
Аналогічно отримуємо інші приватні похідні. Тобто
L = + Λ p i = 0, де i = .
Висловивши x i, отримаємо x i = a i - . (5.6)
L = - Q = 0. Помноживши кожне з рівностей (5.6) на λ p i і підсумувавши їх по i, маємо
= 0 (5.7).
Оскільки в точці оптимуму бюджетне обмеження виконується як рівність, замінимо на Q, одержимо = 0. Поділивши на λ, отримаємо =- (Q - ). Звідки . Отриманий вираз підставляємо в рівність (5.6)
x i = a i + (5.8)
Тобто спочатку купується мінімально необхідну кількість продукту a i. Потім розраховується сума грошей, що залишається після цього, яка розподіляється пропорційно "ваг» важливості i. Розділивши кількість грошей на ціну p i, отримуємо додатково купується, понад мінімум, кількість i-продукту і додаємо його до а i. [1]
Висновок
При написанні роботи мною була вивчена література по даній темі. Були розглянуті математичні моделі в економіці, повторені деякі поняття функцій декількох змінних, необхідних для вивчення оптимізаційних завдань. Також була вивчена постановка задач математичного програмування і методи їх вирішення. Було розглянуто симплексний метод, який дозволяє вирішити будь-яке завдання лінійного програмування. Для ЗЛП була розглянута симетрична взаімодвойственная завдання і метод її вирішення з використанням теорем подвійності. Для задачі нелінійного програмування було розглянуто геометричний метод розв'язання. А також розглянуто задачі на умовний екстремум.
У роботі наводиться завдання споживчого вибору, рішення якої зводиться до розв'язання задач на умовний екстремум. Також розглянуто окремий випадок задачі споживчого вибору - модель Стоуна.
Мною були вирішені завдання по кожному виду розглянутих оптимізаційних завдань. Це ЗЛП симплексним і графічним методом, вирішена двоїста задача, кілька задач нелінійного програмування, задачі на умовний екстремум методом підстановки і методом множників Лагранжа, завдання споживчого вибору.
Я вважаю, що знання цієї теми може стати в нагоді не тільки економістам і людям, спеціально займається цією наукою, але і ненауковим працівникам, тому що в житті часто доводиться стикатися з рішенням подібного роду завдань.

Бібліографічний список
1. Замків, О.О. Математичні методи в економіці: Підручник / За заг. ред. д.е.н., проф. А.В. Сидоровича / О.О. Замків, А.В. Толстопятенко, Ю.М. Черемних; МДУ ім. Ломоносова.-3-е изд., Перераб. - М.: Видавництво «Справа і Сервіс», 2001
2. Ільїн, В.А. Математичний аналіз / В.А. Ільїн, В.А. Садовничий, Б.Х. Сенді. - М.: Наука, 1979
3. Красс, М.С. Основи математики і її застосування в економічній освіті: Підручник. - 3-е вид. - М.: Справа, 2002
4. Кремер, Н.Ш. Вища математика для економістів: Підручник для вузів / Н.Ш. Кремер, Б.А. Путко, І.М. Тришин, М.М Фрідман. - М.: ЮНИТИ, 2002.
5. Кремер, Н.Ш. Дослідження операцій в економіці: Навчальний посібник для вузів / Н.Ш. Кремер, Б.А. Путко, І.М. Тришин, М.М. Фрідман; Під ред. проф. Н.Ш. Кремера. - М.: Банки і біржі, ЮНИТИ, 1997.
6. Малихін, В.І. Математика в економіці: Навчальний посібник .- М.: ИНФРА - Москва, 2002.
7. Симонов, А.В. Про один додатку похідної до вирішення економічних завдань / А.С. Симонов, Н.Г. Ігнатьєв / / математика в школі № 9, 2001
8. Збірник завдань і вправ з вищої математики: мат. програмування: Учеб. Посібник / О.В. Кузнєцов, В.А. Сакович, Н.І. Холод; Під. заг. ред. А.В. Кузнєцова - Мн. Обчислюємо. шк., 2002
9. Збірник задач з вищої математики для економістів: Навчальний посібник / Під. ред. В.І. Єрмакова .- М.: Инфра - Москва, 2002.
10. Збірник завдань по мікроекономіці. До «Курсу мікроекономіки» Р.М. Нурєєва / Гол. ред. д.е.н., проф. Р.М. Нурієв. - М.: Норма, 2003
11. Фіхтенгольц, Г.М. основи математичного аналізу. Частина 1. 4-е вид. - СПб: видавництво «Лань», 2002.
12. Онегов, В.А. Дослідження операцій. Завдання, методи, алгоритми. - К.: ВДПУ, 2001.
Додати в блог або на сайт

Цей текст може містити помилки.

Економіко-математичне моделювання | Диплом
255.6кб. | скачати


Схожі роботи:
Деякі аспекти оптимізації параметрів ядерного палива для ВВЕР
Завдання оптимізації
Завдання оптимізації взаємодії людини і живої природи стратегія майбутнього
Передумови аудиту та його завдання в ринковій економіці
Завдання статистики в ринковій економіці Система показників демографічної статистики
Вправа - завдання - тестове завдання точки перетину
Вправа завдання тестове завдання точки перетину
Методи оптимізації господарства
Дослідження методів оптимізації
© Усі права захищені
написати до нас