Математические модели задачи /qualihelpy

Математические модели задачи

Справочник / Студент / Линейное программирование /

Справочный материал Примеры Обратите внимание! Видео Модели Пройти тесты

Математическое программирование – область математики, разрабатывающая теорию и численные методы решения задач на экстремум функции многих переменных с ограничениями на область определения этих переменных.

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

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

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

Рассмотрим постановку одной из задач и составим ее математическую модель.

Постановка задачи. Предприятие пытается наладить выпуск n видов продукции: $LaTeX formula: \Pi _{1}, \Pi _{2}, ..., \Pi _{n}.$ Для этого оно располагает LaTeX formula: m

видами ресурсов $LaTeX formula: P_{1},P_{2},...,P_{m},$ объемы которых соответственно составляют: $LaTeX formula: b_{1},b_{2},...,b_{m}.$ Известна прибыль, которую можно получить от реализации одной единицы каждого вида продукции: $LaTeX formula: c_{1},c_{2},...,c_{n}.$ Расход LaTeX formula: j

-го вида ресурса на выпуск одной единицы LaTeX formula: i

-го вида продукции $LaTeX formula: a_{ij}$ представлен в технологической матрице:

$LaTeX formula: A=\begin{pmatrix} a_{11} & a_{12} &... & a_{1n}\\ a_{21} &a_{22} &... & a_{2n}\\ ... &... & ...&... \\ a_{m1} &a_{m2} &... & a_{mn} \end{pmatrix}$ .

Необходимо определить план выпуска продукции, обеспечивающий максимальную прибыль.

Представим данные задачи в таблице:

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

План: $LaTeX formula: X=(x_{1};x_{2};...;x_{n}).$ LaTeX formula: (12.1)

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

$LaTeX formula: max f(X)=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n}.$ LaTeX formula: (12.2)

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

$LaTeX formula: \left\{\begin{matrix} 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{matrix}\right.$ LaTeX formula: (12.3)

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

$LaTeX formula: x_{i}\geq 0, i=\overline{1,n}.$ LaTeX formula: (12.4)

Основные виды записи ЗЛП

Симметричной формой записи называют задачу 12.1 – 12.2 – 12.3 – 12.4 или задачу:

$LaTeX formula: min f(X)=c_{1}x_{1}+c_{2}x_{2}+...+c_{n}x_{n};$ LaTeX formula: (12.5)

$LaTeX formula: \left\{\begin{matrix} 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{matrix}\right.$ LaTeX formula: (12.6)

$LaTeX formula: x_{i}\geq 0, i=\overline{1,n}.$ LaTeX formula: (12.7)

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

$LaTeX formula: max (min) f(X)=\sum_{i=1}^{n}c_{i}x_{i};$ LaTeX formula: (12.8)

$LaTeX formula: \sum_{i=1}^{n}a_{ij}x_{i}=b_{j},$ $LaTeX formula: j=\overline{1,m};$ LaTeX formula: (12.9)

$LaTeX formula: x_{i}\geq 0, i=\overline{1,n}.$ LaTeX formula: (12.10)

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

1) к левым частям неравенств типа $LaTeX formula: \leq$ прибавить неотрицательные дополнительные переменные, а из левых частей неравенств типа $LaTeX formula: \geq$ вычесть неотрицательные дополнительные переменные;

2) в целевую функцию дополнительные переменные ввести с коэффициентами, равными нулю.

Общая форма записи ЗЛП:

$LaTeX formula: max (min) f(X)=\sum_{i=1}^{n}c_{i}x_{i};$ LaTeX formula: (12.11)

$LaTeX formula: \sum_{i=2}^{n}a_{ij}x_{i}=b_{j}, j=\overline{1,k_{1}};$ LaTeX formula: (12.12)

$LaTeX formula: \sum_{i=2}^{n}a_{ij}x_{i}\leq b_{j}, j=\overline{k_{1}+1,k_{2}};$ LaTeX formula: (12.13)

$LaTeX formula: \sum_{i=2}^{n}a_{ij}x_{i}\geq b_{j}, j=\overline{k_{2}+1,m};$ LaTeX formula: (12.14)

$LaTeX formula: x_{i}\geq 0, i=\overline{1,n_{1}};$ $LaTeX formula: x_{i}$ - произвольные, $LaTeX formula: i=\overline{n_{1}+1,n}.$ LaTeX formula: (12.15)

Пример 1. При изготовлении продукции $LaTeX formula: \Pi _{1}$ и $LaTeX formula: \Pi _{2}$ используются токарные и фрезерные станки, а также сталь и цветные металлы. На производство единицы продукции $LaTeX formula: \Pi _{1}$ требуется LaTeX formula: 120

станко-часов соответственно токарного и фрезерного оборудования, а также LaTeX formula: 30

кг стали и LaTeX formula: 5

кг цветных металлов. Для производства единицы продукции $LaTeX formula: \Pi _{2}$ требуется соответственно LaTeX formula: 200, 100, 70

единиц тех же ресурсов. Цех располагает LaTeX formula: 22400

станко-часами оборудования, LaTeX formula: 4800

кг и

кг металлов. Прибыль от реализации единицы продукции $LaTeX formula: \Pi _{1}$ составляет LaTeX formula: 360

тыс. ден. ед., а продукции $LaTeX formula: \Pi _{2}$ – LaTeX formula: 890

тыс. ден. ед. Необходимо определить план выпуска продукции, обеспечивающий максимальную прибыль.

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

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

Составим математическую модель 12.1 – 12.2 – 12.3 – 12.4 данной задачи:

$LaTeX formula: max f(X)=360x_{1}+890x_{2};$

$LaTeX formula: \left\{ \begin{array}{lcl} 120x_{1} +200x_{2}\leq 22400, & & & \\ 210x_{1} +100x_{2}\leq 16800, & & & \\ 30x_{1} +70x_{2}\leq 4800, & & & \\ 5x_{1} +50x_{2}\leq 500; & & & \end{array} \right.$ $LaTeX formula: x_{1}, x_{2}\geq 0.$

Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10 с помощью дополнительных переменных $LaTeX formula: x_{3},x_{4},x_{5}$ и $LaTeX formula: x_{6}$ .
Получим:

$LaTeX formula: max f(X)=360x_{1}+890x_{2}+0\cdot x_{3}+0\cdot x_{4}+0\cdot x_{5}+0\cdot x_{6};$

$LaTeX formula: \left\{ \begin{array}{lcl} 120x_{1} +200x_{2}+x_{3}= 22400, & & & \\ 210x_{1} +100x_{2}+x_{4}= 16800, & & & \\ 30x_{1} +70x_{2}+x_{5}= 4800, & & & \\ 5x_{1} +50x_{2}+x_{6} =500. & & & \end{array} \right. x_{i}\geq 0, i=\overline{1,6}.$

Пример 2. В опытном хозяйстве установили, что откорм животных выгоден тогда, когда животное будет получать в дневном рационе не менее LaTeX formula: 8

ед. питательного вещества LaTeX formula: A,

не менее

ед. вещества LaTeX formula: B

и не менее LaTeX formula: 5

ед. вещества LaTeX formula: C

. Для кормления животных используются три вида корма: $LaTeX formula: K_{1}, K_{2}$ и $LaTeX formula: K_{3}$ .
Составьте математическую модель задачи для определения суточного рациона кормления скота и приведите ее к каноническому виду.
В таблице показано сколько единиц каждого питательного вещества содержит LaTeX formula: 1

кг корма каждого вида:

Решение. Составим математическую модель 12.1 – 12.5 – 12.6 – 12.7 данной задачи:

план закупки корма: $LaTeX formula: X=(x_{1};x_{2},x_{3});$

$LaTeX formula: min f(X)=15x_{1}+18x_{2}+9x_{3};$ $LaTeX formula: \left\{ \begin{array}{lcl} 3x_{1}+x_{2} \geq 8,& & \\ 2x_{1}+4x_{2}+3x_{3} \geq 15, & & \\ 5x_{2}+2x_{3} \geq 5; & & \end{array} \right.$ $LaTeX formula: x_{i}\geq 0, i=\overline{1,3}.$

Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10 с помощью дополнительных переменных $LaTeX formula: x_{4},x_{5}$ и $LaTeX formula: x_{6}$ . Получим:

$LaTeX formula: min f(X)=15x_{1}+18x_{2}+9x_{3}+0\cdot x_{4}+0\cdot x_{5}+0\cdot x_{6};$

$LaTeX formula: \left\{ \begin{array}{lcl} 3x_{1}+x_{2} -x_{4}= 8,& & \\ 2x_{1}+4x_{2}+3x_{3}-x_{5} = 15, & & \\ 5x_{2}+2x_{3}-x_{6} = 5; & & \end{array} \right. x_{i}\geq 0, i=\overline{1,6}.$

Пример 3. В цех распила поступило LaTeX formula: 520

бревен длиной LaTeX formula: 5

м. Их необходимо разрезать на заготовки LaTeX formula: A

длиной соответственно LaTeX formula: 2

м и

м и составить из них комплекты. В каждый комплект входит LaTeX formula: 3

заготовки

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

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

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

План: $LaTeX formula: X=(x_{1};x_{2},x_{3});$ где

$LaTeX formula: x_{1}$ – количество бревен, подлежащих распилу по варианту LaTeX formula: I,

$LaTeX formula: x_{2}$ – количество бревен, подлежащих распилу по варианту LaTeX formula: II,

$LaTeX formula: x_{3}$ – количество бревен, подлежащих распилу по варианту LaTeX formula: III;

$LaTeX formula: x_{1},x_{2},x_{3}\geq 0.$

Целевая функция: $LaTeX formula: min f(X)=1x_{1}+0x_{2}+0,5x_{3}.$

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

$LaTeX formula: \left\{ \begin{array}{lcl} x_{1} +x_{2}+x_{3}\leq 520,& \\ \frac{2x_{1}+x_{2}}{3}=\frac{2x_{2}+x_{3}}{2}& \end{array} \right.$ или $LaTeX formula: \left\{\begin{matrix} x_{1} +x_{2}+x_{3}\leq 520,& \\ 4x_{1}-4x_{2}-9x_{3}=0.& \end{matrix}\right.$

Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10:

$LaTeX formula: min f(X)=1x_{1}+0x_{2}+0,5x_{3}+0x_{4}.$

$LaTeX formula: \left\{ \begin{array}{lcl} x_{1} +x_{2}+x_{3}+x_{4}= 520,& \\ 4x_{1}-4x_{2}-9x_{3}=0.& \end{array} \right.$

$LaTeX formula: x_{i}\geq 0,i=\overline{1,4}.$

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

Н а п р и м е р, приведем модель задачи к каноническому виду:

$LaTeX formula: min (max) f(X)=15x_{1}+18x_{2}+9x_{3};$

$LaTeX formula: \left\{ \begin{array}{lcl} 3x_{1}-x_{2}\geq -8, & & \\ 2 x_{1}-4x_{2}+3x_{3}\geq 15,& & \\ - x_{2}+2x_{3}\leq -5;& & \end{array} \right. x_{i}\geq 0, i=\overline{1,3}.$

Поскольку правые части первого и третьего неравенств системы ограничений отрицательные, то, умножим эти неравенства на число LaTeX formula: -1

и получим:

$LaTeX formula: \left\{ \begin{array}{lcl}-3x_{1}+x_{2}\leq 8, & & \\ 2 x_{1}-4x_{2}+3x_{3}\geq 15,& & \\ x_{2}-2x_{3}\geq 5.& & \end{array} \right.$

Приведем модель задачи к каноническому виду 12.8 – 12.9 – 12.10:

$LaTeX formula: min(max) f(X)=15x_{1}+18x_{2}+9x_{3}+0\cdot x_{4}+0\cdot x_{5}+0\cdot x_{6};$

$LaTeX formula: \left\{ \begin{array}{lcl} -3x_{1}+x_{2}+x_{4}= 8, & & \\ 2 x_{1}-4x_{2}+3x_{3}-x_{5}= 15,& & \\ x_{2}-2x_{3}-x_{6}= 5.& & \end{array} \right. x_{i}\geq 0, i=\overline{1,6}.$

Программа для просмотра моделей (МК-плеер) Файлы для скачивания

Математические модели задачи