Големина на текста:
Линейно програмиране (оптимиране)
OPERATION RESEARCH
1. Общи задачи на линейното програмиране – КМЛ е научен подход за вземане на
решения за управление на дадена система в условия на ограничения от технически,
икономически или друг характер върху система.Методите на КМЛ намират широко
приложение в производството, транспорта, здравеопазването и т.н.Някои от основните
дялове на тази научна област са:
1. математическо програмиране(оптимиране) – линейно,нелинейно,динамично и др.
2. теория на игрите – GAME TEORY
3. теория на решенията – DECISIONS TEORY
4. теория на масовото обслужване
5. теория на запасите
Основните задачи на КМЛ са свързани със създаване и решаване на модели, описващи
реални системи и проблеми.
Основните типове модели са математическите.Те могат да са : детерминистични – с
определяне на входни данни, и стохастични – вероятностни
Освен математическите се използват симулационни и евристични модели.
В частност от математическото програмиране ще изучим само линейното.
1. Обща задача на линейното програмиране
Най-характерния проблем, който решаваме е този за разпределение на ограничени
ресурси из между конкуриращите се за тях дейности по възможно най-
добрия(оптимален) начин.Думата програмиране е синоним на планиране.Илюстративен
пример : фирмата производител на прозорци и врати в 3 завода.В първия се призвеждат
PVC, във втория – дървени, а в третия се произвежда стъкло и се сглобява
продукта.Поради намалените разходи от продажба на готови продукти управлението
решава да преработи продуктовата линия.Някои от произведените продукти се спират
от производствто като при това 2 нови продукта с празен потенциал.Производството на
1вия продукт изисква опрделен капацитет от 1 и 3 завод, а 2рия от 2ри и 3ти завод.
Според маркетинговия отдел няма ограничения при потребителското търсене на
продуктите, т.е компанията може да продаде, колкото може да произведе.
2та продукта се конкурират за ограничения производствен капацитет на 3тия
завод.Задачата е да се определи какъв трябва да е темпа на производство на 2та типа
продукти за да се максимизира сумарната печалба от тях като се удовлетворят
ограниченията наложени от производствения капацитет, с който се разполага в 3те
завода.Всеки продукт се произвежда на партиди по 20бр. и темпа на производствто е
бр. партиди произведени за 1 седмица.За формулиране на задачата са събрани данни
относно : 1. брой изразходвани часове във всеки от 3те завода за 1 седмица(наличен
производствен капацитет);2. необходимия брой часове за производство на 1 партида от
всеки от продуктите във всеки от заводите; 3. печалба от 1 партида от всеки от новите
продукти(предположение, че печалбата от 1 партида не зависи от броя произведени
партиди)
Освен това, тъй като няма допълнителни разходи за стартиране на производството на
новите продукти може да се приеме, че печалбата от продажбите ще е равна на
печалбата от 1 партида по броя произведени партиди.
В определение на тези данни вземат участие различни категории от персонала на
фирмата: производствен отдел, маркетингов отдел, счетоводството.
Стойности :
Завод
Време за производствто на
1 партида
Свободен
произвдоствен
капацитет
1 продукт2 продукт
1104
20212
33218
Печалба
от
партида
3000лв.5000лв.
Съставяме математически модел:
Целта е да се максимизира сумарната печалба от 2та продукта
Z – сумарната печалба от 2та нови продукта
x
1
– брой произведени партиди от 1 продукт на седмица
x
2
– брой произведени партиди от 2 продукт на седмица
Z = 3*x
1
+ 5*x
2
-> max
печалба от 1 печалба от 2
продукт продукт
1*x
1
+ 0*x
2
<= 4
изразходван производствен
капацитет в 1 завод
0*x
1
+ 2*x
2
<= 12
3*x
1
+ 2*x
2
<= 18
Условията изразяват ограниченията да не се изразходват повече часове от наличните в
3те заводи.Предвид тези ограничения променливите х
1
и х
2
немогат да приемат
произволни стойности, а само такива, които ги удовлетворяват.Смисъла на
променливите, те немогат да приемат отрицателни стойности.Затова се налага и
условията:
x
1
>= 0
x
2
>= 0
Като се има в предвид разгледания пример, ще формулираме т.нар стандартна форма на
математически модел на задача на линейно програмиране.
Да се намерят стойностите на х
1
2
...х
n
,за които функцията (1) Z = C
1
x
1
+ C2x
2
+ … C
n
x
n
се максимизира и които удовлетворяват условията (2)
а
11
x
1
+ a
12
x
2
+ … + a
1n
x
n
<= b
1
a
21
x
1
+ a
22
x
2
+ … + a
2n
x
n
<= b
2
-----------------------------------------
Количество
за 1 партида
от 2 продукт
Количество
часове за 1
партида от 1
продукт
a
m1
x
1
+ a
m2
x
2
+ … + a
mn
x
m
<= b
mn
(3) x
1
>=0;…;x
n
>=0
xj>=0;j>=1,n
Функцията (1) се нарича целева функция (Z=..).Условията (2) са функционални
ограничителни условия.Условията (3) са за неотрицателност, тъй като (1) и левите
страни на (2) са линейни функции на променливите х
1
...х
n
.Програмирането се нарича
линейно.”х
1
...х
n
” изразяват неизвестния брой изпълнения на n конкуриращи се
дейности.Коефициентите C
j
,b
i
I a
ij
за стойноти i=1…m,j=1…n се наричат параметри на
модела и са известни.Коефициента Cj показва как се изменя целевата функция при
единично нарастване на променливата x
j
.Коефициента b
i
е количество от i-ти ресурси,
индекса на който показва номера на ресурса, с което се разполага и което подлежи на
разположение между дейностите.
Коефициента a
ij
се нарича разходни норми и показват количество от i-ти ресурс, което
се изразходва при еднократно изпълнение на j-та дейност.
Съвкупността от получените при решаване на задачата стойности на променливите
формират търсения план на действие, при който величината Z се максимизира.На тяхна
основа се взема управленско решение.
В действителност разгледаната форма на модела отразява всички възможни задачи на
линейно програмиране.Възможни са и следните варианти или комбинации от тях:
1. търси се минимума на целевата функция Z
2. някои от функционалните ограничения с условия са зададени като =
3. някои от ограниченителните условия са >=
4. някои от условията за неотрицателност не са наложени
При тези варианти смисъла на задачата обикновенно не е свързан с разпределяне на
ограничени ресурси.Независимо от смисъла на дадена задача е задачата на линейното
програмиране ако математическата й формулировка съответства на някоя от
изброените форми.
2. Геометрична интерпретация на общата задача на линейното програмиране
Задачата на линейното програмиране може да е изобразена графично в равнината при 2
променливи.Илюстрираме това чрез разгледания пример.
Z = 3x
1
+ 5x
2
-> max
(1) x
1
<= 4
(2) 2x
2
<= 12
(3) 3x
1
+ 2x
2
<= 18
x
1
>= 0
x
2
>= 0

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

За да разгледате всички страници от този документ натиснете тук.
Последно свалили материала:
ДАТА ИНФОРМАЦИЯ ЗА ПОТРЕБИТЕЛЯ
20 ное 2020 в 15:55 студентка на 26 години от София - УНСС, факулетет - Икономика на инфраструктурата, специалност - Икономика на търговията, випуск 2017
10 ное 2020 в 23:58 студент на 35 години от София - СУ "Св. Климент Охридски", факулетет - Геолого-географски факултет, специалност - регионална сигурност, випуск 2020
 
 
Онлайн тестове по Програмиране
Програмиране С++
изпитен тест по Програмиране за Студенти от 3 курс
Тестът включва въпроси върху указатели, програмиране С++, структури от данни. Всички въпроси са затворени и изискват само един верен отговор.
(Труден)
20
13
1
4 мин
02.10.2014
Програмиране и използване на компютрите
междинен тест по Програмиране за Неучащи от 1 клас
Тестът се състои от 21 въпроса върху кратка история на компютрите. Всички въпроси са затворени и изискват един верен отговор.
(Лесен)
21
11
1
3 мин
12.11.2014
» виж всички онлайн тестове по програмиране

Линейно програмиране

Материал № 494328, от 21 апр 2010
Свален: 172 пъти
Прегледан: 254 пъти
Качен от:
Предмет: Програмиране, Информатика, ИТ
Тип: Общ материал
Брой страници: 12
Брой думи: 2,646
Брой символи: 15,233

Потърси помощ за своята домашна:

Имаш домашна за "Линейно програмиране"?
Намери бързо решение, с помощтта на потребители на Pomagalo.com:

Намери частен учител

Виторио Белоречки
преподава по Програмиране
в град София
с опит от  4 години
268 32

Нина Урумова
преподава по Програмиране
в град Варна
с опит от  15 години
308 80

виж още преподаватели...
Последно видяха материала