ана задача
a) x1, х 2, x3 , х 4
b)
В В В
a)
В
Візьмемо перші 2 рівності системи обмежень і методом Гауса виділимо базисні невідомі.
Складемо 2 перших рівняння:
В
Висловимо х 3
В
Знайдемо х 4
В
В
Знайдені значення підставимо у функцію мети
Отримаємо завдання
В В В В В
В
Отримаємо стандартну задачу
В В В В В В В
3. Геометрія завдань лінійного програмування
Допустиме безліч, заданий за допомогою лінійних обмежень
(рівнянь або нерівностей), називається опуклою багатогранною областю .
В
Приклади опуклих множин
Теорема 1
Якщо в задачі лінійного програмування допустиме безліч не порожньо і цільова функція обмежена, то існує хоча б одне оптимальне рішення.
Теорема 1 вказує, коли існує оптимальне рішення, але не дає методу знаходження цього рішення
Визначення
Кутовий точкою називається точка безлічі X , якщо вона не є внутрішньою точкою ні для якого відрізка, цілком лежить в X .
Приклади
Теорема 2
Якщо в задачі лінійного програмування на мінімум (максимум) допустиме безліч має хоча б одну кутову точку, а цільова функція обмежена, то кутова точка допустимого безлічі, в якій функція приймає мінімальне (максимальне) значення серед усіх кутових точок, є оптимальним рішенням даної задачі.
Теорема 2 дозволяє для обмежених цільових функцій при малому числі кутових точок вказати процедуру знаходження оптимального рішення.
Процедура виглядає таким чином:
Знаходяться всі кутові точки допустимого безлічі.
Серед цих точок знаходиться точка з мінімальним (максимальним) значенням цільової функції. Знайдена точка і є оптимальне рішення.
При великому числі кутових точок ця процедура є громіздкою, вимагає безлічі обчислень.
При невеликому ж їх числі її можна і навіть бажано застосовувати.
Задача
А) x1, x2
B
C)
В
План рішення
• Побудуємо область допустимих значень
• Знайдемо кутові точки
• Знайдемо значення функції мети в кутових точках
• Знайдемо максимальне серед цих значень
В В В
x2
В В В В В В В В В В В В В В В В В В В
B
В В В В В В В В В
В В В В В В В В В В В В В В В
A
В В В В В В В В В В В В В В В В В В В В В
C
В В В В
В В В В В ...
