Основни понятия на линейното програмиране

Те са предназначени за специфична цел методите, чрез които се решават тези проблеми и съответните практики за решаването им на компютър;

много линейното програмиране проблем е решен, сега се оказа голямо практическо приложение в националната икономика;

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

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

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

РЕЗЮМЕ линейното програмиране е да се намери най-големите или най-малките стойности на точките на функция в определен набор от ограничения, наложени на случая и определяне на ограничения на системата. което обикновено е безкраен брой решения. Всеки набор от променливи (аргументи функционират F), които отговарят на системата на ограничения се нарича осъществим план на линейното програмиране проблем. Функция F. високо или ниско бъде определен, той нарича целева функция на проблема. Приемливо план, на която максимална или минимална на функцията F. Тя се нарича оптимална програма на проблема.

Системата на ограниченията, който определя набор от планове, продиктувано от производствени условия. Задачата на линейното програмиране (ZLP) е изборът на множество допустими планове най-благоприятни (оптимални).

В общата формулировка линейното програмиране проблем, както следва:

Има някои променливи х = (х1. X2. ... Xn) и функцията на тези променливи е (х) = F (х1. X2. ... Xn). който се нарича целева функция. Проблемът: намерите екстремум (максимална или минимална) целевата функция е (х) при условие, че променливите х принадлежат към определен домейн Г.

В зависимост от формата на F функция (х) и G и отличават области на математически програмиране: квадратичен програмиране, изпъкнала програмиране, число програмиране и т.н. Линейно програмиране се характеризира с факта, че
а) F функцията (х) е линейна функция на X1 променливите. x2. ... хп
б) G се определя от система за линейни уравнения и неравенства.

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

• максимален или минимален на обективната функция (критерий оптималност);
• система от ограничения под формата на линейни уравнения и неравенства;
• неотрицателност изисквания променливи.

В други случаи, може да има проблеми с голям брой променливи, в които ограниченията, неравенство може да се качват и равенство. Poytomu в най-общата форма на задачата на линейното програмиране е формулиран, както следва:

За да канонична форма, можете да конвертирате всеки линейното програмиране проблем.

Обикновено донесе ZLP в канонична форма:

1. Ако първоначалният проблем на ограничение (например, първият) се неравенство, тя се превръща в равенство, въвеждането на лявото крило неотрицателно променлива, отколкото когато неравенството «≤» въведена допълнителна неотрицателна променлива със знак "+"; в случаите на "≥" неравенство - със знак "-"

Тогава (2.10) може да се запише като:

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

2. Ако първоначалният проблем на една променлива не е предмет на условието за не-негативизъм, а след това се заменя (в целевата функция и всички ограничения) разликата между неотрицателни променливи

л - безплатен Index

3. Ако ограниченията на дясната страна е отрицателен, тогава се размножават това ограничение от (-1)

4. И накрая, ако първоначалният проблем е задача най-малко, въвеждането на нова цел функция F1 = -F ние трансформираме проблем на свеждането до минимум на функция F в F1 за максимизиране функция.

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

Стандартната форма на линейното програмиране проблем е предизвикателство за максимум (минимум) на линейна функция цел. ограничаването му система включва някакъв вид линейни неравенства " <= » или «>= ". Всички променливи на проблема не са отрицателни.

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

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