Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Приклад.






-24x1+2x3+6x4®max

-3x1+x2+x3+3x4=4 y1

2x1+2x2+x3+x4=6 y2

x1, …, x4³ 0

4y1+6y2® min A: y1+2y2=0

-3y1+2y2³ -24 y1+y2 = 2

y1+2y2³ 0

y1+y2³ 2 Y = (4; -2)

 
 

3y1+y2³ 6 Z = 4

На підставі теореми 2: Вирішимо дану систему рівнянь методом

(-3y1+2y2+24)x1=0 підбору. Y=(4; -2)

(y1+2y2)x2=0

(y1+y2-2)x3=0

(3y1+y2-6)x4=0

Підставивши в систему знайдені значення Y, отримаємо:

X = (0, 2, 2, 0)

Z = 4.

Доцільність використовування ПЗ:

Використовується з метою зниження розмірності задачі.

Зменшення кількості змінних.

Використовується в інших задачах (Подвійний симплекс метод).

 

ПОДВІЙНИЙ СИМПЛЕКС МЕТОД

 

Даний метод оснований на постійному поліпшенні неприпустимості рішень.

Якщо в ПРЗ симплекс методу основана на постійному поліпшенні значень ЦФ:

k+1 ³ k

0 0, то в ПЗ Xбазисне: Xn Eх B; Xn £ 0.

Мета: Xn®max.

 

ВІДЗНАКА ПОДВІЙНОГО симплекс методу (ПСМ) від ПРЯМОГО (ПРСМ)

 

Вибір направляючого елементу (спочатку визначається рядок:

min(Xi0 ç Xi0 < 0), а потім стовпець: ;

Канонічна форма ПСМ повинна мати рівність та одиничний базис.

Для приведення до канонічного виду необхідно розрахувати псевдоплан. Псевдоплан – це нова модель, що містить в собі одиничний базис (сопряжённый базис) та неприпустиме опорне рішення.

Примітка: існують типові моделі, для яких псевдоплан можна записати відразу (наприклад, Задача змінно-добового планування).

Якщо в ПРСМ повинна бути хоча б одна Ітерація, то в ПСМ рішення може бути отримане відразу після перерахунку псевдоплану.

Всі останні Подвійні симплекс-перетворення аналогічні ПРСМ.

 

Приклад.

 

4x1+3x2+10x3+5x4®min 3 * 10 розмірність симплекс задачі.

3x1+2x2-x3+5x4³ 8 3 * 7 розмірність подвійної СЗ.

x2-3x3+6x4³ 4

2x1+x3-x4³ 0

x1, …, x4³ 0

необхідно привести до max та до рівностей (канонічний вигляд):

-4x1-3x2-10x3-5x4®max

3x1+2x2-x3+5x4-x5=8 y1

-x2-3x3+6x4-x6=4 y2

2x1+x3-x4-x7=0 y3

 

формуємо подвійну модель, щоб вибрати “сопряжённый” базис.

 

8y1+4y2®min A0

3y1+2y3³ -4 A1

2y1-y2³ -3 A2

-y1-3y2+y3³ -10 A3

5y1+6y2-y3³ -5 A4

-y1> 0 A5

-y2> 0 A6

-y3> 0 A7

3) На підставі рядків ПЗ будуємо подвійні вектори А0, А1, А2, А3, А4, А5, А6, А7.

                               
               


8 3 2 -1

А0 = 4 А1 = 0 А2 = -1 А3 = -3

0 2 0 1

                               
               


5 -1 0 0

А4 = 6 А5 = 0 А6 = -1 А7 = 0

-1 0 0 -1

 

 

4) Вибір “сопряжённого” базису розміром m. Для цього необхідно:

свавільно вибрати m рівнянь (в даній задачі вибираємо рівняння (5, 6, 7), тут =(0, 0, 0));

розв’язуємо цю систему з m рівнянь;

підставляємо рішення в кожне з залишених (n-m) обмежень(в даній задачі це рівняння(2, 3, 4, 5)) та перевіряємо, чи задовольняє “сопряжённый” базис.

Якщо так, то відбувається розрахунок симплекс таблиці, тобто псевдоплан.

Якщо ж ні, то даний варіант не задовольняє, тому слід перейти до наступного

“сопряжённого ”базису.

Отже маємо складену симплекс таблицю:

      -4 -3 -10 -5      
  Bx A0 A1 A2 A3 A4 A5 A6 A7
  X5 -8 -3 -2   -5      
  X6         -6      
  X7   -2   -1        
                 
            ­      

 

A0 = A5X50 + A6X60 + A7X70

 

8 = -1x50 + 0x60 + 0x70

4 = 0x50 - 1x60 + 0x70

0 = 0x50 + 0x60 – 1x70

Xb = (-8; -4; 0).

 

Наступні розрахунки утворюються аналогічним чином.

 

Класифікація методів неперервного лінійного програмування

Симплекс метод використовується коли: ЦФ®max, а обмеження £ 0.

Симплекс метод (М-задача): обмеження ³ 0, = 0.

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

цільова функція®min, а всі обмеження > 0 (задача змінно-добового планування).

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

 

 

СПЕЦІАЛЬНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ

 

Задача призначення.

- задача про розподілення обладнання

Потрібно розподілити 5 екскаваторів між 4 кар’єрами з метою максимізації виробітки.

  K1 K2 K3 K4
    -   -
        -
         
         
    - -  

5 5

5 -100 7 -100 0

j = 1, M 7 8 8 -100 0

4 4 12 10 0

I = 1, N 8 7 10 11 0

10 -100 -100 14 0

Xij ³ 0;

 

 

Для приведення задачі до закритого вигляду, необхідно ввести (додати) фіктивне обладнання.

Задача про розклад.

Для кожної пари вирішується задача призначення потоку групи в аудиторії.

Критерієм є вмісткість аудиторії, розвантаження сходів(мінімізація хвилин переходу).

Cij-хвилини переходу; і - номер групи; j-аудиторія.

j=1, M; і=1, N;

3)Розподілення користувачем в класі ЕОМ.

Задана кількість користувачів та кількість комп’ютерів. Кожен користувач вирішує свою задачу за окремою ЕОМ. Необхідно розподілити користувачів

по критерію мінімума.

 

4)Транспортна задача.


 

 
 

Склад Споживач

 

A B

 

- вміщення матеріалів на складі;

- заявка.

Сij - витрати

і=1, M; j=1, N;

 

5) Задача планування будівельного майданчика.

 






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.