ЗАГАЛЬНА ПОСТАНОВКА Й РІЗНОВИДИ ЗАДАЧ МАТЕМАТИЧНОГО ПРОГРАМУВАННЯ⇐ ПредыдущаяСтр 14 из 14
Математичне програмування - велика галузь знань. Ми розглянули далеко не повністю один з розділів - лінійне програмування. Загальна математична схема задачі математичного програмування така: дана деяка функція 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-х книгах).- 4. Міну М. Математичне програмування. Теорія й
ЗМІСТ
1. РІШЕННЯ СИСТЕМ ЛІНІЙНИХ РІВНЯНЬ МЕТОДОМ ГАУСА - ЖОРДАНА........................................................ . . . . . . . . . . . . . . . . . . 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. СИМПЛЕКСНИЙ МЕТОД РІШЕННЯ ЗЛП 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
©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|