Короткі теоретичні відомості. Тема. Розв´язання задач лінійного програмування

Практичне заняття № 1-2

Тема. Розв´язання задач лінійного програмування

Мета: навчитися методам розв´язання задач лінійного програмування.

1. Загальна задача лінійного програмування (З З Л П)

З З Л П зображується у вигляді:

max (min) (1)

а₁₁X₁ + а₁₂X₂ + …... + а_1nX_n = b₁

а₂₁X₁ + а₂₂X₂ + …... + а_2nX_n = b₂ (2)

а_m1X₁ + а_m2X₂ + …... + а_mnX_n = b_m

X₁ ≥ 0; X₂ ≥ 0; …..., X_n ≥ 0 (3)

де a_ij, b_i, C_j - задані постійні величини, (i=1;..m, j=1;..n).

2. Основні визначення З З Л П.

Визначення 1. Планом чи припустимим розв´язком З.З.Л.П. називається =(X₁,...X_n), що задовольняє (2-3).

Визначення 2. План називається опорним, якщо вектори , що входять у розкладання (2) з позитивними X_j (X_j>0) лінійно незалежні.

Так як вектори m-мірні, то в опорному плані число його компонент більших нуля, не може перевищувати m.

Визначення 3. Опорний план * не вироджений, якщо він містить m позитивних компонентів, якщо меньш m позитивних компонентів, то * вироджений.

Визначення 4. Оптимальним планом З З Л П ⁰ називається план, що доставляє мінімум функції мети Z.

3. Вимоги до З З Л П для можливості її розв´язання симплексом-методом.

З вищевикладеного випливає, що застосування симплекса-методу вимагає наявності початкового опорного плану З З Л П. За канонічної форми зображення З З Л П з обмежень задачі легко одержати такий опорний план. Канонічна форма З З Л П задовольняє трьом вимогам:

1) обмеження – у виді рівностей;

2) праві частини b_i≥0;

3) кожне обмеження містить базисну перемінну. Загальний вид З З Л П у канонічній формі:

(4)

.

Дата добавления: 2015-05-23