Задачі лінійного програмування

Прийняття управлінських рішень

Припустімо, що задача лінійного програмування має такий вигляд:

і = с1 х1 + с2 х2 -" тах(тіп):

ацх1 ~т~ х2 - Ь1:

х1 > 0, х2 > 0.

Вважатимемо, що багатокутник розв'язків (область допустимих розв'язків) цієї задачі непорожній та обмежений. Тоді алгоритм графічного методу розв'язання задачі лінійного програмування складається з таких кроків.

1. На основі обмежень задачі в площині змінних Ох1 х2 будуємо

прямі, рівняння яких мають вигляд аі1 х1 + аі2х2 - Ьі = 0, і = 1, т.

• 2. Визначаємо ту частину площини, в якій виконується кожне з обмежень задачі.

• 3. Знаходимо багатокутник розв'язків задачі.

• 4. Будуємо вектор gradz = ^-i = cli + c2j, що задає на-

dxl <3x2

прям зростання цільової функції.

• 5. Проводимо пряму cl xl + c2 x2 = const, перпендикулярно до вектора grad z.

• 6. Рухаючи пряму clxl + c2x2 = const у напрямку вектора grad z (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв'язків, де цільова функція набуває екстремального значення.

• 7. Визначаємо координати точки, в якій цільова функція набуває максимального (мінімального) значення, й обчислюємо екстремальне значення цільової функції в цій точці.

Геометрична інтерпретація задач лінійного програмування можлива лише за наявності двох незалежних змінних. Якщо кількість змінних більша двох, зображення істотно ускладнюється або взагалі неможливе. Проте ідея одержання розв'язку, що лежить в основі графічного методу, зберігає зміст і для випадку багатовимірного простору.

На основі такої ідеї створений і розроблений один з основних точних методів розв'язання задач лінійного програмування - так званий симплекс-метод. Суть методу полягає в отриманні оптимального розв'язку шляхом перебирання допустимих розв'язків у такий спосіб, що на кожному кроці здійснюється перехід від одного допустимого розв'язку до наступного, яке за значенням цільової функції було б хоча б не гіршим за попереднє. При цьому перебираються лише вершини допустимого багатокутника.

Алгоритм симплекс-методу гарантує, що за наявності хоча б одного допустимого розв'язку за скінчену кількість кроків буде або одержаний оптимальний розв'язок, або доведена відсутність таких розв'язків.

Розглянемо послідовність дій під час реалізації цього алгоритму.

• 1. Модель практичної задачі лінійного програмування звести до канонічного вигляду за умови пошуку найбільшого значення цільової функції.

Сторінки


В нашій електронній бібліотеці ви можете безкоштовно і без реєстрації прочитати «Прийняття управлінських рішень» автора Автор невідомий на телефоні, Android, iPhone, iPads. Зараз ви знаходитесь в розділі „Задачі лінійного програмування“ на сторінці 2. Приємного читання.

Зміст

  • Вступ

  • Розділ 1. Сутність, природа і класифікація управлінських рішень

  • Основні етапи розробки та прийняття управлінських рішень

  • Класифікація управлінських рішень

  • Розділ 2. Людський фактор психологічні аспекти управлінських рішень

  • Особливості стилів прийняття управлінських рішень

  • Неформальні аспекти розробки рішень

  • Розділ 3. Класифікація методів прийняття управлінських рішень

  • Методи генерації ідей, оцінювання і вибору варіанта рішення

  • Розділ 4. Моделі та методи прийняття оптимальних рішень

  • Математичне програмування як засіб прийняття оптимальних управлінських рішень

  • Задачі лінійного програмування
  • Задачі лінійного цілочислового програмування

  • Розділ 5. Математичні методи розробки рішень у логістичній діяльності

  • Транспортна задача за критерієм часу та декількома критеріями

  • Розділ 6. Використання нелінійного та динамічного програмування в розробці управлінських рішень

  • Динамічне програмування

  • Розділ 7. Експертні методи в розробці управлінських рішень

  • Формування експертних оцінок та оцінка узгодженості експертів

  • Розділ 8. Методи прогнозування розробці управлінських рішень

  • Якісні методи прогнозування

  • Розділ 9. Теорія ігор. Прийняття управлінських рішень в умовах ризику та невизначеності

  • Моделювання ризикових ситуацій в управлінні

  • Ризики

  • Розділ 10. Прийняття стратегічних управлінських рішень

  • Стратегічне мислення і бачення

  • Процес установлення організаційних цілей

  • Розділ 11. Прийняття управлінських рішень у сфері маркетингу

  • Процес стратегічного маркетингового аналізу

  • Обґрунтування стратегічних і тактичних маркетингових рішень

  • Розділ 12. Прийняття фінансових та інвестиційних рішень

  • Моделі управління грошовими потоками

  • Управління інвестиційними рішеннями

  • Методи оцінки, що ґрунтуються на дисконтуванні (NPV, IRR, DPP)

  • Розділ 13. Прийняття рішень у сфері управління персоналом

  • Управлінські рішення щодо професійної діяльності працівників

  • Управлінські рішення у сфері мотивації

  • Розділ 14. Інформаційна підтримка процесу розробки і прийняття управлінських рішень

  • Класифікація інформаційних систем

  • Інформаційні системи підтримки прийняття управлінських рішень

  • Система фінансового моделювання та аналізу Project Expert

  • Література