Поиск по базе сайта:
Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування» icon

Методичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»




НазваМетодичні вказівки до виконання лабораторних робіт із дисципліни «Економіко-математичне моделювання» Розділ 1: «Математичне програмування»
Сторінка3/8
Дата конвертації02.08.2013
Розмір1.22 Mb.
ТипМетодичні вказівки
1   2   3   4   5   6   7   8

Розв’язання.

Необхідно привести задачу до канонічного вигляду:



Базисні змінні виражаються через неосновні. У якості базисних змінних обираються додаткові змінні (одиничні вектори) .

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

.

Шуканий початковий план має вигляд

.

Початковий опорний план задачі знаходиться безпосередньо тільки при невід’ємних правих частинах системи обмежень. Тому обмеження з від’ємною правою частиною повинні бути переписані після множення на (-1).

Примітка. Така операція змінює знак нерівності.


^ Перший крок: базисні змінні: ;

неосновні змінні: .




У прикладі, що розглядається, базисний розв’язок ,.

Функція вже виражена через неосновні змінні і оскільки коефіцієнти перед х1 та х2 мають знак «+» , то цю функцію можна збільшити, тобто Х1 не є оптимальним розв’язком.

Збільшення функції рівносильне переходу до іншого опорного (плану) розв’язку.

Функцію можна збільшити за рахунок збільшення як х1, так і х2. Змінна х2 має більший коефіцієнт, тому обирається для введення до базису. Зростання змінної х2 обмежується умовою невід’ємності змінних, а саме (покладаємо, що х1=0):





Рівняння, де досягається найбільше можливе значення змінної, яка переходить до основних, називається розв’язувальним. У даному випадку – третє рівняння.

Знаходиться другий опорний розв’язок, у якому х2 буде вже базисною змінною, а х5 перейде в неосновні.


Другий крок: базисні змінні: ;

неосновні змінні: .

Необхідно виразити базисні змінні через неосновні, починаючи з розв’язувального рівняння.



Другий базисний розв’язок .

Функція цілі, виражена через неосновні змінні, має вигляд



– це значення, яке не є оптимальним, оскільки F(x) можна збільшити за рахунок х1. Для знаходження розв’язувального рівняння необхідно покласти .

Тоді .

Друге рівняння є розв’язувальним, а значить х3 перейде в неосновні змінні.

Третій крок: базисні змінні: ;

неосновні змінні: .







Значення функції можна збільшити за рахунок змінної х5, яка має коефіцієнт +3, отже змінна х5 переходить до основних.

Для знаходження розв’язувального рівняння необхідно покласти х3=0.

- третє рівняння є розв’язувальним.

Четвертий крок: базисні змінні: ;

неосновні змінні: .





Коефіцієнти при неосновних змінних цільової функції є від’ємними, тому функцію не можна збільшити за рахунок цих змінних, таким чином розв’язок є оптимальним.

^ Критерій оптимальності при знаходженні максимуму лінійної функції: якщо у виразі лінійної цільової функції через неосновні змінні відсутні додатні коефіцієнти при неосновних змінних, то розв’язок є оптимальним.

^ Знаходження мінімуму цільової функції

Для знаходження мінімуму цільової функції можливими є два шляхи:

  1. знаходження максимуму функції , в результаті чого (оптимальний максимум потрібно взяти з протилежним знаком);

  2. модифікувати симплекс-метод, тобто на кожному кроці зменшувати цільову функцію за рахунок тієї неосновної змінної, яка входить до цільової функціії з від’ємним коефіцієнтом.

^ Критерій оптимальності при знаходженні мінімуму цільової функції: якщо у виразі цільової функції через неосновні змінні відсутні від’ємні коефіцієнти при неосновних змінних, то розв’язок є оптимальним.


^ Завдання до лабораторної роботи

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


№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = –x1 – 2x2  min





Z = x1 + 3x2  max





Z = x1 + x2  max





Z = –x1 – x2  min





Z = 2x1 + 2x2  max





Z = x1 + 2x2  max






№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = 2x1 – x2 + 3x3 – 2x4   max





Z = 2x1 + x3 + x4 – x5  min





Z = x1 + x2 – x3 – 4x4  max





Z = 6x1–7x2–6x3+10x5–7x6  max





Z = x1 – x2 – 2x3 + 2x4  min





Z = x1 – x2 + x3 + x4 – x5  min





Z = 2x1 + x2 + 2x3 + 3x4  max





Z = 3x1 – x3 + x4  max






Z = x1 – x2 – 3x3  min





Z = x1 + 2x2  max






№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



Z = 2x1 + 6x2  max





Z = -x1 - x2  min





Z = 2x1 – 3x2  min





Z = -5x1 - 5x2  min





Лабораторна робота № 3

^ РОЗВ’ЯЗАННЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

З ВИКОРИСТАННЯМ СИМПЛЕКСНИХ ТАБЛИЦЬ


Мета роботи – навчитися розв’язувати задачі лінійного програмування з використанням симплексних таблиць.

У результаті виконання роботи студент повинен:

ЗНАТИ правила побудови опорних планів;

УМІТИ здійснювати перехід під одного плану до іншого;

МАТИ УЯВЛЕННЯ про виконання критеріїв оптимальності.


Алгоритм симплекс-методу дозволяє знайти оптимальний розв’язок, перебираючи допустимі базисні розв’язки, причому не всі підряд, а намагається на кожному кроці знайти допустимий базисний розв’язок, що покращує значення цільової функції.

Алгоритм заповнення симплексної таблиці:

1 Після введення додаткових змінних для перетворення нерівностей в рівняння, систему рівнянь і цільову функцію записують у такому вигляді:


а11х + а12х2 + ...+ а1пхп п+1 = b1;

а21х1 + а22х2 + ...+а2пхп п+2 = b2;



am1x1 + аm2х2 + ...+ атпхп п+m = bm;

Fc1x1 с2х2 – ... – спхп = 0.

Дана система називається розширеною системою.

Припускається, що всі додаткові змінні мають такий самий знак, що і вільні члени (у протилежному випадку застосовують М-метод).

2 Вихідну розширену систему необхідно занести до першої симплексної таблиці.


^ Базисні змінні

Вільні члени

x1

x2



хn

Оцінююче відношення

xn+1



















xn+2







































xn+ m



















F




















3 Перевірити виконання критерію оптимальності (якщо розглядається задача знаходження максимуму, то критерієм оптимальності є присутність в останньому рядку від’ємних коефіцієнтів; у разі, якщо таких немає – розв’язок є оптимальним).


4 Якщо критерій оптимальності не виконано, то найбільший за модулем від’ємний коефіцієнт в останньому рядку визначає розв’язувальний стовпчик s. Оцінююче відношення складається за такими правилами:

    1. ∞, якщо bi, ais є різними за знаком;

    2. ∞, якщо bi=0, ais<0;

    3. ∞, якщо ais =0;

    4. 0, якщо bi=0, ais>0;

    5. │bi /ais│, якщо bi, ais є однакові за знаком.

Розв’язувальний рядок визначається за мінімальним значенням відношення │bi /ais│.

Якщо скінченного мінімуму немає, то задача не має скінченного оптимуму, тобто Fmax=∞.

Якщо ж указаний мінімум є скінченим, то обирається рядок q, на якому він досягається (будь-який, якщо їх декілька). Цей рядок називається розв’язувальним. На перетині розв’язувального рядка і стовпчика знаходиться розв’язувальний елемент aqs.


5 Перехід до нової симплекс-таблиці здійснюється за наступним правилом. Позначений рядок q ділиться на aqs і записується на тому самому місці:




До кожного з інших рядків таблиці додається рядок, одержаний на місці відміченого рядка, помножений на таке число, щоб елемент, який стоїть у відміченому стовпчику, перетворився на нуль. Одержаний рядок записується на місці попереднього, тобто елементи будь-якого іншого рядка перераховуються за формулою:

.

Значення базисних змінних (вільних членів) нового опорного плану обчислюються за формулами:




Далі здійснюється перехід до пункту 3 алгоритму.


^ Приклад

Знайти максимальне значення функції.

F(х)=2х1+ 3х2 → max


х1 + 3х2 ≤ 18;

1 + х2 ≤ 16;

х2 ≤ 5;

1 ≤ 21;

х1≥0; х2 ≥0.


Розв’язання

х1 + 3х2 + х3 = 18

1 2 + х4 = 16

х2 + х5 = 5

1 + х6 = 21

F – 2х1 – 3х2=0


^ Базисні змінні

Вільні члени

x1

x2

x3

x4

x5

х6

Оцінююче відношення




x3

18

1

3

1

0

0

0

18/3




x4

16

2

1

0

1

0

0

16/1




x5

5

0

1

0

0

1

0

5/1

розв’язувальний рядок,

що має min оцінююче відношення

x6

21

3

0

0

0

0

1

21/0=∞




F

0

-2

-3

0

0

0

0
















розв’язувальний стовпчик,

що має min значення в останньому рядку




















Таким чином змінна x5 виводиться з базису, її замінює x2. На місці розв’язувального рядка записується новий рядок, з такими самими значеннями, адже розв’язувальний елемент дорівнює 1.

Розв’язувальний рядок множиться:

  • на -3 і додається до 1-ого рядка;

  • на -1 і додається до 2-ого рядка;

  • на 0 і додається до 4-ого рядка;

  • на 3 і додається до 5-ого рядка (F).




^ Базисні змінні

Вільні члени

x1

x2

x3

x4

x5

х6

Оцінююче відношення




x3

3

1

0

1

0

-3

0

3/1




x4

11

2

0

0

1

-1

0

11/2




x2

5

0

1

0

0

1

0

5/0=∞




x6

21

3

0

0

0

0

1

21/3




F

15

-2

0

0

0

3

0










^ Базисні змінні

Вільні члени

x1

x2

x3

x4

x5

х6

Оцінююче відношення




х1

3

1

0

1

0

-3

0

3/-3=∞




x4

5

0

0

-2

1

5

0

5/5




x2

5

0

1

0

0

1

0

5/1




x6

12

0

0

-3

0

9

1

12/9




F

21

0

0

2

0

-3

0










^ Базисні змінні

Вільні члени

x1

x2

x3

x4

x5

х6

Оцінююче відношення




х1

6

1

0

-1/5

3/5

0

0







x5

1

0

0

-2/5

1/5

1

0







x2

4

0

1

2/5

-1/5

0

0







x6

3

0

0

3/5

-9/5

0

1







F

24

0

0

4/5

3/5

0

0








Критерій оптимальності виконано, оскільки останній рядок не містить від’ємних коефіцієнтів. Таким чином, максимального значення F(х)=24 функція набуває при значенні плану Х=(6;4;0;0;1;3).

Можна зробити висновок, що послідовність базисних розв’язків складається з того, що ітераційний процес симплекс-методу розпочинається в кутовій точці (0;0), а потім проходить через кутові точки до оптимуму. Ітерації відповідають суміжним крайнім точкам границі області допустимих розв’язків.

1   2   3   4   5   6   7   8



Схожі:




База даних захищена авторським правом ©lib.exdat.com
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації