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

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




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

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

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

№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



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






№ варіанта

Умови ЗЛП

№ варіанта

Умови ЗЛП



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




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

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

З ВИКОРИСТАННЯМ МЕТОДУ ШТУЧНОГО БАЗИСУ (М-МЕТОДУ)


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

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

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

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

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


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

Якщо систему обмежень вихідної задачі можна привести до вигляду АХ≤В при В≥0, то виділення одиничного базису можливе завжди. Однак більша частина математичних моделей задач ЛП подається у вигляді, що не дозволяє привести обмеження до даного вигляду, отже, не можна виділити необхідний одиничний базис. Для таких задач розроблено метод штучного базису або М-метод.

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

Нехай існує канонічна задача

F = c1x1 + с2х2 + ... + спхпmax(min)


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

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



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


xj >0; j=1,n,

припускається, що bі≥0.

Для складання розширеної задачі необхідно використати штучні змінні. Штучними називаються невід’ємні змінні, які вводяться в обмеження – рівності для одержання початкового опорного розв’язку. Штучні змінні додаються до рівняння з коефіцієнтом +1 (завжди), а до цільової функції – з коефіцієнтом –М (в задачі на max) і (в задачі на min), де М – додатне число набагато більше за 1.

Таким чином, розширена задача буде мати такий вигляд:

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

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



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


де у1, у2,…,уm - штучні змінні.


Z = c1x1 + с2х2 + ... + спхп - Му1 - М у2 - … - Муm max

Опорний розв’язок: =(0;0;…;0; b1, b2,…, bm).

Для того, щоб обрати вектор, що вводиться до базису для покращення значення цільової функції, використовують так звані оцінки векторів:



де cj – коефіцієнти при змінних в цільовій функції, ;

cі – коефіцієнти при базисних змінних в цільовій функції, ;

aij – коефіцієнти при змінних в обмеженнях.


^ Приклад

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

F=-2 х1+ х2 – х3 → min


1 2 3 = 4;

х2 -2х3 ≤ 5;

1 +2х2 ≥ 3;

xj >0; j=1,n.


Розв’язання

Система обмежень приводиться до канонічного вигляду:


1 2 3 = 4

х2 - 2х3 4 = 5

1 +2х2 – х5 = 3


До рівнянь 1 і 3 додаються штучні змінні (вони є базисними), у рівнянні 2 за базисну обирається х4.


1 2 3 +y1= 4

х2 - 2х3 4 = 5

1 +2х2 – х5 +y2= 3

хj≥0, yi ≥0


Z =-2 х1+ х2 – х3 + Му1 + М у2 → min


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

cj

ci

Вільні члени

-2

1

-1

0

0

M

M

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

x1

x2

x3

x4

x5

у1

у2

у1

M

4

2

1

1

0

0

1

0

4/2=2

x4

0

5

0

1

-2

1

0

0

0

5/0=∞

у2

M

3

2

2

0

0

-1

0

1

3/2

Δj

7M

4М+2

3М-1

М+1

0



0

0


































у1

M

1

0

-1

1

0

1

1

-1

1

x4

0

5

0

1

-2

1

0

0

0

-5/2=∞

x1

-2

3/2

1

1

0

0

-1/2

0

1/2

3/2/0=∞

Δj

M-3

0

-М-3

М+1

0

М+1

0

-2М-1


































x3

-1

1

0

-1

1

0

1

1

-1




x4

0

7

0

-1

0

1

-2

-2

2




x1

-2

3/2

1

1

0

0

-1/2

0

1/2




Δj

-4

0

-2

0

0

0

-1-М








Перевіркою умови оптимальності є наявність в останньому рядку від’ємних значень. Умова виконана, тобто рішення є оптимальним. Функція набуває значення -4 при =(3/2;0;1;7;0;0;0), а значить функція F* також набуває значення -4 при Х*=(3/2;0;1;7;0).

1   2   3   4   5   6   7   8



Схожі:




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