• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

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

(3.1)

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

(3.2)

(3.3)

(3.4)

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

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

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

Табл.1

2. План записаний в Табл. 1 не може бути опорним, так як F₂ = 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

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

Рис.7.

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

(3.4)

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

(3.5)

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

.

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

(3.6)

Позначимо:

(3.7)

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

(3.8)

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

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

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

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

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

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

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

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