Система m линейных уравнений с n неизвестными

Система m линейных уравнений с n переменными имеет вид

Любые m переменных системы m линейных уравнений с n переменными (m

Базисным решением системы m линейных уравнений с n переменными называется решение,

Геометрический метод решения задач линейного программирования

Решение неравенств

Множеством решений неравенства
с двумя переменными является одна из полуплоскостей, на которые

Множеством решений совместной системы m линейных неравенств с двумя переменными

является выпуклый многоугольник (или выпуклая многоугольная область)

Множество всех допустимых решений совместной системы m линейных уравнений с n

Угловая точка

Сформулированные теоремы и понятия позволяют сделать следующие выводы.

Если основная задача линейного программирования имеет оптимальный план, то максимальное или

Если максимальное значение целевая функция задачи принимает более чем в одной

Для определения этой вершины необходимо построить линию уровня
c1x1+ c2x2=h (где

и будем передвигать ее в направлении вектора
d= (c1;c2),
до тех

Координаты указанной точки и определяют оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации задачи , отметим, что при нахождении ее

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

х2 А
х1

Из рис. 2 видно, что максимальное значение целевая функция принимает в

х2 А
В
х1

Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой

Итак, нахождение решения задачи линейного программирования на основе ее геометрической интерпретации

1. Строят прямые, уравнения которых получаются в результате замены в ограничениях

2. Находят полуплоскости, определяемые каждым из ограничений задачи.
3. Находят многоугольник решений.

4. Строят вектор целевой функции d(c1;c2),.
5. Строят прямую c1x1+ c2x2=h,

6. Передвигают прямую в направлении вектора , в результате чего -

7. Определяют координаты точки максимума (минимума) функции и вычисляют значение целевой

Для изготовления двух видов продукции Р1 и Р2 используют 4 вида

Прибыль, полученная от единицы продукции Р1 и Р2 , - соответственно

Найдем решение сформулированной задачи, используя ее геометрическую интерпретацию.
Сначала построим многоугольник

Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки

Х1+3х2=18

х2 х1+3х2=18
х1

Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из

х2
х1+3х2=18
х1

В результате получим:

х2 х1+3х2=18
х1=7
х2=5
2х1+ х2=16
х1

х2 х1+3х2=18
х1=7
х2=5
2х1+ х2=16
х1

х1+3х2=18
2х1+х2=16
х1=18-3х2
2(18-3х2)+х2=16
-5х2=-20
х2=4
х1= 6
F=2*6+3*4=24

Область допустимых решений задачи линейного программирования имеет вид:
Тогда максимальное значение функции

Область допустимых решений задачи линейного программирования имеет вид
Тогда максимальное значение функции

Максимальное значение целевой функции  
при ограничениях
равно…

Максимальное значение целевой функции  
при ограничениях
равно…