Общият състав на проблема с линейното програмиране (ZLP)

1. Обща формулировка на проблема на линейното програмиране (ZLP). Примери ZLP.
2. Геометрична разтвор ZLP.
3. Основната теорема на линейното програмиране.
4. Метод Simplex за решаване на ZLP.
5. Двойнственост в линейното програмиране.

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

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

Чрез математическите проблемите на линейното програмиране включва случаи от практиката на промишлени-икономически ситуации, които в една или друга форма се интерпретират като проблемът за оптимално използване на ограничени ресурси.

Обхватът на задачите, които могат да бъдат решени с помощта на линейни методи за програмиране е достатъчно широк. Това, например:

· Проблемът на оптималното използване на ресурсите в планиране на производството;

· Проблемът на смеси (персонал продуктово планиране);

· Проблемът с намирането на оптималната комбинация от различни видове продукти за съхранение на склад (управление на инвентара или "раницата проблем");

· Транспортни задачи (анализ на разположението на завода, движението на стоки).

Линейно програмиране - най-развитата и широко използван секция на математическото програмиране (в допълнение, тук включват: число, динамична, нелинейна параметрично програмиране). Това се обяснява по следния начин:

· Математически модели на голям брой линейни икономически цели по отношение на необходимите променливи;

· Този тип задача сега е най-добре изучени. специални методи, чрез които тези цели са предназначени за това решен и съответната компютърна програма;

· Много проблеми линейното програмиране се решават, са били широко използвани;

· Някои от задачите, които са в първоначалната формулировка не са линейни, след редица допълнителни ограничения и предположения може да бъде линейна, или може да бъде намалена до такава форма, че те могат да бъдат решени чрез линейно програмиране.

Икономическо-математически модел на всяка линейното програмиране проблем включва: обективна функция. където оптималната стойност (максимален или минимален) е необходимо да се намери; ограничения като система линейни уравнения и неравенства; неотрицателност изисквания променливи.

Като цяло, моделът е написано, както следва:

В този случай Aij. двупосочно. CJ () - предварително константи.

Задачата е да се намери оптималните стойности на функцията (2.1) съгласно ограниченията (2.2) и (2.3).

Системни ограничения (2.2) се наричат ​​функционални ограничения проблеми и ограничения (2.3) - прав.

Vector отговаря на ограниченията (2.2) и (2.3) се нарича допустимо решение (план) на задачата на линейното програмиране. Планът, за които функцията (2.1) достига своя максимум (минимум) стойност nazyvaetsyaoptimalnym.

1. Проблемът на оптималното използване на ресурсите в планиране на производството.

Общият смисъл на този клас задачи е както следва.

Предприятието произвежда н различни продукти. За тяхното производство изисква м различни видове ресурси (суровини, материали, време и други подобни). Ресурси са ограничени, и техните резерви в периода на планиране са, съответно, В1. b2. ВМ конвенционални единици.

Има и технологични коефициенти Aij. които показват колко единици-тото ресурс е необходим за производството на единица продукт к-ти вид ().

Печалбите, получени от предприятие в прилагането на продукта на к-тип, е CJ.

В периода на планиране на стойностите на Aij. дву и Джей са постоянни.

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

Ето един прост пример за това е проблем на този клас.

Фирмата е специализирана в производството на стикове и игра на шах. Всеки стика носи на компанията печалба в размер на $ 2, и всеки комплект шах - в размер на $ 4. При производството на стика изисква четири часа до част А и два часа на мястото Б. шах набор произведени с разходи шест часа в областта А, шест часа в зона В и един час при сайта С достъпно част капацитет е 120 N -Hours дневно част Б - 72 часа и п сечение с - 10 N часа.

Колко клубове и комплекти шах да бъдат издадени от Дружеството на дневна база, за да получите максимална печалба?

Условия за този клас проблеми често се представя в табличен вид (вж. Таблица 2.1).

Таблица 2.1 - Първоначалните данни на проблема с използването на производствените ресурси

времето, необходимо за единица продукция, п-часова