- •6.030504 «Економіка підприємства», 6.030509 «Облік і аудит»
- •1.Рішення систем лінійних рівнянь методом гауса - жордана
- •1.1. Основні поняття
- •1.2. Приведення системи лінійних рівнянь до жорданової форми
- •1.3. Поняття загального, часного й базисного рішень
- •2. Загальні властивості задач лінійного програмування
- •2.І. Приклад задачі лінійного програмування - задача про використання обладнання
- •2.2. Задача про використання сировини
- •2.3. Задачі складання раціону (задача про дієту)
- •2.4. Загальна постановка задач лінійного програмування
- •2.5. Геометричний метод вирішення злп
- •Приклад 1
- •2.6. Канонічний вигляд злп
- •3. Симплексний метод вирішення злп
- •3.1. Загальна характеристика й основні етапи симплекс - методу
- •3.2. Табличний вигляд злп. Симплекс - таблиці
- •3.3. Умова оптимальності опорного плану
- •3.4. Умова нерозв'язності злп через необмеженість знизу на опр цільової функції
- •3.5. Перехід до нового опорного плану.
- •3.6. Табличний симплекс-алгоритм
- •Після вибору генерального елемента переходимо до таблиці 3.11
- •Знову вибираємо генеральний елемент і переходимо до таблиці 3.14
- •3.7. Відшукування початкового опорного плану злп методом штучного базису
- •3.8. Виродженість опорного плану. Зациклення
- •Двоїстість у лінійному програмуванні
- •5.4. Цикли перерахування
- •5.4.1. Поняття циклу перерахування
- •5.4.2. Максимально припустиме зрушення по циклу перерахування
- •5.4.3. Ціна циклу перерахування
- •5.5. Потенціали
- •5.6. Алгоритм вирішення транспортної задачі методом потенціалів
- •5.7. Відкриті транспортні задачі.
- •6. Цілочислове лінійне програмування
- •6.1. Загальна постановка задачі цілочислового лінійного програмування (зцлп)
- •6.2. Цілочислова задача про використання сировини
- •6.3. Задача про рюкзак
- •6.4. Вирішення зцлп методом округлення
- •6.5. Метод гілок і меж
- •Оптимальний план оптимальний план
- •7. Загальна постановка й різновиди задач математичного програмування
- •Література
7. Загальна постановка й різновиди задач математичного програмування
Математичне програмування - велика галузь знань. Ми розглянули далеко не повністю один з розділів - лінійне програмування.
Загальна математична схема задачі математичного програмування така: дана деяка функція
z = f(x1, x2, . . . , xn) (7.1)
і деяка система обмежень , накладених на змінні x1, x2, . . . , xn:
Потрібно знайти такий набір значень змінних x1, x2, . . . , xn, що задовольняє обмеженням (7.2), і при цьому мінімізує або максимізує функцію (7.1).
Якщо всі функції, що фігурують в (7.1) і (7.2), лінійні, то ми маємо ЗЛП. У протилежному випадку виходить задача нелінійного програмування.
Для задач нелінійного програмування немає такого універсального методу вирішення, яким є симплекс-метод для ЗЛП. Тільки для вузьких класів задач нелінійного програмування розроблені точні методи, основна маса вирішується приблизно.
У деяких задачах математичного програмування ОПР складається з дискретної множини точок. Такі задачі називаються дискретними оптимізаційними задачами. Наприклад, якщо в ЗЛП зажадати, щоб змінні приймали тільки цілі значення, то вийде дискретна оптимізаційна задача - задача цілочислового лінійного програмування. Дискретні задачі, як правило, складніші безперервних. Із задач дискретної оптимізації в теперішні часи проводяться інтенсивні наукові дослідження.
Важливою галуззю є й динамічне програмування. Тут вивчаються методи поетапного вирішення оптимізаційних задач. Такі методи використовуються в особливо складних задачах. Наприклад, при складанні плану роботи заводу на рік доцільно розбити рік по місяцях і план роботи на кожний місяць погоджувати із планами на попередні й наступні місяці.
Нарешті відзначимо, що зустрічаються задачі математичного програмування, в яких вихідні дані є випадковими величинами. Такі задачі вивчає стохастичне програмування. Стохастичне програмування використовує теоретико-імовірнісні, статистичні й оптимізаційні методи.
З математичного програмування написано вже багато книг. Література, що приводиться - незначна частина їх. Але в ній можна знайти виклад основних положень математичного програмування, а також посилання на інші джерела.
Література
1. Крушевский А.В., Зшивальників К.М. Математичне програмування й моделювання в економіці.-К.: Вища шк., 1979
2. Ковалів Ю.Н., Кузубов В.М., Волощенко А.Б. Математичне програмування.-М.: Высш.шк.,1980
3. Таха X. Введення в дослідження операцій. (В 2-х книгах).- М.:Мир,1985
4. Міну М. Математичне програмування. Теорія й алгоритми.-М.: Наука, 1990.
ЗМІСТ
РІШЕННЯ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ МЕТОДОМ ГАУСА - ЖОРДАНА........................................................ . . . . . . . . . . . . . . . . . . 4
1.1. Основні поняття ...................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
1.2. Приведення системи лінійних рівнянь до жорданової форми. . . . 5
1.3. Поняття загального, часного й базисного рішень . . . . . . . . . . . . . 7
2.ЗАГАЛЬНІ ВЛАСТИВОСТІ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ
2.І. Приклад задач лінійного програмування – задача про використання обладнання . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.
2.2. Задача про використання сировини . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3. Задача складання раціону (задача про дієту) . . . . . . . . . . . . . . . . . .9
2.4. Загальна постановка задач лінійного програмування (ЗЛП) . . . . .10
2.5. Геометричний метод рішення ЗЛП . . . . . . . . . . . . . . . . . . . . . . . . . .11.
2.6. Канонічний вигляд ЗЛП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .15
2.7. Поняття опорного плану ЗЛП . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
СИМПЛЕКСНИЙ МЕТОД РІШЕННЯ ЗЛП
3.1. Загальна характеристика і основні етапи симплекс – методу . . . . .17
3.2.Табличний вид ЗЛП. Симплекс – таблиці . . . . . . . . . . . . . . . . . . . . . 18
3.3. Умова оптимальності опорного плану . . . . . . . . . . . . . . . . . . . . . . . .20
3.4. Умова нерозв'язності ЗЛП через необмеженість знизу на ОПР цільовій функції . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . .20
3.5. Перехід до нового опорного плану . . . . . . . . . . . . . . . . . . . . . . . . . .21
3.6. Табличний симплекс-алгоритм . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.7. Відшукання початкового опорного плану ЗЛП методом штучного базису . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.8. Виродженість опорного плану. Зациклення . . . . . . . . . . . . . . . . . . . .34
4. ДВОЇСТІСТЬ У ЛІНІЙНОМУ ПРОГРАМУВАННІ
4.1. Економічна інтерпретація двоїстих задач . . . . . . . . . . . . . . . . . . . . .35
4.2. Поняття двоїстої задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36
4.3. Теореми двоїстості . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .37
5. ТРАНСПОРТНА ЗАДАЧА
5.1. Задача про перевезення . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
5.2. Загальна постановка транспортної задачі . . . . . . . . . . . . . . . . . . . . . .40
5.3. Відшукання початкового опорного плану . . . . . . . . . . . . . . . . . . . . 41 5.4. Цикли перерахування . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
5.5. Потенціали . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46.
5.6. Алгоритм вирішення транспортної задачі методом потенціалів . . .49
5.7. Відкриті транспортні задачі . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
6. ЦІЛОЧИСЛОВЕ ЛІНІЙНЕ ПРОГРАМУВАННЯ
6.1. Загальна постановка задачі цілочислового лінійного програмування (ЗЦЛП) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..53
6.2. Цілочислова задача про використання сировини . . . . . . . . . . . . . . . . .54
6.3. Задача про рюкзак . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
6.4. Вирішення ЗЦЛП методом округлення . . . . . . . . . . . . . . . . . . . . . . . . 55
6.5. Метод гілок і меж . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56
7. ЗАГАЛЬНА ПОСТАНОВКА І РІЗНОВИДИ ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Література . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
Зміст . . . . . .. . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .59