Лабораторна робота №3 Тема. Програмування побудови двоїстої задачі Мета



Сторінка1/11
Дата конвертації31.12.2016
Розмір1.27 Mb.
  1   2   3   4   5   6   7   8   9   10   11



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



Тема. Програмування побудови двоїстої задачі
Мета:

  1. Розглянути принцип двоїстості в лінійному програмуванні;

  2. Створити програму побудови двоїстої задачі до заданої у вигляді матриці коефіцієнтів системи обмежень та вектора коефіцієнтів цільової функції;

  3. Пояснити економічний зміст двоїстої задачі та взаємозв’язок вихідної і двоїстої задач;

  4. Створити програму побудови двоїстої задачі, що працює у “дружньому інтерфейсі” з користувачем (введення даних та виведення результатів здійснюється у вигляді стрічок системи обмежень та математичного вигляду цільової функції).


Завдання для самостійної роботи.

  1. Повторити теоретичний матеріал лекції “Принцип двоїстості в ЛП”.

  2. Розглянути приклади побудови двоїстих задач.

  3. Виконати завдання лабораторної роботи. Завдання виділенні курсивом є додатковими та розрахованими на оцінку відмінно”.

  4. Провести тестування програми (Додаток 2). Виконати завдання свого варіанту.

  5. Зробити висновок, оформити результат виконання.



  1. Теоретичні відомості

  2. Дві задачі лінійного програмування називаються взаємно-двоїстими, якщо виконуються такі умови:


  1. Матриці системи обмежень обох задач є транспонованими, одна по відношенні до другої;

  2. Системи обмежень складаються з нерівностей, які спрямовані в обох задачах в протилежні боки;

  3. Коефіцієнти оптимізуючої форми одної задачі є вільними членами другої і навпаки;

  4. Форми в обох задачах оптимізуються в протилежних смислах (одна на min, друга на max).

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

Загальні правила побудови двоїстих задач:

І. Перевіряємо виконання таких вимог:

  1. В усіх обмеженнях вільні члени знаходяться в правій частині рівності чи нерівності, члени з невідомими – в лівій;

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

  3. Загальний член нерівності системи обмежень пов’язується з оптимізацією форми так: якщо “” то min, якщо “”, то max.

ІІ. При побудові системи обмежень двоїстої задачі дотримуємось правил:

  1. Кожному обмеженню вихідної задачі відповідає невідома yi двоїстій задачі, причому на двоїсту невідому, що відповідає обмеженню – нерівності, накладаються умови невід’ємності, а рівності – ні.

  2. Кожній невідомій xj вихідної задачі відповідає обмеження двоїстої. Будуються ці обмеження так: множаться коефіцієнти aij, що стоять при xj на відповідні двоїсті невідомі yi , результати множення сумуються і ставляться в лівій частині обмеження, а в правій – коефіцієнт cj, що знаходиться при xj в оптимізуючій формі.

  3. В усіх обмеженнях двоїстої задачі ставимо один і той же знак нерівності, протилежний до загального знаку нерівності системи обмежень вихідної задачі.

ІІІ. Для оптимізуючої форми двоїстої задачі повинні задовольнятись умови:

  1. Форма z* двоїстої задачі оптимізується в протилежному з z смислі.

  2. Коефіцієнтами при двоїстих невідомих в формі z* є відповідно вільні члени системи обмежень вихідної задачі. Вільний член c0 форми z переноситься без зміни в форму z*.

Приклад побудови двоїстої задачі. Побудувати двоїсту задачу до такої задачі лінійного програмування:



z=z-x1+2x3 (max).

Перш ніж побудувати двоїсту задачу до даної замінимо знак другого обмеження на (для цього множимо його на (-1)) і згрупуємо члени:





z=2-x1+2x3 (max).

У відповідність обмеженням вихідної задачі покладемо двоїсті невідомі у1, у2, у3 і будуємо двоїсту задачу



23z=-24x1-50x2 (max)

-x199-3(x1+x2)

-2x1-2x2-74

3x1+2x2101

x10, x20Основні етапи програмування побудови двоїстої задачі.

  1. Оголошуємо список змінних, необхідних для роботи програми:

  1. АМасив коефіцієнтів при невідомих системи обмеженьBВектор вільних членів системи обмеженьSВектор символьних значень, що позначають знаки в нерівностях системи обмеженьСВектор коефіцієнтів при невідомих у оптимізуючій форміОрЛогічна змінна із значенням 0 у випадку дослідження оптимізуючої форми на мінімум та 1 у випадку дослідження оптимізуючої форми на максимумi, jНеобхідні цілочисельні змінні для лічильників у циклахСкладаємо програму за примірним сценарієм:

  2. Формуємо матрицю А коефіцієнтів при невідомих в системі обмежень;

  3. Формуємо вектор В вільних членів;

  4. Вводимо значення “” чи “” для всіх нерівностей у вектор S;

  5. Формуємо вектор С коефіцієнтів при невідомих у оптимізуючій формі;

  6. Задаємо значення змінній Ор в залежності від типу оптимізації;

  7. Порівнюємо значення Si із знаком нерівностей, що відповідає канонічному вигляду оптимізуючої форми, залежно від значення змінної Ор. У випадку неспівпадання міняємо знак всіх коефіцієнтів аij та bi (Це бажано оформити процедурою);

  8. Транспонуємо матрицю коефіцієнтів перестановкою рядків і стовпців місцями;

  9. Міняємо місцями вектори В і С;

  10. Для оптимізуючої форми виводимо тип оптимізації протилежний до заданого в змінній Ор.

236x1+5230

5x1+6x230

x1+x23

0x14

z=-4x1-6x2+14 (extr)

Завдання для самостійної роботи відповідають Вашому варіанту індивідуального завдання №4 для самостійного виконання (для коректної роботи програми необхідно перенести всі невідомі вліво, а вільні члени системи обмежень вправо та згрупувати подібні члени).

Контрольні запитання

  1. Сформулюйте принцип двоїстості. Які задачі називаються взаємно-двоїстими?

  2. Сформулюйте умови існування взаємно – двоїстих задач.

  3. Що таке канонічна форма задачі лінійного програмування?

  4. Яка матриця називається транспонованою, які її властивості?

  5. Сформулюйте правила побудови двоїстих задач.

  6. Яка економічна суть двоїстих задач?

  7. Сформулюйте теорему про зв’язок розв’язків взаємно – двоїстих задач.

  8. Сформуйте алгоритм побудови двоїстої задачі.

  9. Яка суть змінних А, В, С, S, Ор, перерахованих в таблиці ідентифікаторів.


Додаток 2

Орієнтовний текст програми
program L2;

uses crt;

var

i,j,m,n:integer;



Opt:string;

A,a1:array[1..4, 1..4] of integer;

b:array[1..4] of integer;

c:array[0..4] of integer;

s:array[1..4] of string[2];

zn:string[2];

begin

clrscr;


writeln('Введiть кiлькiсть рядкiв ');

read(m);


writeln('Введiть кiлькiсть невiдомих');

read(n);


for i:=1 to m do

begin


writeln('Введiть коефiцiєнти системи ', i,'-ого рядка');

for j:=1 to n do read(a[i,j]);

end;

writeln('Введiть вiльнi коефiцiєнти');



for i:=1 to m do read(b[i]);

writeln('Введiть коефiцiєнти цiльової функцiї починаючи з вiльних');

for j:=0 to n do readln(c[j]);

writeln('Введiть знаки рiвностей');

for i:=1 to m do readln(s[i]);

writeln('Введiть тип оптимiзацiї');

read(Opt);

for i:=1 to m do

if (Opt='max') and (s[i]='>=') then

begin


s[i]:='<=';

b[i]:=-b[i];

for j:=1 to n do a[i,j]:=-a[i,j];

end;
for i:=1 to m do

if (Opt='min') and (s[i]='<=') then

begin


s[i]:='>=';

b[i]:=-b[i];

for j:=1 to n do a[i,j]:=-a[i,j]

end;


if Opt='max' then begin

Opt:='min';

zn:='>=';

end


else if Opt='min' then

begin


Opt:='max';

zn:='<=';

end;

for i:=1 to m do



for j:=1 to n do a1[j,i]:= a[i,j]

writeln('Задача двоїста до заданої');

for j:=1 to n do begin

for i:=1 to m do begin

if a1[j,i]>=0 then write('+');

write(a1[j,i]:3,'y',i:1);

end;

write(zn);



write(c[j]:3);

writeln;


end;

write('z=');

write(c[0]);

for i:=1 to m do begin

if b[i]>=0 then write('+');

write(b[i]:3,'y',i:1);

end;

writeln(' ',Opt);



end.

  1   2   3   4   5   6   7   8   9   10   11


База даних захищена авторським правом ©lecture.in.ua 2016
звернутися до адміністрації

    Головна сторінка