Загрузка
ТестыСправкаQualiMe РегистрацияВход
ТестыСправкаQualiMe
РегистрацияВход
Тесты Студент
Графический метод ИТ
45.000

Графический метод ИТ

Решите графически задачу:
    $$maxf(X)=-x_1+4x_2$$;
    $$\begin{cases} 2x_1-3x_2\geq 2, \\ x_1+2x_2\leq 8; \end{cases}$$
    $$x_1\geq 0$$, $$x_2\geq 0$$.
Алгоритм решения ЗЛП с двумя переменными графическим методом
  1. Строим область допустимых значений целевой функции. 
  2. Строим вектор-градиент целевой функции, который указывает направление ее наискорейшего возрастания:
    $$\bar{c}(f'_{x_1}; f'_{x_2})$$. 
  3. Строим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Перемещаем линию уровня $$F_0=0$$ вдоль вектора-градиента так, чтобы она касалась ОДЗ в ее крайней точке (до ее разрешающего положения), и строим линию $$F_{max}$$. 
  5. Находим оптимальный план и оптимальное значение целевой функции:
    $$X^*=(x^*_1; x^*_2)$$, $$f(X^*)=c_1x^*_1+c_2x^*_2$$.
  1. Построим область допустимых значений целевой функции (Рисунок 1).
    Построим прямую $$2x_1-3x_2=2$$ (1). Подставим в неравенство $$2x_1-3x_2\geq 2$$ координаты любой точки плоскости, например $$O(0;0)$$ . Так как получили неверное числовое неравенство $$0\geq 2$$, то решением данного неравенства является часть полуплоскости, не содержащая точку $$O(0;0)$$.
    Построим прямую $$x_1+2x_2=8$$ (2). Подставим в неравенство $$x_1+2x_2\leq 8$$ координаты точки $$O(0;0)$$. Так как получили верное числовое неравенство $$0\leq 8$$, то решением данного неравенства является часть полуплоскости, содержащая точку $$O(0;0)$$.
                                                          
                                                                                                             Рис. 1
    Пересечение решений неравенств системы ограничений образуют ОДЗ целевой функции. А так как переменные неотрицательные, то решение системы неравенств будет находиться только в первой четверти координатной плоскости: треугольник$$ABC$$. 
  2. Построим вектор-градиент целевой функции: $$\bar{c}(-1;4)$$ (Рисунок 2). 
                                                  
                                                                                                         Рис. 2
  3. Построим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Из Рисунка 2 видим, что линия уровня $$F_{max}$$ проходит через точку $$B$$, координаты которой найдем, решая систему уравнений:
    $$\begin{cases} 2x_1-3x_2=2, \\ x_1+2x_2=8; \end{cases}$$$$\begin{cases} 2x_1-3x_2=2, \\ 2x_1+4x_2=16; \end{cases}$$$$\begin{cases} 7x_2=14, \\ x_1+2x_2=8; \end{cases}$$$$\begin{cases} x_2=2, \\ x_1=4. \end{cases}$$ 
  5. Оптимальный план задачи: $$X^*=(4;2)$$.
    Оптимальное значение целевой функции: $$f(X^*)=-4+4\cdot 2=4$$.
  1. Чтобы построить прямую, достаточно знать две точки, ей принадлежащие.
    Например, прямую $$2x_1-3x_2=2$$ можно построить по точкам:
    $$x_1=0$$, $$x_2=-\frac{2}{3}$$ и $$x_2=0$$, $$x_1=1$$. 
  2. Чтобы построить вектор-градиент, необходимо найти частные производные целевой функции:
    $$f'_{x_1}(X)=(-x_1)'_{x_1}+(4x_2)'_{x_1}=-1+0=-1$$;
    $$f'_{x_2}(X)=(-x_1)'_{x_2}+(4x_2)'_{x_2}=0+4=4$$.
Выберите несколько вариантов ответов
Решите графически задачу:
    $$minf(X)=0, 3x_1+2x_2$$;
    $$\begin{cases} 3x_1-5x_2\leq 0, \\ x_1+x_2\geq 6, \\ x_1+2x_2\geq 10; \end{cases}$$
    $$x_1\geq 0$$, $$x_2\geq 0$$.
Алгоритм решения ЗЛП с двумя переменными графическим методом
  1. Строим область допустимых значений целевой функции. 
  2. Строим вектор-антиградиент целевой функции, который указывает направление ее наискорейшего убывания:
    $$-\bar{c}(f'_{x_1}; f'_{x_2})$$. 
  3. Строим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Перемещаем линию уровня $$F_0=0$$ вдоль вектора-антиградиента так, чтобы она касалась ОДЗ в ее крайней точке (до ее разрешающего положения), и строим линию $$F_{min}$$. 
  5. Находим оптимальный план и оптимальное значение целевой функции: 
    $$X^*=(x^*_1; x^*_2)$$, $$f(X^*)=c_1x^*_1+c_2x^*_2$$.
  1. Построим область допустимых значений целевой функции (Рисунок 4).
    Найдем решение первого неравенства системы ограничений.
    Для этого построим прямую$$3x_1-5x_2=0$$ (1).
    Подставим в неравенство $$3x_1-5x_2\leq 0$$ координаты точки $$M(1;0)$$.
    Так как получили неверное числовое неравенство $$3\leq 0$$, то решением данного неравенства является часть полуплоскости, не содержащая точку $$M(1;0)$$.
    Аналогично найдем решения второго и третьего неравенств системы ограничений. 
                                                              
                                                                                                                 Рис. 4
  2. Построим вектор-градиент целевой функции: $$\bar{c}(0,3;2)$$ (Рисунок 5). 
                                                            
                                                                                                            Рис. 5
  3. Построим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Из Рисунка 5 видим, что линия уровня $$F_{min}$$ проходит через точку $$A$$, координаты которой найдем, решая систему уравнений:
    $$\begin{cases} 3x_1-5x_2=0, \\ x_1+2x_2=10; \end{cases}$$$$\begin{cases} 3x_1-5x_2=0, \\ 3x_1+6x_2=30; \end{cases}$$$$\begin{cases} 11x_2=30, \\ x_1+2x_2=10; \end{cases}$$$$\begin{cases} x_2=\frac{30}{11}, \\ x_1=\frac{50}{11}. \end{cases}$$ 
  5. Оптимальный план задачи:
    $$X^*=\left ( \frac{50}{11};\frac{30}{11} \right )$$.
    Оптимальное значение целевой функции:
    $$f(X^*)=\frac{15}{11}+\frac{60}{11}=\frac{75}{11}$$.
Максимальное значение целевой функции определить невозможно, так как ОДЗ – неограниченная область.
Выберите несколько вариантов ответов
Решите графическим методом задачу:
    $$minf(X)=2x_1-3x_2$$;
    $$\begin{cases} x_1-x_2\leq 0, \\ x_1+x_2\leq 10; \end{cases}$$
    $$x_1\geq 5$$, $$x_2\geq 0$$.
Алгоритм решения ЗЛП с двумя переменными графическим методом
  1. Строим область допустимых значений целевой функции. 
  2. Строим вектор-антиградиент целевой функции, который указывает направление ее наискорейшего убывания:
    $$-\bar{c}(f'_{x_1}; f'_{x_2})$$. 
  3. Строим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Перемещаем линию уровня $$F_0=0$$ вдоль вектора-антиградиента так, чтобы она касалась ОДЗ в ее крайней точке (до ее разрешающего положения), и строим линию $$F_{min}$$. 
  5. Находим оптимальный план и оптимальное значение целевой функции:
    $$X^*=(x^*_1; x^*_2)$$, $$f(X^*)=c_1x^*_1+c_2x^*_2$$.
  1. Найдем решение системы неравенств (Рисунок 6):
    $$\begin{cases} x_1-x_2\leq 0, \\ x_1+x_2\leq 10. \end{cases}$$
    Решим первое неравенство. Для этого построим прямую $$x_1-x_2=0$$ (1). Подставим в неравенство $$x_1-x_2\leq0$$ координаты точки $$M(1;0)$$. Так как получили неверное числовое неравенство $$1\leq0$$, то решением первого неравенства является часть полуплоскости, не содержащая точку $$M(1;0)$$.
    Решим второе неравенство. Для этого построим прямую $$x_1+x_2=10$$ (2). Подставим в неравенство $$x_1+x_2\leq10$$ координаты точки $$M(1;0)$$. Так как получили верное числовое неравенство $$1\leq10$$, то решением данного неравенства является часть полуплоскости, содержащая точку $$M(1;0)$$. 
                                                                  
                                                                                                              Рис. 6
  2. Найдем координаты точки $$A$$: $$\begin{cases} x_1-x_2=0, \\ x_1+x_2=10; \end{cases}$$$$\begin{cases} 2x_1=10, \\ x_1+x_2=10; \end{cases}$$$$\begin{cases} x_1=5, \\ x_2=5.\end{cases}$$. 
  3. Построим прямую $$x_1=5$$ (3).
    Так как $$x_1\geq 5$$, $$x_2\geq 0$$ (Рисунок 7), то ОДЗ: точка $$A(5;5)$$. 
                                                                 
                                                                                                               Рис. 7
  4. Следовательно, оптимальный план задачи: $$X^*=(5;5)$$.
    Оптимальное значение целевой функции: $$f(X^*)=2\cdot 5-3\cdot 5=-5$$.
$$f_{min}(X^*)=f_{max}(X^*)=-5$$.
Выберите несколько вариантов ответов
Решите графически задачу:
    $$minf(X)=x_1+2x_2$$;
    $$\begin{cases} x_1+2x_2\geq 2, \\ x_1+2x_2\geq 8; \end{cases}$$
    $$x_1\geq 0$$, $$x_2\geq 0$$.
Алгоритм решения ЗЛП с двумя переменными графическим методом
  1. Строим область допустимых значений целевой функции. 
  2. Строим вектор-антиградиент целевой функции, который указывает направление ее наискорейшего убывания:
    $$-\bar{c}(f'_{x_1}; f'_{x_2})$$. 
  3. Строим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Перемещаем линию уровня $$F_0=0$$ вдоль вектора-градиента так, чтобы она касалась ОДЗ в ее крайней точке (до ее разрешающего положения), и строим линию $$F_{min}$$. 
  5. Находим оптимальный план и оптимальное значение целевой функции:
    $$X^*=(x^*_1; x^*_2)$$, $$f(X^*)=c_1x^*_1+c_2x^*_2$$.
  1. Построим область допустимых значений целевой функции (Рисунок 8).
    Найдем решение первого неравенства системы ограничений. Построим прямую $$x_1+2x_2=2$$ (1). Подставим в неравенство $$x_1+2x_2\geq 2$$ координаты точки $$O(0;0)$$. Так как получили неверное числовое неравенство $$0\geq 2$$, то решением данного неравенства является часть полуплоскости, не содержащая точку $$O(0;0)$$.
    Аналогично найдем решение второго неравенства системы ограничений. Пересечение решений неравенств системы ограничений образуют ОДЗ целевой функции.
    А так как переменные неотрицательные, то решение системы неравенств будет находиться только в первой четверти координатной плоскости: неограниченная область $$ABCD$$. 
                                                          
                                                                                                          Рис. 8
  2. Построим вектор-антиградиент целевой функции: $$-\bar{c}(-1;-2)$$ (Рисунок 9). 
                                                           
                                                                                                       Рис. 9
  3. Построим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$-\bar{c}$$. 
  4. Так как вектор $$-\bar{c}(-1;-2)$$ перпендикулярен прямой $$x_1+2x_2-2=0$$, то линия уровня $$F_{min}$$ совпадает с этой прямой. Следовательно, функция $$f(X)=x_1+2x_2$$ достигает своего наименьшего значения в любой точке отрезка $$BC$$. Действительно, значение функции $$f(X)=x_1+2x_2$$ в точке $$B(0;4)$$ равно $$8$$ и значение этой функции в точке $$C(8;0)$$ также равно $$8$$.
  1. Общее уравнение прямой: $$Ax+By+C=0$$. 
  2. Нормальный вектор прямой: $$\bar{c}(A;B)$$.
Выберите несколько вариантов ответов
Решите графически задачу:
    $$maxf(X)=-x_1+4x_2$$;
    $$\begin{cases} x_1+2x_2\leq 2, \\ x_1+2x_2\geq 8; \end{cases}$$
    $$x_1\geq 0$$, $$x_2\geq 0$$.
Алгоритм решения ЗЛП с двумя переменными графическим методом
  1. Строим область допустимых значений целевой функции. 
  2. Строим вектор-градиент целевой функции, который указывает направление ее наискорейшего возрастания: $$\bar{c}(f'_{x_1}; f'_{x_2})$$. 
  3. Строим линию уровня $$F_0=0$$, проходящую через начало координат перпендикулярно вектору $$\bar{c}$$. 
  4. Перемещаем линию уровня $$F_0=0$$ вдоль вектора-градиента так, чтобы она касалась ОДЗ в ее крайней точке (до ее разрешающего положения), и строим линию $$F_{max}$$. 
  5. Находим оптимальный план и оптимальное значение целевой функции:
    $$X^*=(x^*_1; x^*_2)$$, $$f(X^*)=c_1x^*_1+c_2x^*_2$$.
Построим область допустимых значений целевой функции (Рисунок 3).
  1. Найдем решение первого неравенства системы ограничений.
    Построим прямую $$x_1+2x_2=2$$ (1). Подставим в неравенство $$x_1+2x_2\leq 2$$ координаты точки $$O(0;0)$$.
    Так как получили верное числовое неравенство $$0\leq 2$$, то решением данного неравенства является часть полуплоскости, содержащая точку $$O(0;0)$$. 
  2. Аналогично найдем решение второго неравенства системы ограничений.
Так как решения неравенств системы ограничений не пересекаются, то ОДЗ целевой функции – пустое множество. Следовательно, данная задача решений не имеет.
                                                                          
                                                                                                         Рис. 3
Прямые $$A_1x+B_1y+C_1=0$$ и $$A_2x+B_2y+C_2=0$$ параллельны, если 
$$A_1=A_2$$, $$B_1=B_2$$ и $$C_1\neq C_2$$.
Выберите несколько вариантов ответов
© Сиротина И.К., 2013—2026