1. лінійне програмування icon

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



Название1. лінійне програмування
страница1/5
Дата конвертации12.12.2012
Размер0.67 Mb.
ТипДокументы
  1   2   3   4   5
1. /Оптимизация 1.DOC1. лінійне програмування

1. ЛІНІЙНЕ ПРОГРАМУВАННЯ



1.1. Постановка задач лінійного програмування і дослідження їх структури


Більшість задач, що розв‘язуються методами дослідження операцій, можна сформулювати так:

максимізувати f (x1, x2, …, xn) (1.1.1)


при обмеженнях:

g1(x1, x2, …, xn)  b1;

. . . . . . . . (1.1.2)

gm(x1, x2, …, xn) bm;

де f (x1, x2, …, xn) – цільова функція, або критерій ефективності (наприклад, прибуток від виробництва якихось видів продукції, вартість перевезень тощо) ; х={x1,…, xn}- змінні параметри ; g1(х),…, gm(х) -функції, що визначають обмеження на наявні ресурси.

Форма запису задачі ЛП. Задачу лілійного програмування можна записати так:

максимізувати (1.1.3)

при обмеженнях

a11x1 + a12x2 + … + a1nxn  b1 ;

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

am1x1 + am2x2 + … + amnxn  bm ; (1.1.4)

x1  0, x2  0, …, xn  0. (1.1.5)

Обмеження (1.1.5) називають умовами невід‘емності змінних.

Якщо всі обмеження задачі ЛП мають вигляд строгих рівностей

a11x1 + a12x2 + … + a1nxn = b1 ;

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

am1x1 + am2x2 + … + amnxn = bm . (1.1.6)

то форму запису називають канонічною.

У матричній формі задача ЛП записується так:

максимізувати cTx (1.1.
7)

при обмеженнях

Ax b ;

х 0, (1.1.8)

де А – матриця обмежень розміром (т x п); b(m1) - вектор-стовпець довільних членів; x(n1) - вектор змінних; сT=[c1, c2,…, cn] - вектор (рядок) коефіцієнтів ц. ф.

Допустимою множиною розв‘язків задачі (1.1.3) -(1.1.5) зветься множина R (х) усіх векторів x, що задовольняють умови (1.1.4) і (1.1.5).

Множина R (х) являє собою опуклу многогранну множину або опуклий многогранник.

Розв‘язок x0 є оптимальним, якщо він задовольняє умові сTx0 сTx,

для всіх хR (х)

Оскільки пошук min f(х) еквівалентний пошук mах[—f(х)], то задачу ЛП завжди можна звести до еквівалентної задачі максимізації.

Розширена форма задачі ЛП. Для розв‘язання задачі ЛП треба переходити від обмежень – нерівностей до обмежень у формі рівнянь. Для цього у кожну нерівність вводять по одній вільній змінній xn+10, xn+20,…,xn+m0, щоб перетворити її в рівність. У такому вигляді задачу ЛП називають розширеною і записують так:

максимізувати f(x1, x2, …, xn)=c1x1+c2x2+…+cnxn+0xn+…+0xn+m . (1.1.9)

при обмеженнях

a11x1 + a12x2 + … + a1nxn + 1xn+1 + 0xn+2 + … +0xn+m= b1 ;

. . . . . . . . . . . . . . . . . . . . . . . (1.1.10)

am1x1 + am2x2 + … + amnxn + 1xn+1 + 0xn+2 +…+0xn+m= bm ;

У матричній формі ця задача має такий вигляд:

максимізувати cTx (1.1.11)

при обмеженнях

Am n x1 + Emmx2 =b; (1.1.12)

де


Допустимі базисні розв‘язки

  1   2   3   4   5




Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов