Графічний метод для задач ЛП n-вимірного простору при - Розв'язання задач математичного програмування
Нехай кількість змінних N
Число обмежень M,
.
Дві з N змінних, наприклад Х1 та Х2 Вільні, інші M базисні
рівнянь вигляду:
Оскільки, то
,
(2.19.1)
Узявши величину Х3 рівною нулю, отримаємо рівняння:
.
Для такої прямої,
Відмітимо ту півплощину, де. Аналогічно ; ;...;. Спільна частина площини в - багатокутник допустимих розв'язків.
Необхідно знайти максимальне значення функціонала:
.
Підставивши, , ,...; з (2.19.1) у функціонал, отримаємо F через дві вільні змінні та :
,
Де -- вільний член. Далі відшукання оптимального плану здійснюється за алгоритмом для випадку двох змінних.
Розв'язати графічним методом задачу лінійного програмування
.
Розв'язання.
N = 7 -- кількість змінних, M = 5 -- кількість обмежень.
Вільні змінні Х1 та Х2 і виразимо через них всі базисні змінні.
(2.19.2)
, (2.19.3)
. (2.19.4)
;
.
Далі за алгоритмом беремо Х1 = 0 та Х2 = 0 -- координатні осі; інші обмежуючі прямі знаходимо, узявши Х3 = 0, Х4 = 0, Х5 = 0, Х6 = 0, Х7 = 0. Багатокутник допустимих розв'язків зображено на рис. 2.12.
Рис. 2.12
Знайдемо вигляд функціонала, вираженого через Х1 та Х2.
.
Відкидаючи вільний член, маємо: .
Будуємо вектор (-5, -2), а перпендикулярно пряму F.
Рухаючи пряму F в напрямку, протилежному (необхідно знайти мінімальне значення функції F), отримаємо точку мінімуму -- А (рис. 2.13).
Рис. 2.13
У точці А перетинаються дві обмежуючі прямі: Х6 = 0 та Х7 = 0.
= 8,5; = 5.
Звідки
= 0,5; = 16,5; = 17,5; = 0; = 0.
Підстановкою значень та в лінійну функцію F отримуємо значення цільової функції:
.
Симплексний метод розв'язування задач лінійного програмування
З властивостей розв'язків задачі лінійного програмування відомо: оптимальний розв'язок задачі має знаходитись в одній з кутових точок багатогранника допустимих розв'язків. Загальна кількість опорних планів визначається кількістю комбінацій.
1949 року американським вченим Дж. Данцігом запропоновано Симплекс-метод.
Похожие статьи
-
Розглянемо задачу. Знайти (2.17) За умов: (2.18) . (2.19) Припустимо, що система (2.18) за умов (2.19) сумісна і багатокутник її розв'язків обмежений....
-
Теорема 2.2. Множина всіх планів задачі лінійного програмування опукла. Доведення . Необхідно довести, що коли X 1 та X 2 -- плани задачі лінійного...
-
Подамо схематично довільну економічну систему у такому вигляді (рис. 1.1): Рис. 1.1 Схема економічної системи Параметри С K ( K = 1, 2,..., l ) -...
-
Якщо в транспортній задачі не виконується така умова, тобто загальна кількість продукції постачальників не дорівнює загальному попиту всіх споживачів, то...
-
До задач дробово лінійного програмування відносяться задачі нелінійного програмування математична модель яких в загальному можна представити в наступному...
-
1. За допомогою знака суми "". (2.6) 2. У векторно-матричному вигляді: Max(min) Z = CX АХ = А 0; (2.7) Х ? 0, Де , , Матриця коефіцієнтів; вектор...
-
Приклади економічних задач МП та їх моделей - Розв'язання задач математичного програмування
Задача визначення оптимального плану виробництва : для деякої виробничої системи (цеху, підприємства, галузі) необхідно визначити план випуску кожного...
-
Класифікація задач математичного програмування - Розв'язання задач математичного програмування
Рис. 1.2 Класифікація задач математичного програмування У математичному програмуванні виділяють два напрямки -- Детерміновані задачі і Стохастичні ....
-
Історична довідка - Розв'язання задач математичного програмування
Початком математичного програмування в сучасному розумінні вважають праці радянського вченого Л. В. Канторовича. (монографія "Математичні методи...
-
Приклади розв'язування задач графічним методом - Розв'язання задач математичного програмування
Фірма спеціалізується на виробництві офісних меблів, зокрема вона випускає два види збірних книжкових полиць -- А та В. Полиці обох видів виготовляють на...
-
Умова цілочисловості є по суті нелінійною і може зустрічатися в задачах, що містять як лінійні, так і нелінійні функції. Задачі математичного...
-
Для побудови алгоритмів розв'язання задач матричних ігор використовується властивість оптимальних змішаних стратегій: оптимальна змішана стратегія...
-
В основі моделі (2.2.) - (2.6) лежить рівняння, яке має вигляд: , Зробимо просте перетворення, зробивши заміну: (2.7) І отримаємо рівняння (2.8): (2.8)...
-
Методом розв'язку ТЗ є метод потенціалів. для того, щоб можна було застосувати цей метод, необхідне виконання 2х умов: - ТЗ є закритою; - побудовано...
-
Предмет та об'єкти математичного програмування - Розв'язання задач математичного програмування
Переклад англійського терміну Mathematical programming означає розроблення на основі математичних розрахунків Програми Дій для досягнення обраної мети ....
-
Закритою називається транспортна задача в якій загальна кількість продукції постачальників дорівнює загальному попиту всіх споживачів, тобто . Теорема:...
-
1. записуємо цільову функцію та обмеження 2. приводимо систему обмежень до канонічної форми 3. знаходимо рівняння прямої. Будуємо ці прямі в системі...
-
Складемо симплексну таблицю для першого опорного плану задачі. Елементи останнього рядка симплекс-таблиці є оцінками j, за допомогою яких опорний план...
-
ВСТУП, - Методи розв'язування різних типів економічних задач
Економіко-математичне моделювання є галуззю економічної науки, яка вивчає основні принципи та інструментарій постановки економічних задач, побудови їх...
-
Характеристичний багаточлен матриці, Розв'язання рівнянь - Вивчення математичного пакету MathСad
Для побудови характеристичного багаточлена матриці A використаємо символьні обчислення. Побудуємо матрицю D = A - Е, віднявши з діагональних елементів...
-
Всі економічні процеси та явища є динамічними, оскільки вони функціонують і розвиваються не тільки у просторі, але й у часі. Для народного господарства в...
-
1. Задача оптимального планування виробництва. Визначити план виробництва х=(х1,...,хn)'(xj - шукана кількість одиниць продукції Pj), який би при заданих...
-
Опорний розвязок(план) - невідємний базисний розв'язок. Базисні розвязки - це частинний розвязок, який знаходиться якщо надати всім вільним змінним...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Система ... називається системою обмежень, або системою умов задачі. Вона описує внутрішні технологічні та економічні процеси функціонування й розвитку...
-
Розв'язання систем рівнянь, Порядок виконання роботи - Вивчення математичного пакету MathСad
Матриця математичний пакет арифметичний Для розв'язання системи рівнянь з кількома невідомими треба задати початкові наближення для кожної змінної. Далі...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Перед пошуком розв'язку задачі зробимо деякі перетворення в моделі. Для перетворимо рівняння (2.2) і отримаємо: Отримаємо: Тепер підставимо отриманий...
-
Методи розв'язування стохастичних задач поділяють на дві групи -- прямі та непрямі. Прямі методи використовують для розв'язування задач стохастичного...
-
Розрахуємо критерій Фішера [3]: (5.19) Де - обгрунтована складова дисперсії; - необгрунтована складова дисперсії; - загальна дисперсія; ,(5.20) Де -...
-
Умова задачі Бройлерне господарство птахівницької ферми налічує 20000 курчат, які вирощуються до 8-тижневого віку і після відповідної обробки надходять у...
-
Цілочисельне програмування - різновид лінійного програмування, в якому отримані значення повинні бути цілими числами. Особливий інтерес до задач...
-
Розглянемо емпіричну залежність y=a+bx (1). Так як це лінійна функція, то ні яких перетворень не буде і x та y лишаються без будь-яких перетворень...
-
Оптимізаційна задача - це емм задача мета якої полягає у знаходженні найкращого виконання сформованих обмежуючих умов. K1, k2,k3 - знаки нерівності A,...
-
ЗАКЛЮЧЕНИЕ - Основные методы математического моделирования для принятия управленческих решений
В данной работе поставленная цель была достигнута. Мы рассмотрели основные методы математического моделирования (принятия решений) на практике, а именно:...
-
Регрессия -- зависимость среднего значения какой-либо величины от некоторой другой величины или от нескольких величин. Задача регрессионного анализа...
-
Перехід від одного опорного плану до іншого - Методи розв'язування різних типів економічних задач
Перехід від одного опорного плану до іншого здійснюють зміною базису, тобто через виключення з поточного базису якоїсь змінної та включення замість неї...
-
Пусть имеется оптимизационная задача вида: (1) (2) (3) - задан(4) Здесь предполагается, что FJ(xJ,yJ)>0 для всех допустимых значений xJ,yJ. В этом случае...
-
Розробка математичного забезпечення інформаційної системи Характеристика моделей і методів рішення економічної задачі Фінансовий аналіз здійснюється за...
-
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей
Решение смешанной задачи для уравнения теплопроводности методом конечных разностей 1. Цель работы Ознакомление с методами решения смешанных задач для...
Графічний метод для задач ЛП n-вимірного простору при - Розв'язання задач математичного програмування