Page 32 - 6449

8 5 1 1 3

x 8 1 - 0 -3 -1 24
1
1
x 1 0 1 2 1 8
3
1

0 1 0 23 10 Z  200

2
8
Отже, Z  200, x  24, x  , x  x  x  0.
3
min 1 2 4 5
 1
 1  1 1   1
 7
y    1;8       1;8      ;8  ; y  8, y   7
    1 2
 0 1   0 1 
f  32 8 8 7  256  56  200 .
max
Зауважимо при цьому, що розв’зок двоїстої задачі не обов’язоково
повинен бути додатньо визначеним.

1.6. Поняття про задачі цілочисельного програмування
У багатьох випадках практичних задач, які зводяться до ЗЛП,
виникає проблема цілочисельності розв’язку, якщо ставиться задача
максимальної ефективності роботи підприємства.
Як базисні змінні можуть виступати кількість сировини X ; кількість
1
станків X ; чисельність обслуговувального персоналу X ; кількість
2 3
нафтопродуктів X ; кількість комп’ютерів X ; Очевидно, при знаходженні
4 5
оптимального розв’язку значення змінних X та X можуть бути як цілими,
4
так і дробовими числами, тоді як величини X , X та X повинні бути
2 3 5
цілочисельними.
Як знайти оптимальний розв’язок задачі за умови цілочисельності
деяких змінних? Просте округлення результатів не дає бажаних
результатів, оскільки в одних випадках округлення результатів призводить
до того, що точка з округленими координатами може не належати ОДР, а в
інших випадках округлення результатів призводить до того, що одержана
точка не доставляє цільовій функції оптимального значення серед всіх
цілочисельних точок.
Розглянемо в загальних рисах методику розв’язку задачі
цілочисельного програмування на прикладі двох задач – одна з яких може
бути розв’язана графічним методом, а інша – симплекс-методом.
У тому випадку, коли задачу розв’язують графічним методом,
побудована ОДР модифікується таким чином:
– модифікована область є вупуклою областю;

32