UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваСуть симплекс-методу (реферат)
АвторPetya
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось4229
Скачало503
Опис
ЗАКАЧКА
Замовити оригінальну роботу

РЕФЕРАТ

 

на тему:

 

Суть симплекс-методу

 

ПЛАН

 

1. Поняття симлекс-методу, його місце у розв'язуванні задач

 

лінійного програмування

 

2. Поняття двоїстого симплекс-методу, його особливості

 

Список використаної літератури

 

1. Поняття симлекс-методу, його місце у розв'язуванні задач

 

лінійного програмування

 

Нехай потрібно знайти максимум функції

 

Z(x1, х2) = 3х1 + 2,5х2

 

на множині ?, що описується системою нерівностей. Значення функції Z(x1,

х2) = 3х1 + 2,5х2 в деякій точці з координатами х1, х2 також можна

сприймати як відхилення цієї точки від прямої Z(x1, х2) = 3х1 + 2,5х2 =

0. Тому чим більше точка відхиляється від прямої Z(x1, х2) = О, тим

більше значення має в цій точці функція Z(x1, х2). Крім того, точки

будь-якої прямої, паралельної прямій Z(x1, х2) = 0, однаково відхилені

від прямої Z(x1, х2) = 0. Отже, точка, в якій функція Z(x1, х2) досягає

найбільшого значення, повинна бути точкою області ?, яка лежатиме на

прямій, що має з ? спільні точки і відхилена від прямої Z(x1, х2) = О

найбільше. Таким чином, шукана точка може лежати лише на межі області ?,

тобто належати деяким прямим, що обмежують область ? (мал. 1, 2).

Відхилення такої точки від кожної з межових прямих, яким вона належить,

очевидно, дорівнює нулю.

 

 

Мал. 1 Мал. 2

 

Допустимий розв'язок, в якому функція Z досягає найбільшого значення,

називатимемо оптимальним розв'язком. Точку, що відповідає оптимальному

розв'язку, називатимемо оптимальною точкою. Якщо оптимальна точка існує

і єдина (на мал. 1 — точка M2), то це — деяка вершина многокутника ?. А

якщо оптимальних точок безліч (мал. 2), то до їх множини належать і

деякі вершини многокутника ? (на мал. 2 — точки M1* i М2*). Тому для

знаходження оптимальної точки достатньо розглядати лише вершини

многокутника ?.

 

Отже, з геометричного погляду нашу задачу можна сформулювати так: серед

вершин многокутника ? знайти таку, в якій би функція Z(x1, x2) досягла

найбільшого значення.

 

Симплекс-метод якраз і дає можливість знайти спочатку якусь вершину

многокутника ?, а потім від неї перейти до тієї, в якій значення функції

Z не менше, ніж у попередній.

 

Перейдемо тепер до загального випадку. Нехай потрібно знайти максимум

функції

 

Z(x) = (p, x) = p1x1 + p2x2 + ... + рnхn (1)

 

(або, що те саме, мінімум функції Z1(x) = —Z(x)) на множині ?, що

визначається системою лінійних нерівностей

 

?i(x) = (ai, x) + bi = аi1x1 + ai2x2 + ... + аinхn + bi ? О (i=1, 2,

..., m). (2)

 

Запишемо дані нашої задачі у вигляді таблиці.

 

Таблиця 1

 

  x1 x2 ... xn 1

 

? 1 a11 a12 ... a1n b1

 

?2 a21 a22 ... a2n b2

 

... ... ... ... ... ...

 

?m am1 am2 ... amn bm

 

Z p1 p2 ... pm 0

 

Не порушуючи загальності міркувань, припустимо, що ранг матриці (aij) (і

= 1, m; j = 1, n) дорівнює n. Знайдемо спочатку якусь допустиму вершину

множини розв'язків ?. Нехай через n кроків жорданових виключень матимемо

таблицю:

 

Таблиця 2

 

Z(n)

 

Нехай вершина ?1 = 0, ?2 = 0, ..., ?n = 0 допустима, тобто b(n)n+1 ? 0,

..., b(n)m ? 0. Якщо при цьому всі коефіцієнти в Z-рядку недодатні,

тобто р(n)1 ? 0, р(n)2 ? 0, ..., р(n)n ? 0, то в вершині ?1 = 0, ?2 = 0,

-----> Page:

0 [1] [2] [3]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ