Загрузка

Математическая модель ЗЛП

Для кондитерского цеха требуется рассчитать оптимальный план выпуска печенья двух видов: $$\Pi _1$$ и $$\Pi _2$$. Для производства печенья используют муку, сахар и масло, запасы которых равны соответственно $$150$$ кг, $$60$$ кг и $$40$$ кг. Другие ингредиенты, входящие в готовый продукт в небольших количествах, не учитываются. Для производства одного килограмма печенья $$\Pi _1$$ требуется $$0, 4$$ кг муки, $$0, 3$$ кг сахара и $$0, 2$$ кг масла, а для $$\Pi _2$$ требуется $$0, 6$$ кг муки, $$0, 2$$ кг сахара и $$0, 1$$ кг масла. Прибыль от выпуска одного килограмма печенья составляет: для $$\Pi _1$$$$15$$ тыс. ден. ед. , для $$\Pi _2$$$$10$$ тыс. ден. ед.

Математическая модель задачи имеет вид:

Математическая модель задачи о распределении ресурсов

План: $$X=(x_1; x_2; . . . ; x_n)$$ .

Целевая функция качества:

$$max$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ .

Система ограничений:

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$ .

Условия не отрицательности переменных:

$$x_i\geq 0$$ , $$i=\overline{1, n}$$ .

Где: $$b_j$$$$( j=\overline{1, m})$$ – объемы ресурсов;

$$c_i$$$$( i=\overline{1, n})$$ – прибыль от реализации одной единицы каждого вида продукции;

$$a_{ji}$$ – расход $$j$$-го вида ресурса на выпуск одной единицы $$i$$-го вида продукции.

Составим таблицу данных:

Составим математическую модель задачи:
план выпуска продукции: $$X=(x_1;x_2)$$ ;
целевая функция: 

$$max$$$$f(x)=15x_1+10x_2$$  ;

система ограничений:

 $$\begin{cases} 0,4x_1+0,6x_2\leq 150, \\ 0,3x_1+0,2x_2\leq 60, \\ 0,2x_1+0,1x_2\leq 40; \end{cases}$$

условия не отрицательности переменных: 

$$x_1\geq 0$$ , $$x_2\geq 0$$ .


Математической моделью задачи называют отражение реальной (производственной, экономической) ситуации в виде функций, уравнений и неравенств.

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

Выберите несколько вариантов ответов

Дневной рацион корма зверей в зоопарке должен содержать не менее $$25$$ ед. питательного вещества $$A$$, $$45$$ ед. вещества $$B$$ и $$32$$ ед. вещества $$C$$. Используются три вида корма: $$K_1$$, $$K_2$$ и $$K_3$$. Один килограмм корма $$K_1$$ содержит питательных веществ $$A$$, $$B$$ и $$C$$ соответственно $$3$$ ед. , $$2$$ ед. и $$0$$ ед. , корма $$K_2$$$$1$$ ед. , $$6$$ ед. и $$5$$ ед. , а корма $$K_3$$$$4$$ ед. , $$2$$ ед. и $$1$$ ед. Стоимость $$1$$ кг корма $$K_1$$ равна $$50$$ ден. ед. , корма $$K_2$$$$60$$ ден. ед. и корма $$K_3$$$$40$$ ден. ед. Сколько корма каждого вида необходимо расходовать ежедневно, чтобы затраты на него были минимальными?

Математическая модель задачи имеет вид:

Математическая модель задачи о смесях (диетах)

План: $$X=(x_1; x_2; . . . ; x_n)$$ .

Целевая функция качества:

$$min$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ .

Система ограничений:

$$\sum_{i=1}^{n}a_{ji}x_i\geq b_j$$ .

Условия не отрицательности переменных:

$$x_i\geq 0$$ , $$i=\overline{1, n}$$ .

Где: $$b_j$$$$( j=\overline{1, m})$$ – объемы ресурсов;

$$c_i$$$$( i=\overline{1, n})$$ – затраты на одну единицу каждого вида продукции;

$$a_{ji}$$ – содержание $$j$$-го вида ресурса в одной единице $$i$$-го вида продукции.

Составим таблицу данных:

Составим математическую модель задачи:
план кормления: $$X=(x_1;x_2;x_3)$$ ;
целевая функция: 

$$min$$$$f(X)=50x_1+60x_2+40x_3$$  ;

система ограничений:  

$$\begin{cases} 3x_1+x_2+4x_3\geq 25, \\ 2x_1+6x_2+2x_3\geq 45, \\ 5x_2+x_3\geq 32; \end{cases}$$

условия не отрицательности переменных: 

$$x_1\geq 0$$ , $$x_2\geq 0$$ , $$x_3\geq 0$$ .

Симметричные формы записи задач:

  1. $$X=(x_1; x_2; . . . x_n)$$ ; $$max$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ ;

    $$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$ ; $$x_i\geq 0$$ , $$i=\overline{1, n}$$ ;

  2. $$X=(x_1; x_2; . . . x_n)$$ ; $$min$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ ;

    $$\sum_{i=1}^{n}a_{ji}x_i\geq b_j$$ ; $$x_i\geq 0$$ , $$i=\overline{1, n}$$ .

Выберите несколько вариантов ответов

Выполнять заказ по производству $$35$$ изделий первого вида и $$40$$ изделий второго вида взялись две бригады. Производительность первой бригады составляет соответственно $$4$$ и $$2$$ изделия в единицу времени, а фонд рабочего времени этой бригады $$10$$ ед. Производительность второй бригады – соответственно $$2$$ и $$5$$ изделий, а ее фонд рабочего времени – $$15$$ ед. Затраты, связанные с производством единицы изделия, для первой бригады равны соответственно $$9$$ и $$20$$ тыс. ден. ед. , для второй бригады – $$15$$ и $$30$$ тыс. ден. ед. Найдите оптимальный план размещения заказа при условии, что фонд рабочего времени первой бригады должен быть использован полностью.

Математическая модель задачи имеет вид:

Математическая модель ЗЛП

План: $$X=(x_1; x_2; . . . ; x_n)$$ .

Целевая функция качества:

$$max$$$$(min)$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ .

Система ограничений:

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$ $$(=, \geq)$$, $$j=\overline{1, m}$$ .

Условия не отрицательности переменных:

$$x_i\geq 0$$ , $$i=\overline{1, n}$$ .

Составим таблицу данных:

Составим математическую модель задачи:
план выпуска продукции: 

$$X=(x_1;x_2;x_3;x_4)$$ ;

целевая функция: 

$$min$$$$f(X)=9x_1+20x_2+15x_3+30x_4$$  ;

система ограничений:  

$$\begin{cases} x_1+x_3= 35, \\ x_2+x_4= 40, \\ 0,25x_1+0,5x_2= 10,\\ 0,5x_3+0,2x_4\leq 15; \end{cases}$$

условия не отрицательности и целочисленности переменных: 

$$x_1\geq 0$$ , $$x\in Z$$ , $$i=\overline{1,4}$$ .

Если $$T$$ – общее время выполнения работы, $$k$$ – количество изделий, выпущенных за это время, $$t$$ – время выпуска одного изделия, то

$$T=k\cdot t$$ , откуда $$t=T: k$$ .

Так, если $$T=1$$ , $$k_1=4$$ , то

$$t_1=1: 4=0, 25$$ .

Аналогично,

$$t_2=1: 2=0, 5$$,

$$t_3=1: 2=0, 5$$,

$$t_4=1: 5=0, 2$$.

Выберите несколько вариантов ответов

В цех распила поступило $$600$$ бревен длиной $$6$$ м. Их необходимо разрезать на заготовки $$A$$ и $$B$$ длиной соответственно $$2, 5$$ м и $$3, 5$$ м и составить из них комплекты. В каждый комплект входит $$4$$ заготовки $$A$$ и $$5$$ заготовок $$B$$. Составьте план распила бревен, гарантирующий минимизацию отходов.

Математическая модель задачи имеет вид:

Математическая модель ЗЛП

План: $$X=(x_1; x_2; . . . ; x_n)$$ .

Целевая функция качества:

$$max$$$$(min)$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ .

Система ограничений:

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$ $$(=, \geq )$$, $$j=\overline{1, m}$$ .

Условия не отрицательности переменных:

$$x_i\geq 0$$ , $$i=\overline{1, n}$$ .

Составим таблицу данных:

Составим математическую модель задачи: 

План: $$X=(x_1;x_2;x_3)$$ , где 
 $$x_1$$ – количество бревен, подлежащих распилу по варианту $$I$$,
 $$x_2$$ – количество бревен, подлежащих распилу по варианту $$II$$,
 $$x_3$$ – количество бревен, подлежащих распилу по варианту $$III$$;
$$x_1$$$$x_2$$$$x_3\geq0$$.
Целевая функция: 

$$min$$$$f(X)=x_1+0,5x_2$$ .

Система ограничений: 

$$\begin{cases} x_1+x_2+x_3\leq 600, \\ \frac{2x_1+x_2}{4}=\frac{x_2+2x_3}{5}; \end{cases}$$$$\begin{cases} x_1+x_2+x_3\leq 600, \\ 10x_1+x_2-8x_3=0. \end{cases}$$

   

К основным видам задач ЛП, как правило, относят: задачи о наилучшем использовании ресурсов, задачи о выборе оптимальных технологий, задачи о размещении заказа, задачи о смесях, задачи о раскрое материалов, транспортные задачи и т. п.

Выберите несколько вариантов ответов

Приведите к каноническому виду модель задачи:

$$max$$$$f(X)=3x_1-x_2$$;

$$\begin{cases} 2x_1+x_2\leq 3, \\ x_1-x_2\leq 12; \end{cases}$$

$$x_i\geq 0$$, $$i=\overline{1, 2}$$.

Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:

  1. к левым частям неравенств типа $$\leq$$ прибавить неотрицательные дополнительные переменные;
  2. в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.

Приведем модель задачи к каноническому виду с помощью дополнительных переменных $$x_3$$ и $$x_4$$ .

Целевая функция: $$max$$ $$f(X)=3x_1-x_2+0\cdot x_3+0\cdot x_4$$ .

Система ограничений: $$\begin{cases} 2x_1+x_2+x_3=3, \\ x_1-x_2+x_4=12. \end{cases}$$

Условия неотрицательности переменных: $$x_i\geq 0$$ , $$i=\overline{1, 4}$$ .

Каноническая форма записи ЗЛП:

$$max$$$$(min)$$$$f(X)=\sum_{i=1}^{n}c_ix_i$$ ;

$$\sum_{i=1}^{n}a_{ji}x_i=b_j$$ ;

$$x_i\geq 0$$ , $$i=\overline{1, n}$$ .

Выберите несколько вариантов ответов

Приведите к каноническому виду модель задачи:

$$min$$$$f(X)=3x_1-x_2$$;

$$\begin{cases} 2x_1+x_2\geq 3, \\ x_1-x_2\leq -2; \end{cases}$$

$$x_i\geq 0$$, $$i=\overline{1, 2}$$.

Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:

  1. из левых частей неравенств типа $$\geq$$ вычесть неотрицательные дополнительные переменные;
  2. в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.

Приведем модель задачи к каноническому виду с помощью дополнительных переменных $$x_3$$ и $$x_4$$ .

Целевая функция:

$$min$$ $$f(X)=3x_1-x_2+0\cdot x_3+0\cdot x_4$$ .

Система ограничений:

$$\begin{cases} 2x_1+x_2\geq 3, \\ -x_1+x_2\geq 2; \end{cases}$$$$\begin{cases} 2x_1+x_2-x_3=3, \\ -x_1+x_2-x_4=2. \end{cases}$$

Условия неотрицательности переменных:

$$x_i\geq 0$$ , $$i=\overline{1, 4}$$ .

Приводить модель задачи к каноническому виду можно только при условии, что все правые части неравенств-ограничений неотрицательные.

Так как правая часть неравенства $$x_1-x_2\leq -2$$ отрицательная, то мы умножили обе части этого неравенства на число $$-1$$, изменив при этом его смысловой знак: $$-x_1+x_2\geq 2$$ .

Выберите несколько вариантов ответов

Решите графически задачу:

$$max$$ $$f(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. Построим область допустимых значений целевой функции.

Найдем решение первого неравенства системы ограничений. 

Построим прямую $$2x_1-3x_2=2$$ (1) (рис. 10.1).

 

Подставим в неравенство $$2x_1-3x_2\geq 2$$ координаты любой точки плоскости, например точки $$O(0;0)$$ . Так как получили неверное числовое неравенство $$0\geq 2$$, то решением данного неравенства является часть полуплоскости, не содержащая точку $$O(0;0)$$

Построим прямую $$x_1+2x_2=8$$ (2) (рис. 10.1).

Подставим в неравенство  $$x_1+2x_2\leq 8$$ координаты точки  $$O(0;0)$$. Так как получили верное числовое неравенство $$0\leq 8$$ , то решением данного неравенства является часть полуплоскости, содержащая точку  $$O(0;0)$$.

Пересечение решений неравенств системы ограничений образуют ОДЗ целевой функции. А так как переменные неотрицательные, то решение системы неравенств будет находиться только в первой четверти координатной плоскости: треугольник $$ABC$$

2. Построим вектор-градиент целевой функции: $$\bar{c}(-1;4)$$ (рис. 10.2).

3. Построим линию уровня $$F_0=0$$ , проходящую через начало координат перпендикулярно вектору $$\bar{c}$$ .
4. Из рисунка 10.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}$$
Оптимальный план: $$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$$ .

Выберите несколько вариантов ответов

Решите графически задачу:

$$max$$$$f(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$$ .
Построим область допустимых значений целевой функции.

Найдем решение первого неравенства системы ограничений. Построим прямую $$x_1+2x_2=2$$ (1) (рис. 10.3). Подставим в неравенство $$x_1+2x_2\leq 2$$ координаты точки $$O(0;0)$$ .Так как получили верное числовое неравенство $$0\leq 2$$, то решением данного неравенства является часть полуплоскости, содержащая точку $$O(0;0)$$

Аналогично найдем решение второго неравенства системы ограничений. 

Так как решения неравенств системы ограничений не пересекаются, то ОДЗ целевой функции – пустое множество (рис. 10.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$$.

Выберите несколько вариантов ответов

Решите графически задачу:

$$min$$$$f(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. Построим область допустимых значений целевой функции (рис. 10.4). 

Найдем решение первого неравенства системы ограничений. Для этого построим прямую $$3x_1-5x_2=0$$ (1) (рис. 10.4). Подставим в неравенство $$3x_1-5x_2\leq 0$$ координаты точки $$M(1;0)$$ . Так как получили неверное числовое неравенство $$3\leq 0$$ , то решением данного неравенства является часть полуплоскости, не содержащая точку $$M(1;0)$$

Аналогично найдем решения второго и третьего неравенств системы ограничений. 

2. Построим вектор-градиент целевой функции: $$\bar{c}(0,3;2)$$ (рис. 10.5).
3. Построим линию уровня $$F_0=0$$ , проходящую через начало координат перпендикулярно вектору $$\bar{c}$$ .
4. Из рисунка 10.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}$$ . 


Максимальное значение целевой функции определить невозможно, так как ОДЗ – неограниченная область.

Выберите несколько вариантов ответов

Решите графическим методом задачу:

$$min$$$$f(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$$ .

Найдем решение системы неравенств: 

$$\begin{cases} x_1-x_2\leq 0, \\ x_1+x_2\leq 10. \end{cases}$$

Найдем решение первого неравенства системы ограничений. Для этого построим прямую $$x_1-x_2=0$$ (1) (рис. 10.6). Подставим в неравенство $$x_1-x_2\leq0$$ координаты точки $$M(1;0)$$. Так как получили неверное числовое неравенство $$1\leq0$$, то решением данного неравенства является часть полуплоскости, не содержащая точку $$M(1;0)$$.

Найдем решение второго неравенства системы ограничений. Для этого построим прямую $$x_1+x_2=10$$ (2) (рис. 10.6). Подставим в неравенство $$x_1+x_2\leq10$$ координаты точки $$M(1;0)$$. Так как получили верное числовое неравенство $$1\leq10$$, то решением данного неравенства является часть полуплоскости, содержащая точку $$M(1;0)$$.

Найдем координаты точки $$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}$$.
Построим прямую $$x_1=5$$ (3). Так как $$x_1\geq 5$$ , $$x_2\geq 0$$  (рис. 10.7), то ОДЗ: точка $$A(5;5)$$.

Следовательно, оптимальный план: $$X^*=(5;5)$$ . 

Оптимальное значение целевой функции: 

$$f(X^*)=2\cdot 5-3\cdot 5=-5$$ . 


$$f_{min}(X^*)=f_{max}(X^*)=-5$$.

Выберите несколько вариантов ответов