Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник
Авто
Автоматизація
Архітектура
Астрономія
Аудит
Біологія
Будівництво
Бухгалтерія
Винахідництво
Виробництво
Військова справа
Генетика
Географія
Геологія
Господарство
Держава
Дім
Екологія
Економетрика
Економіка
Електроніка
Журналістика та ЗМІ
Зв'язок
Іноземні мови
Інформатика
Історія
Комп'ютери
Креслення
Кулінарія
Культура
Лексикологія
Література
Логіка
Маркетинг
Математика
Машинобудування
Медицина
Менеджмент
Метали і Зварювання
Механіка
Мистецтво
Музика
Населення
Освіта
Охорона безпеки життя
Охорона Праці
Педагогіка
Політика
Право
Програмування
Промисловість
Психологія
Радіо
Регилия
Соціологія
Спорт
Стандартизація
Технології
Торгівля
Туризм
Фізика
Фізіологія
Філософія
Фінанси
Хімія
Юриспунденкция






Симплек-метод у дробово-лінійному програмуванні.

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

Ця подібність із задачею лінійного програмування дозволяє розв’язувати задачі дробово-лінійного програмування звичайним симплекс-методом зі зміненим критерієм оптимальності.

РОЗГЛЯНЕМО ЗАДАЧУ.

Знайти максимум функціоналу:

(3.1)

при обмеженнях

(3.2)

(3.3)

(3.4)


РОЗВ’ЯЗУВАННЯ.

1. Складаємо початкову симплекс-таблицю (Табл.1).

При чому, для F передбачаємо два рядка: у верхньому записуємо коефіцієнт чисельника pj, в нижньому – знаменника qj.

Табл.1

-x1 -x2 -x m 1
y1= y2= - ym= a 11 a 12 a 1n a 21 a 22 a 2n a m1 a m2 a mn a 1 a 2 a m
F1= F2= -p1 -p2 -p m -q1 -q2 -q m 0 0

 


2. План записаний в Табл. 1 не може бути опорним, так як F2 = 0, отже серед bі є від’ємні обов’язково.

Кроками МЖВ відшукуємо опорний план, перетворюючи коефіцієнти стрічок .

Нехай в результаті k – кроків отримаэмо таблицю (Табл.2).

Табл.2

-y 1 -y 2 -y k -x s -x n 1
Х1= Х2= Хk= Yr= Ym= b 11 b 12 b 1k b 1s b 1n b 21 b 22 b 2k b 2s b 2n b k1 b k2 b kk b ks b kn b r1 b r2 b rk b rs b rn b m1 b m2 b mk b ms b mn b 1 b 2 b k b r b m
F1= F2= -p1‘ -p2‘ -pk -ps -pn -q1‘ -q2‘ -qk -qs -qn

 

Тут вже всі bj невід’ємні. В рядках F1 і F2 з’явились вільні члени P(k) і Q(k), Q(k) ¹ 0, .


 
 

Відшукання оптимального плану, тобто Fmaxполягає у переміщенні від отриманої опорної вершини до сусідньої вершини по ребру, яка розміщена найближче до оптимальної вершини (Рис.7).

 

Рис.7.


Аналітично це означає зробити крок МЖВ з деяким brs. Задача полягає в тому, щоб встановити правило вибору brs (розв’язуючого елементу). Нехай ми вибрали brs. В новій (k+1) - ій таблиці замість P(k) буде стояти число:

(3.4)

Аналогічно замість i Q(k) буде стояти число:

(3.5)

Значення функціоналу на (k+1)- му кроці:

.


Далі знаходимо:

(3.6)

Позначимо:

(3.7)

З цими позначеннями отримаємо:

(3.8)


Дослідимо вираз (3.8)

1. Щоб не відірватися від многогранника розв’язків, симплексне відношення повинно бути і найменшим із всіх можливих

Звідки слідує, що , так як по умові допустимості плану . Отже, завжди.


2. Q(i) завжди > 0, то Q(k)×Q(k+1) завжди > 0, тому знак F(k+1) F(k) залежить від знаку ds. Коли ds > 0, то F(k+1) F(k) < 0. Звідки F(k+1) < F(k) або F(k) > F(k+1).

Іншими словами, коли за розв’язуючий стовпчик взяти стовпчик з
ds > 0, то після кроку МЖВ функціонал зменшується, а при виборі розв’язуючого стовпчика з ds < 0, F(k) > F(k+1) – функціонал збільшується.

При ds = 0, F(k+1)=F(k) функціонал не змінюється.

Визначник ds служить критерієм для вибору brs.

 





Переглядів: 705

<== попередня сторінка | наступна сторінка ==>
Приклад економічної задачі та її математичне формулювання. | Алгоритм відшукання оптимального плану.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.004 сек.