Математическая модель задачи ИТ
Для кондитерского цеха требуется рассчитать оптимальный план выпуска печенья двух видов: $$\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)=c_1\cdot x_1+c_2\cdot x_2+…+c_n\cdot x_n$$. - Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\leq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\leq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\leq b_m. \end{cases}$$ - Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
$$c_i$$ $$(i=\overline{1, n})$$ – прибыль от реализации одной единицы каждого вида продукции;
$$a_{ji}$$ – расход $$j$$-го вида ресурса на выпуск одной единицы $$i$$-го вида продукции.
Составим таблицу данных:
|
Ресурсы |
Выпускаемая продукция |
Запас ресурса (кг) |
|
|
П1 |
П2 |
||
|
мука |
0,4 |
0,6 |
150 |
|
сахар |
0,3 |
0,2 |
60 |
|
масло
|
0,2 |
0,1 |
40 |
|
Прибыль от выпуска 1 кг печенья (ден. ед.) |
15 |
10 |
|
|
План выпуска (кг) |
x1 |
x2 |
|
Составим математическую модель задачи.
- План выпуска продукции: $$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$$.
- Математической моделью задачи называют отражение реальной (производственной, экономической) ситуации в виде функций, уравнений и неравенств.
- Линейным программированием (ЛП) называют раздел математического программирования, если все функции математической модели задачи линейные.
Выберите несколько вариантов ответов
Приведите модель задачи к предпочтительному виду:
$$max f(x)=5x_1+x_2+x_3$$;
$$\begin{cases} 4x_1-x_3\leq 15, \\ x_1+x_2\leq 6, \\ 2x_2+x_3\leq 4; \end{cases}$$
$$x_i\geq 0$$, $$i=\overline{1, 3}$$.
1. Чтобы привести модель задачи к каноническому виду, необходимо:
1) к левым частям неравенств типа $$\leq$$ прибавить неотрицательные дополнительные переменные;
2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
2. Каноническая модель ЗЛП имеет предпочтительный вид, если в каждом из уравнений системы ограничений присутствует предпочтительная переменная.
Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.
1. Приведем модель задачи к каноническому виду с помощью дополнительных переменных $$x_4$$, $$x_5$$ и $$x_6$$.
В целевую функцию дополнительные переменные введем с коэффициентами, равными нулю:
$$max f(x)=5x_1+x_2+x_3+0x_4+0x_5+0x_6$$.
К левой части первого неравенства системы ограничений прибавим переменную $$x_4$$, к левой части второго неравенства прибавим переменную $$x_5$$, а к левой части третьего неравенства – переменную $$x_6$$:
$$\begin{cases} 4x_1-x_3+x_4=15, \\ x_1+x_2+x_5=6, \\ 2x_2+x_3+x_6=4; \end{cases}$$
$$x_i\geq 0$$, $$i=\overline{1, 6}$$.
2. Математическая модель задачи имеет предпочтительный вид, так как в каждом уравнении системы ограничений есть предпочтительная переменная.
В первом уравнении системы ограничений предпочтительной является переменная $$x_4$$, так как она присутствует только в этом уравнении и ее коэффициент равен числу $$1$$.
Во втором уравнении системы ограничений предпочтительной является переменная $$x_5$$, так как она присутствует только в этом уравнении и ее коэффициент равен числу $$1$$.
В третьем уравнении системы ограничений предпочтительной является переменная $$x_6$$, так как она присутствует только в этом уравнении и ее коэффициент равен числу $$1$$.
Если в канонической модели задачи отсутствуют предпочтительные переменные, то вводим неотрицательные искусственные переменные.
В целевую функцию искусственные переменные в случае ее максимизации вводим с коэффициентом $$–M$$, а в случае минимизации – с коэффициентом $$+M$$.
Выберите несколько вариантов ответов
Выполнять заказ по производству $$35$$ изделий первого вида и $$40$$ изделий второго вида взялись две бригады. Производительность первой бригады составляет соответственно $$4$$ и $$2$$ изделия в единицу времени, а фонд рабочего времени этой бригады $$10$$ ед. Производительность второй бригады – соответственно $$2$$ и $$5$$ изделий, а ее фонд рабочего времени – $$15$$ ед. Затраты, связанные с производством единицы изделия, для первой бригады равны соответственно $$9$$ и $$20$$ тыс. ден. ед. , для второй бригады – $$15$$ и $$30$$ тыс. ден. ед. Найдите оптимальный план размещения заказа при условии, что фонд рабочего времени первой бригады должен быть использован полностью.
Математическая модель задачи имеет вид:
Математическая модель задачи о размещении заказа
План: $$X=(x_1; x_2; . . . ; x_n)$$.
Целевая функция качества:
$$min f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\leq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\leq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\leq b_m. \end{cases}$$
Условия не отрицательности переменных:
$$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;x_4)$$ ;
целевая функция:
$$minf(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$$.
Выберите несколько вариантов ответов
Приведите к предпочтительному виду модель задачи:
$$minf(X)=x_1+5x_3$$;
$$\left\{\begin{array}{lr} x_1+6x_3=11,\\ 15x_1+x_2\geq0,\\ x_1+3x_3\leq-7; \end{array}\right.$$
$$x_i\geq0$$, $$i=\overline{1;3}$$.
1. Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо из левых частей неравенств типа $$\geq$$ вычесть неотрицательные дополнительные переменные, а в в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
2. Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.
3. Если в канонической модели задачи отсутствуют предпочтительные переменные, то вводим неотрицательные искусственные переменные. В целевую функцию искусственные переменные в случае ее минимизации вводим с коэффициентом, равным $$+M$$.
1. Преобразуем второе неравенство системы ограничений. Умножим обе его части на число $$-1$$ и изменим смысловой знак неравенства:
$$-x_1-3x_3\geq7$$.
2. Приведем модель задачи к каноническому виду с помощью неотрицательных дополнительных переменных $$x_4$$ и $$x_5$$.
Целевая функция:
$$f(X)=x_1+5x_3+0 \cdot x_4+0 \cdot x_5$$.
Система ограничений:
$$\left\{\begin{array}{lr} x_1+6x_3=11, \\ 15x_1+x_2\geq0, \\ -x_1-3x_3\geq7; \end{array}\right.$$$$\left\{\begin{array}{lr} x_1+6x_3=11, \\ 15x_1+x_2-x_4=0, \\ -x_1-3x_3-x_5=7. \end{array}\right.$$
3. Приведем модель задачи к предпочтительному виду с помощью неотрицательных искусственных переменных $$\omega_1$$ и $$\omega_2$$.
Целевая функция:
$$minf(X)=x_1+5x_3+0x_4+x_5+M\omega_1+M\omega_2$$.
Система ограничений:
$$\left\{\begin{array}{lr} x_1+6x_3+\underline{\omega_1}=11, \\ 15x_1+\underline{x_2}-x_4=0, \\ -x_1-3x_3-x_5+\underline{\omega_2}=7. \end{array}\right.$$
Условия не отрицательности переменных:
$$x_i\geq0$$, $$i=\overline{1; 5}$$; $$\omega_1\geq0$$, $$\omega_2\geq0$$.
В целевую функцию обе искусственные переменные входят с одним и тем же коэффициентом $$+M$$.
Выберите несколько вариантов ответов
На швейной фабрике для пошива трех моделей женских костюмов используется хлопок, лен и вискоза. На производство $$1$$ ед. модели $$M_1$$ требуется $$2,4$$ м хлопка, $$0,5$$ м льна и $$0,3$$ м вискозы. На производство $$1$$ ед. модели $$M_2$$ требуется соответственно $$0,2$$ м, $$1,8$$ м и $$1$$ м тех же тканей. А на производство $$1$$ ед. модели $$M_3$$ требуется $$1,2$$ м хлопка и $$2,5$$ м льна. Цех располагает $$100$$ м хлопка, $$350$$ м льна и $$50$$ м вискозы. Прибыль от реализации $$1$$ ед. модели $$M_1$$ составляет $$150$$ ден. ед., модели $$M_2$$ – $$220$$ ден. ед., а модели $$M_3$$ – $$390$$ ден. ед.
Составьте математическую модель задачи, на основании которой можно определите план выпуска продукции, обеспечивающий максимальную прибыль, и приведите ее к каноническому виду.
Математическая модель задачи о планировании производства
План: $$X=(x_1; x_2; . . . ; x_n)$$.
Целевая функция качества:
$$max f(X)=c_1\cdot x_1+c_2\cdot x_2+…+c_n\cdot x_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\leq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\leq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\leq b_m. \end{cases}$$
Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
Где: $$b_j$$ $$(j=\overline{1, m})$$ – объемы ресурсов;
$$c_i$$ $$(i=\overline{1, n})$$ – прибыль от реализации одной единицы каждого вида продукции;
$$a_{ji}$$ – расход $$j$$-го вида ресурса на выпуск одной единицы $$i$$-го вида продукции.
1. Составим таблицу данных:
|
Ресурсы |
Выпускаемая
продукция |
|
||
|
М1 |
М2 |
М3 |
Запас
ресурса |
|
|
Хлопок
(м) |
2,4 |
0,2 |
1,2 |
100 |
|
Лен
(м) |
0,5 |
1,8 |
2,5 |
350 |
|
Вискоза
(м) |
0,3 |
1 |
0 |
50 |
|
Прибыль
(ден. ед.) |
150 |
220 |
390 |
|
|
План
|
х1 |
х2 |
х3 |
|
2. Составим математическую модель задачи.
План выпуска продукции:
$$X=(x_1; x_2; x_3)$$.
Целевая функция (максимизация прибыли):
$$max f(X)=150x_1+220x_2+390x_3$$.
Система ограничений:
$$\begin{cases} 2,4x_1+0,2x_2+1,2x_3\leq 100, \\ 0,5x_1+1,8x_2+2,5x_3\leq 350, \\ 0,3x_1+x_2\leq 50. \end{cases}$$
Условия не отрицательности переменных:
$$x_1\geq 0$$, $$x_2\geq 0$$, $$x_3\geq 0$$.
3. Приведем модель задачи к каноническому виду, вводя неотрицательные дополнительные переменные $$x_4$$, $$x_5$$ и $$x_6$$:
$$max f(X)=150x_1+220x_2+390x_3+0x_4+0x_5+0x_6$$;
$$\begin{cases} 2,4x_1+0,2x_2+1,2x_3+x_4=100, \\ 0,5x_1+1,8x_2+2,5x_3+x_5=350, \\ 0,3x_1+x_2+x_6=50; \end{cases}$$
$$x_i\geq 0$$, $$i=\bar{1,6}$$.
1. Канонический вид математической модели задачи.
План: $$X=(x_1; x_2; . . . ; x_n)$$.
Целевая функция качества:
$$max (min) f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n=b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n=b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n=b_m. \end{cases}$$
Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
2. Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:
1) к левым частям неравенств типа $$\leq$$ прибавить неотрицательные дополнительные переменные;
2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
Выберите несколько вариантов ответов
Дневной рацион корма зверей в зоопарке должен содержать не менее $$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)=c_1\cdot x_1+c_2\cdot x_2+…+c_n\cdot x_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\geq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\geq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\geq b_m. \end{cases}$$
Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
Где: $$b_j$$ $$(j=\overline{1, m})$$ – объемы ресурсов;
$$c_i$$ $$(i=\overline{1, n})$$ – затраты на одну единицу каждого вида продукции;
$$a_{ji}$$ – содержание $$j$$-го вида ресурса в одной единице $$i$$-го вида продукции.
Составим таблицу данных:
|
Питательные
вещества |
Корм |
Кол-во
вещества
|
||
|
К1 |
К2 |
К3 |
||
|
А |
3 |
1 |
4 |
25 |
|
В |
2 |
6 |
2 |
45 |
|
С |
0 |
5 |
1 |
32 |
|
Стоимость 1 кг корма (ден. ед.) |
50 |
60 |
40 |
|
|
План кормления (кг) |
x1 |
x2 |
x3 |
|
Составим математическую модель задачи.
План кормления: $$X=(x_1;x_2;x_3)$$.
Целевая функция:
$$minf(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$$ .
Симметричные формы записи задач:
- $$X=(x_1; x_2; . . . x_n)$$; $$maxf(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}$$;
- $$X=(x_1; x_2; . . . x_n)$$; $$minf(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}$$.
Выберите несколько вариантов ответов
Приведите к каноническому виду модель задачи:
$$minf(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. Канонический вид математической модели задачи.
План: $$X=(x_1; x_2; . . . ; x_n)$$.
Целевая функция качества:
$$max (min) f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n=b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n=b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n=b_m. \end{cases}$$
Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
2. Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:
1) из левых частей неравенств типа $$\geq$$ вычесть неотрицательные дополнительные переменные;
2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
Преобразуем второе неравенство системы ограничений, так как его правая часть отрицательная. Умножим обе части этого неравенства на число $$–1$$, изменив при этом смысловой знак неравенства:
$$x_1-x_2\leq -2$$, $$-x_1+x_2\geq 2$$.
Приведем модель задачи к каноническому виду, вводя дополнительные переменные $$x_3$$ и $$x_4$$.
В целевую функцию дополнительные переменные введем с коэффициентами, равными нулю:
$$min f(X)=3x_1-x_2+0\cdot x_3+0\cdot x_4$$.
Из левой части первого неравенства системы ограничений вычтем переменную $$x_3$$, а из левой части второго неравенства вычтем переменную $$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}$$.
1. Приводить модель задачи к каноническому виду можно только при условии, что все правые части неравенств-ограничений неотрицательные.
2. Дополнительные переменные можно вводить только в левые чести неравенств-ограничений.
Выберите несколько вариантов ответов
В цех распила поступило $$600$$ бревен длиной $$6$$ м. Их необходимо разрезать на заготовки $$A$$ и $$B$$ длиной соответственно $$2,5$$ м и $$3$$ м и составить из них комплекты. В каждый комплект входит $$4$$ заготовки $$A$$ и $$5$$ заготовок $$B$$. Составьте план распила бревен, гарантирующий минимизацию отходов.
Математическая модель задачи имеет вид:
Математическая модель задачи о распиле
План: $$X=(x_1; x_2; . . . ; x_n)$$.
Целевая функция качества (минимизация отходов):
$$min f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\geq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\geq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\geq b_m. \end{cases}$$
Ограничения на объем исходного материала:
$$x_1+x_2+…+x_n\leq N$$.
Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
Где: $$N$$ – объем исходного материала;
$$x_i$$ – количество единиц исходного материала, планируемое к распилу по каждому из вариантов;
$$b_j$$ $$(j=\overline{1, m})$$ – количество заготовок каждого вида;
$$c_i$$ $$(i=\overline{1, n})$$ – отходы от распила одной единицы исходного материала по каждому из вариантов;
$$a_{ji}$$ – количество $$j$$-го вида заготовок, полученных от распила одной единицы исходного материала по $$i$$-му варианту распила.
Составим таблицу данных:
|
Заготовки |
Длина заготовок |
Варианты
распила |
Кол-во заготовок |
Кол-во комплектов |
||
|
I |
II |
III |
||||
|
А |
2,5
м |
2 шт. |
1
шт. |
0
шт. |
2x1+x2 |
(2x1+x2):4 |
|
Б |
3
м |
0
шт. |
1
шт. |
2
шт. |
x2+2x3 |
(2x1+x2):5 |
|
Отходы |
1м |
0,5
м |
0
м |
|
|
|
|
План распила |
x1 |
x2
|
x3 |
|
|
|
Составим математическую модель задачи.
План: $$X=(x_1;x_2;x_3)$$, где
$$x_1$$ – количество бревен, подлежащих распилу по варианту I,
$$x_2$$ – количество бревен, подлежащих распилу по варианту II,
$$x_3$$ – количество бревен, подлежащих распилу по варианту III,
$$x_1$$, $$x_2$$, $$x_3$$ – целые неотрицательные числа.
Целевая функция:
$$min f(X)=1x_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}$$
К основным видам задач ЛП, как правило, относят: задачи о наилучшем использовании ресурсов, задачи о выборе оптимальных технологий, задачи о размещении заказа, задачи о смесях, задачи о раскрое материалов, транспортные задачи и т. п.
Выберите несколько вариантов ответов
Приведите к предпочтительному виду модель задачи:
$$maxf(X)=3x_1-x_2+5x_3$$;
$$\left\{\begin{matrix} x_1+3x_2=5, \\ x_2-x_3=16;\end{matrix}\right. $$
$$x_i \geq0$$, $$i=\overline{1; 3}$$.
Каноническая модель ЗЛП имеет предпочтительный вид, если в каждом из уравнений системы ограничений присутствует предпочтительная переменная.
Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.
Если в канонической модели задачи отсутствуют предпочтительные переменные, то вводим неотрицательные искусственные переменные.
В целевую функцию искусственные переменные в случае ее максимизации вводим с коэффициентом, равным $$–M$$.
Модель задачи уже имеет канонический вид.
Приведем эту модель к предпочтительному виду:
1) в первом уравнении системы ограничений есть предпочтительная переменная $$x_1$$;
2) так как во втором уравнении системы ограничений отсутствует предпочтительная переменная, то вводим искусственную переменную $$\omega \geq0$$;
3) в целевую функцию переменную $$\omega$$ вводим с коэффициентом, равным $$–M$$.
Получим:
$$maxf(X)=3x_1-x_2+5x_3-M\omega$$;
$$\left\{\begin{array}{lr} \underline{x_1}+3x_2=5, \\ x_2-x_3+\underline{\omega}=16. \end{array}\right. $$
Во втором уравнении $$x_2-x_3=16$$ переменная $$x_2$$ не является предпочтительной, так как она присутствует в первом уравнении системы ограничений. А переменная $$x_3$$ не является предпочтительной, так как она имеет коэффициент $$-1$$.
Выберите несколько вариантов ответов
Приведите к каноническому виду модель задачи:
$$maxf(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. Канонический вид математической модели задачи.
План: $$X=(x_1; x_2; . . . ; x_n)$$.
Целевая функция качества:
$$max (min) f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n=b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n=b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n=b_m. \end{cases}$$
Условия не отрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
2. Чтобы привести модель задачи к каноническому виду, при условии, что все правые части неравенств-ограничений неотрицательные, необходимо:
1) к левым частям неравенств типа $$\leq$$ прибавить неотрицательные дополнительные переменные;
2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.
Приведем модель задачи к каноническому виду с помощью дополнительных переменных $$x_3$$ и $$x_4$$.
В целевую функцию дополнительные переменные введем с коэффициентами, равными нулю:
$$max f(X)=3x_1-x_2+0\cdot x_3+0\cdot x_4$$.
К левой части первого неравенства системы ограничений прибавим переменную $$x_3$$, а к левой части второго неравенства прибавим переменную $$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}$$ .
Выберите несколько вариантов ответов