Joomla Software solutions Template

Payday loan

ВЪПРОС No. 7

ОПТИМИЗАЦИОННИ МЕТОДИ. ЛИНЕЙНО ПРОГРАМИРАНЕ

Структура на оптимизационни задачи – това не са вероятностни задачи:

1) Т.е. в този случай задачите са детерминирани  при избор на определена стратегия се получава точно определен резултат (предварително известен при даден начин на действие)

2) Знаем резултата от приложението на единична интензивност на определен начин на действие

3) Винаги съществуват ограничения, които влияят върху интензивността на стратегиите

4) Субектът, който взема решение търси каква да бъде интензивноста на стратегията.

Търсим тази интензивност, при която се получава максимален ефект, при определените ограничения.

5) Х₁, Х₂, ......... Х_j..... Х_n (интензивност при j-тата стратегия – интензивност на приложение на начините на действие).

6) b₁……..b_n – величина на ограниченията – разход на съответните ресурси

7) С₁, С₂..... С_n – ефекта, който се получава при единично приложение е на 1, 2.... n-ти начин на действие.

8) a_ij – количеството от i-ия ресурс, което се изразходва при j-ия начин на действие (единична интензивност), като ограниченията са известни:

за първия ресурс:

……………….

Да се определят значенията на X_j като:

Основна задача на линейното програмиране:

Допълващи променливи:  - неизползван ресурс от първия вид; X_n+2 – от втория;. X_n+m – от m-ия.

Към решението на една задача като се прибавят допълващите променливи, следователно се получава основната задача на линейното програмиране

Дадено предприятие може да произвежда 2 вида продукти. Печалбата по I-ия продукт с₁ = 5 лв.; с₂ = 10 лв.

Продукти             I              II             Ефективно работно време

Машини

М₁ 2 h          1,5                          1200

М₂ 1              2                             800

М₃ 0              3                             900

Х₁ Х₂

I и II – продължителност на времето за обработка на единица продукция на съответната машина.

при условия:

Ако се произвежда само Х₁ в първия случай (1) Х₁ = 600. Ако се произвежда само Х₂  Х₂ = 800. Всички възможни решения за първи случай (1) се намират по линията свързваща “600~800” или решенията са под тази линия.

Между двата продукта съществува взаимозаменяемост – това е основно понятие при оптимизацията.

За втория случай (2) Х₁ = 800; Х₂ = 400 и за (3) Х₂ = 300.

Областта на допустимите решения е многоъгълника АВСD0 на фигурата по-долу.

Оптималното решение е или върху една от страните или върху един от върховете !!!

Когато нищо не се произвежда се започва от началото на координатната система като се преминава през отделните върхове на оптималното решение, докато се намери оптимален резултат!

Оптималното решение е в т. В (200;300), тогава:

L = 5.200 + 10.300 = 4000

Основни етапи при обосновката на решенията:

1) Съставяне на математически модел

2) Изходни данни (ограничения, разходни коефициенти, печалба)

3) Приложение на метод на линейно програмиране

- симплекс метод;

- метод на решение на транспортната задача.

4) Интерпретация на решението:

- двойственост при линейното програмиране

- еластичност на ограниченията

- еластичност на коефициентите в целевата функция.

Задачи, чието решение се обосновава чрез линейно програмиране:

I. “Mix” (структурна, асортиментна задачи)

1. Задачи за оптимизация на производствената програма на една фирма

2. Задачи за смеси

3. Задачи за разкрояване на материали.

II. Разпределителни задачи:

1. За разпределение на машини или материали между различни видове производство или продукти.

2. Транспортна задача

3. Задача за назначението

Задачи за съставяне на производствена програма:

1) Една фирма произвежда n вида продукти; j – номер на продукта.

2) Производството на всеки един продукт последователно минава през m вида машини (i – индекс на операция  i = 1..m)

q₁, q₂, …. Q_m – брой на машините от m-тата група. За всяка една група машини е определен ефективен фонд от време за машина:

f₁, f₂, …. f_m – часове (f_i е един и същ за всяка една машина от дадената група).

F_i = q_i.f_i (часове)  общ ефективен фонд от време в i-тата група.

3) a_ij – продължителността на обработката на единица от j-ия продукт от i-тата група машини.

Пресметната е цената, по която ще се предлага един продукт:

4) c₁, c₂, …. c_n  цена (печалба) от j-ия продукт.

5) Х₁, Х₂....Х_j...Х_n – количеството, което трябва да се произведе.

6) L = c₁.X₁ + c₂.X₂ +…….+ c_n.X_n.  max

, като X_j

Допълваща променлива – свободното (неизползвано) време на i-тата група от машини  

F_i – наличността от i-ия материал

а_ij – разходна норма на i-ия материал за единиця от j-ия продукт.

Ограниченията може да са: от материали, от машини, от работна сила. Ако на пазара съществуват ограничения за максимален обем на произвежданата продукция (A_j­  максимално възможното произведено количество продукция от j-ия продукт ). Може да имаме и минимум (A_j – минимум на произведеното количество от j-ия продукт и . Може да имаме и 3ти вариант: .

Връзката между производствените мощности и производствената програма се осъществяват от a_ij.

Разширен модел за оптимизиране на производствената програма, при който е възможно да се повиши броя на машините.

Приемаме, че за период Т, предприятието прави инвестиции от j млн. лв.

При положение, че е известна цената на всяка машина се определя колко да се инвестира в машини т.е. вземаме решение колко машини (M_i) да закупим и колко продукти да продадем

, където:

f_i.M_i – ефективен фонд на новите машини

F_i­ - ефективен фонд на наличните машини.

Задачи за съставяне на смеси - в металургията; в нефтопреработването; в химията.

1. В металургията:

1.1. Готовия продукт се характеризира с m свойства (компактност, тегло, обем, заменяемост  b₁, b₂, .. b_m (примерно: )

1.2. n вида изходни суровини

а_ij – величината на j-ия химичен елемент в j-ия изходен продукт.

Цена на изходните материали – С

Какво количество от всеки материал да се вложи в изходния продукт.

Ограничения:

1) Колко максимум може да е състава на един ХЕ в състава от готовия продукт;

2) Минимумът съдържание на един ХЕ в състава на готовия продукт.

3) Строго фиксирано количество за даден ХЕ.



Ограничения за количеството: Х₁ + Х₂ +....+ Х_n = 1.

Ако количеството продукция е D тона, тогава:

Задачи за разкрояване на материали:

При разкрояването остават отпадъци:

1) Изходния материал може да е с линейна форма, която има определена дължина L (тръби).

2) Заготовки:

Пример: L₁ = 2,9 m; L₂ = 2,1 m; L₃ = 1,5 m (i вида заготовки са необходими b – брой необходими заготовки).

Съставяне на варианти за комбинирано разкрояване:

a_ij – брой заготовки от i-ия вид, които се получават при разкрояване на j-ия способ.

X_j – общо количество на получените заготовки по j-ия способ (колко продукта да се разкроят по j-ия вариант).

C_j – отпадък, при разкрояване по j-ия вариант.

Целта е:

Изходни материали с една форма могат да се разкрояват с други форми.

Максимизиране на комплекти от заготовки:

1) Брой заготовки – d;

2) Вид заготовки – i;

3) Пропорция между заготовките - ;

4) Имаме j варианта за комбинирано разкрояване

5) a_ij­ – броя на заготовките от i-ия вид, получен при разкрояване при j-ия вариант.

Искаме така да разпределим броя на заготовките, че по различни варианти да се получи максимизиране.

Z – общ брой на заготовките; L = Z₁+Z₂+….+Z_n  max.

При условия, че броя на заготовките разкроени по:

1) различни варианти ;

2) брой заготовки се намират в точно определена пропорция

Разпределителни задачи

I. Разпределяне на различните машини между различни видове производствени дейности:

1. j = 1..n  вида продукти, които трябва да се произвеждат

2. D₁, D₂, …. D_n – брой продукти от всеки вид

(D₁ = 500; D₂ = 100; D₃ = 600; M₁ = 3200 часа; М₂ = 2000 часа).

3. i = 1..n  видове машини

b₁, b₂….b_m – ефективен фонд на машините.

4. Продължителност на времето за производство на единица от всеки продукт на всяка група машини.

С_ij – разходи за производството на единица от j-ия продукт на i-тата група машини.

(целта е общите разходи да са минимални)

и  са условия.

В разпределителната задача съществуват 2 вида ограничения:

- входящи – ефективен фонд от време на машината;

- изходящи – количеството, което трябва да се произведе.

Целта е да е максимизира коефициента Z и 

Задача за назначенията

1) i = 1..n  видове работи (длъжности);

2) j = 1..m  кандидати за заемане на съответните длъжности, като всяка работа се изпълнява от един кандидат.

3) Способностите на различните кандидати са различни, следователно им се прави оценка, която е числова  C_ij – оценката на j-ия кандидат по отношение изпълнението на i-тата работа.

Целта е общия ефект да е максимален

;