Industrialnet Головна Про сайт webcache.site checkip.site takescreenshot.site
  • Строрінки

  • Симплексний метод розв'язання задач лінійного програмування

    Лінійне програмування

  • Математичні моделі задач лінійного програмування
  • Симплексний метод розв'язання задач лінійного програмування
  • Транспортна задача. Математична модель [1 ч.]
  • Транспортна задача. Опорне рішення [2 ч.]. Метод північно-західного кута
  • Лекції з Вищої математики
  • Симплексний метод розв'язання задач лінійного програмування
  • Зміст
  • Симплексний метод
  • Алгоритм симплексного методу розв'язування задач лінійного програмування
  • Метод лінійного програмування в економічному аналізі
  • Симплексний метод

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

    Основний зміст симплексного методу полягає в наступному:
  • Вказати спосіб знаходження оптимального опорного рішення
  • Вказати спосіб переходу від одного опорного рішення до іншого, на якому значення цільової функції буде ближче до оптимального, тобто вказати спосіб поліпшення опорного рішення
  • Задати критерії, які дозволяють своєчасно припинити перебір опорних рішень на оптимальному рішенні або следать висновок про відсутність оптимального рішення.
  • Алгоритм симплексного методу розв'язування задач лінійного програмування Для того, щоб вирішити задачу симплексним методом необхідно виконати наступне:
  • Привести задачу до канонічного виду
  • Знайти початкове опорне рішення з одиничним базисом" (якщо опорне рішення відсутнє, то задача не має рішення через несумісність системи обмежень)
  • Обчислити оцінки розкладів векторів за базисом опорного рішення та заповнити таблицю симплексного методу
  • Якщо виконується ознака єдиності оптимального рішення, то рішення задачі закінчується
  • Якщо виконується умова існування множини оптимальних рішень, то шляхом простого перебору знаходять оптимальні рішення
  • Приклад рішення задачі симплексним методом Приклад 26.1

    Розв'язати симплексним методом задачу:

    Рішення:

    Наводимо задачу до канонічного виду.

    Для цього в ліву частину першого обмеження-нерівності вводимо додаткову змінну x6 з коефіцієнтом +1. У цільову функцію змінна x6 входить з коеффіцентом нуль (тобто не входить).

    Отримуємо:

    Знаходимо початкова опорне рішення. Для цього вільні (недозволені) змінні прирівнюємо до нуля х1 = х2 = х3 = 0.

    Отримуємо опорне рішення Х1 = (0,0,0,24,30,6) з одиничним базисом Б1 = (А4, А5, А6).

    Обчислюємо оцінки розкладів векторів умов по базису опорного рішення за формулою:

    ?k = CбXk — ck

    Де:

  • Cб = (с1, с2, ... , m ) — вектор коефіцієнтів цільової функції при базисних змінних
  • Xk = (x1, x2, ... , xm ) — вектор розкладання відповідного вектора Адо по базису опорного рішення
  • Здо — коефіцієнт цільової функції при змінній хдо.
  • Оцінки векторів, що входять в базис завжди дорівнюють нулю. Опорне рішення, коэффиценты розкладень і оцінки розкладів векторів умов по базису опорного рішення записуються в симплексную таблицю:

    Зверху над таблицею для зручності обчислень оцінок записуються коефіцієнти цільової функції. У першому стовпці "Б" записуються вектори, що входять в базис опорного рішення. Порядок запису цих векторів відповідає номерам дозволених невідомих у рівнянні обмеження. У другому стовпці таблиці "б" записуються коефіцієнти цільової функції при базисних змінних в тому ж порядку. При правильному розташуванні коефіцієнтів цільової функції у стовпці "б" оцінки одиничних векторів, що входять в базис, завжди дорівнюють нулю.

    В останньому рядку таблиці з оцінками ?k - у стовпці "А0" записуються значення цільової функції на опорному вирішенні Z(X1).

    Початкова опорне рішення не є оптимальним, так як в задачі на максимум оцінки ?1 = -2, ?3= -9 для векторів А1 і А3 негативні.

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

    Визначимо, введення якого з двох векторів призведе до більшого приросту цільової функції.

    Приріст цільової функції знаходиться за формулою: .

    Обчислюємо значення параметра ?01 для першого і третього стовпців за формулою:

    Отримуємо ?01 = 6 при l = 1, ?03 = 3 при l = 1 (таблиця 26.1).

    Знаходимо приріст цільової функції при введенні в базис першого вектора ?Z1 = — 6*(- 2) = 12, і третього вектора ?Z3 = — 3*(- 9) = 27.

    Отже, для більш швидкого наближення до оптимального рішення необхідно ввести в базис опорного рішення вектор А3 замість першого вектора базису А6, так як мінімум параметра ?03 досягається в першому рядку (l = 1).

    Виробляємо перетворення Жордана з елементом Х13 = 2, отримуємо друге опорне рішення Х2 = (0,0,3,21,42,0) з базисом Б2 = (А3, А4, А5). (таблиця 26.2)

    Це рішення не є оптимальним, так як вектор А2 має негативну оцінку ?2 = — 6. Для поліпшення вирішення необхідно ввести вектор А2 в базис опорного рішення.

    Визначаємо номер вектора, що виводиться з базису. Для цього обчислюємо параметр ?02 для другого стовпця, він дорівнює 7 при l = 2. Отже, з базису виводимо другий вектор базису А4. Виробляємо перетворення Жордана з елементом х22 = 3, одержуємо третє опорне рішення Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблиця 26.3).

    Це рішення є єдиним оптимальним, так як для всіх векторів, що не входять в базис оцінки позитивні

    ?1 = 7/2, ?4 = 2, ?6 = 7/2.

    Відповідь: max Z(X) = 201 при Х = (0,7,10,0,63).

    Метод лінійного програмування в економічному аналізі

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

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

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

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

    Крім цього, даний метод знаходить широке застосування при рішенні задачі складання розкладу. Ця задача полягає в такому розподілі часу функціонування персоналу даної організації, яке було б найбільш прийнятним як для членів цього персоналу, так і для клієнтів організації.

    Ця задача полягає в максимізації кількості обслуговуваних клієнтів в умовах обмежень кількості наявних членів персоналу, а також фонду робочого часу.

    Таким чином, метод лінійного програмування досить поширений в аналізі розміщення і використання різних видів ресурсів, а також у процесі планування та прогнозування діяльності організацій.

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

    Нелінійне програмування спирається на нелінійний характер цільової функції або обмежень, або і того й іншого. Форми цільової функції і обмежень нерівностей в цих умовах можуть бути різними.

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

    Динамічне програмування базується на побудові дерева рішень. Кожен ярус цього дерева стадією служить для визначення наслідків попереднього рішення і для усунення малоефективних варіантів цього рішення. Таким чином, динамічне програмування має багатокроковий, багатоетапний характер. Цей вид програмування застосовується в економічному аналізі з метою пошуку оптимальних варіантів розвитку організації як у даний час, так і в майбутньому.

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

    Copyright © industrialnet.com.ua. 2016 • All rights reserved.