Page 8 - 6449

Сукупність всіх допустимих розв’язків задачі лінійного
програмування утворює область допустимих розв’язків задачі лінійного
програмування (ОДР).
Означення 1.1: випуклою множиною називається множина, будь-
які дві точки якої можуть бути з’єднані прямолінійним відрізком, що
повністю належить даній множині.
Теорема 1.1: область допустимих розв’язків задачі лінійного
програмування завжди є випуклою множиною.
Для того щоб довести цей факт, треба показати, що якщо для
деяких двох допустимих розв’язків х та х виконується умова (1.5), то ця
2
1
ж умова повинна виконуватись і для будь-якого допустимого розв’язку.
х  1 (   х ) 1  х  2 ,   .1;0 (1.6)
3
Справді:
А х  1 (   ) А х   А х  1 (   b )   b  b , (1.7)
3
1
2
що і доводить твердження теореми. При доведенні цієї теореми
використано лінійність функції y  A x , де A – числова матриця, x –
вектор.
Якщо при постановці задачі лінійного програмування система
обмежень записується у вигляді системи рівнянь та нерівностей, або ж
лише нерівностей, то кажуть, що в такому випадку задача лінійного
програмування записана в стандартному вигляді. Як правило, при
постановці практичних задач лінійного програмування використовується
саме стандартна форма запису задачі. Проте для практичного розв’язання
такої задачі необхідно, щоб задача була б подана у формі, в якій система
обмежень була б записана у вигляді системи рівнянь. Така форма запису
називається канонічною формою запису.
Існує методика переходу від стандартної форми запису до
канонічної. З цією метою в кожне з обмежень виду нерівності вводиться
додаткова додатна змінна, причому для кожного такого обмеження вказана
змінна своя, знак вказаної додаткової змінної визначається типом
нерівності: якщо нерівність має знак , то додаткова змінна додається в
ліву частину, а якщо знак нерівності , то додаткова змінна віднімається.
В цільову функцію додаткові змінні входять з коефіцієнтом 0.
Наприклад, поставлена в стандартному вигляді задача :
Z  x  3x  5x  6x  7x  min
1 2 3 4 5
x  2x  x  x  x  7
1 2 3 4 5

 3x 1  x 2  x 3  2x 4  x 5  8

 4 x 1  x 2  x 3  x 4  x 5  9
 3x  x2  x5  x7  x  10
 1 2 3 4 5
х  ,0 і  ,...,1 5
 і
записується в канонічному вигляді таким чином:

8