Цель лекции. Научить строить математическую модель оптимизационных задач средствами Mathcad. Выделять управляемые переменные, целевую функции. ограничения, затем строить систему уравнений. Применять блок given - maximize (minimize) для решения матричных уравнений. Анализировать полученное решение. Строить графики результата.
Принятию любого экономического или финансового решения предшествует перебор и оценка вариантов. Экономико-математические задачи, цель которых состоит в нахождении наилучшего (оптимального) с точки зрения некоторого критерия или критериев варианта использования имеющихся ресурсов (труда, капитала и пр.), называются оптимизационными [18, 19].
Типы оптимизационных задач в экономике:
Оптимизационные задачи решаются с помощью оптимизационных моделей. Оптимизационные модели возникают при практической реализации принципа оптимальности в управлении. В каждом случае выделяется объект оптимизации, определяется цель оптимизации, ставится задача нахождения экстремума функции, описывающей оптимизируемую цель при заданных условиях. Структура оптимизационной модели состоит из целевой функции, области допустимых решений и системы ограничений, определяющих эту область. В качестве инструмента используется математическое программирование (планирование): линейное, нелинейное, динамическое, и т.п. В зависимости от типа переменных и функциональных связей различают задачи линейного и нелинейного программирования. Многие экономические задачи формулируются в терминах линейного программирования, поскольку функции прибыли, стоимости затрат - линейные функции переменных, связанных с объемами выпуска, продаж и других факторов.
В общем виде задача линейного программирования ЗЛП ставится следующим образом: найти вектор $$\overline{X}=(x_1,x_2,...,x_n)$$, максимизирующий (минимизирующий) линейную форму $$f(\overline{X})=\sum_{j=1}^{n}c_jx_j\to \max (\min)$$, удовлетворяющий условиям:
$$\sum_{j=1}^{n}a_{ij}\le b_i$$
$$x_j\ge 0,\;j=1..n$$
где $$f$$ — заданная функции, $$a_{ij},\; b_i$$ — некоторые действительные числа.
Линейная функция $$f(\overline{X})$$ - целевая функция задачи, условия ( 4.1) (4.2) - ограничения задачи, вектор $$\overline{X}=(x_1,x_2,...,x_n)$$, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, называется планом или допустимым решением ЗЛП. Допустимое решение, максимизирующее (минимизирующее) целевую функцию $$f(\overline{X})$$ , называется оптимальным планом задачи: $$f(\overline{X^*})=\max \; f(\overline{X})$$ (или $$\min$$) где $$\overline{X^*}=(x^*_1,x^*_2,...,x^*_n)$$ - оптимальное решение ЗЛП.
В оптимизационной задаче экономический показатель, для которого определяется максимальное или минимальное значение - целевая функция. Управляемые переменные - аргументы целевой функции - переменные задачи, которые подвергаются изменению в процессе поиска решения. Область допустимых решений – это область, в пределах которой осуществляется выбор решений. В экономических задачах она ограничена наличными ресурсами, условиями, которые записываются в виде системы ограничений, состоящей из уравнений и неравенств.
Приведем примеры экономико-математического моделирования оптимизационных задач средствами Mathcad.
Рассмотрим классическую задачу формирования производственной программы [20,21,22]. Пусть осуществляется выпуск $$m$$ видов продукции. Для этого используется n основных видов ресурсов $$B$$, (механизмов, оборудования, времени, специалистов), объем которых на предприятии задан. Известно количество каждого ресурса, идущего на выпуск единицы продукции каждого вида. Отдельная продукция реализуется по цене c, норма переменных затрат для нее составляет $$q$$. Необходимо, чтобы производственная программа была оптимальна и давала наибольшую валовую прибыль,
Постановка задачи. Цель моделирования – получить максимальную прибыль, которая определяется количеством произведенной продукции в имеющихся условиях с учетом всех ограничений. Найти вариант из множества возможных.
Модель задачи
Определение переменных. Введем обозначения:
Входные переменные:
$$m$$ –видов продукции, $$j$$ – текущий номер вида продукции.
$$c_j$$ - прибыль от реализации единицы $$j$$-го вида продукции.
$$q_j$$ - переменные затраты производства единицы $$j$$-го вида продукции
$$В_i$$ - запасы $$i$$-го ресурса $$i$$ – текущий номер вида ресурса, $$m$$ - количество ресурсов.
$$а_{ij}$$ - норма затрат $$i$$ го ресурса для производства $$j$$-го вида продукции
$$Р_j$$ – требуемое количество выпуска продукции каждого вида по плану,
Выходные показатели – суммарная прибыль $$Z(x_1, x_2, x_3,… x_m)$$,
Управляемые переменные. $$x_j$$ - искомый объем продукции $$j$$-го вида.
Целевая функция – показатель, который определяет цель моделирования - результирующий, оптимизируемый параметр – прибыль. Цель решения задачи – нахождение значений управляемых переменных $$x_j$$, доставляющих экстремум целевой функции прибыли $$Z$$.
$$Z(x_j)=\sum_{j=1}^{m}(c_j-q_j)\cdot x_j, \; j=\overline{1,m}$$
$$Z(x_j)\to \max \; j=\overline{1,m}$$
Ограничения. условия, налагаемые на данные задачи, определяющие исследуемую величину, которая оптимизируется. Различают три типа ограничений:
Ресурсные ограничения - ограниченность имеющихся ресурсов; обеспечивающих выпуск:
$$a_{ij}\cdot x_j$$ – планируемые затраты ресурса $$i$$ для производства продукции $$j$$ ,
$$\sum_{j}^{m}a_{ij}\cdot x_j$$ – планируемые затраты ресурса $$i$$ на производство всех видов продукции,
$$\sum_{j}^{m}a_{ij}\cdot x_j \le B_i \; i=\overline{1,n}$$ - условие ограниченности ресурсов
плановые ограничения - необходимость выполнения заданных значений $$P_j$$ для искомых объемов продукции $$j$$-го вида:
$$x_j\ge P_j\; j=\overline{1,m}$$ - условие ограниченности по плану
технологические соотношения между группами управляемых переменных, здесь
$$x_j\ge 0\; j=\overline{1,m}$$
Уравнения. В результате имеем систему уравнений, которую надо решить.
$$ \left\{ \begin{array}{lc} a_{ij}\cdot x_j\le B_i \\ x_j\ge P_j\\ x_j\ge 0 \\ Z(x_j)\to\max \; j=\overline{1,m} \end{array} \right\ $$
Решение, если получено, представляется в виде оптимального решения. Это:
количество управляемых переменных, не равных нулю,
числовые значения управляемых переменных,
полученное значение целевой функции
Рассмотрим решение модели на примере следующей задачи.
Задача. 4.1.
Фирма по сборке компьютеров предполагает производить выпуск 3 новых моделей при использовании комплектующих 5 типов. Маркетинговые исследования показали возможность сбыта компьютеров по приемлемым продажным ценам. Необходимые данные по запасам комплектующих, и ценам приведены в таблице. Определить оптимальные объемы выпуска компьютеров при имеющихся ресурсах для получения максимальной прибыли.
| Вид комплектующих | Расход комплектующих ед./изд. Модели ПК | Запас комплектующих. (ед.) | ||
| Модель 1 | Модель 2 | Модель 3 | ||
| 1 | 4 | 6 | 5 | 240 |
| 2 | 1 | 3 | 4 | 145 |
| 3 | 5 | 2 | 3 | 155 |
| 4 | 2 | 2 | 2 | 60 |
| 5 | 1 | 2 | 3 | 70 |
| Затраты на 1 изд. | 1800 | 2700 | 2100 | |
| Цена реализации(усл.ед.) | 10000 | 35000 | 20000 | |
Решение задачи 4. 1.
Применяем модель, описанную выше. В Mathcad система уравнений с оптимизацией решается численно с помощью блока $$given$$ и функции $$maximize\; (miniimize)$$. Задачу решаем в матричном виде: все данные и уравнения представляем в виде матриц. Порядок действий:
Входные данные
$$\underline{c}:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$\underline{q}:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$\underline{d}:=\underline{c}-\underline{q}$$ - прибыль на один компьютер
$$\underline{Z}(\underline{x})$$ - прибыль
Затраты ресурсов: $$\underline{a}:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Запасы ресурсов: $$\underline{B}:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \\ \end{pmatrix}$$
Начальное значение: $$\underline{x}:=\begin{pmatrix} 1\\ 1\\ 1 \\ \end{pmatrix}$$
$$\underline{Z}(\underline{x}):=\underline{d}\cdot \underline{x}$$
$$\underline{Given}$$
$$\underline{a} \cdot \underline{x}\le B$$
$$\underline{x} \ge 0$$
$$\underline{x}:=\underline{Maximize}(\underline{Z},\underline{x})$$, $$\underline{x}:=\begin{pmatrix} 0\\ 30\\ 0 \\ \end{pmatrix}$$
Максимальная прибыль: $$\underline{Z}(\underline{x})=969000$$
Остаток комплектующих: $$\underline{B}-\underline{a}\cdot \underline{x}:=\begin{pmatrix} 60\\ 55\\ 95 \\ 0 \\10 \\ \end{pmatrix}$$
Оптимальный выпуск компьютеров (рис.4.1):
Продукция: $$\underline{x}^T$$
Ресурсы: $$\underline{B2}:=\underline{a}\cdot \underline{x}$$
$$\underline{B}^T,\;\underline{B2}^T$$
(рис 4.1) Графики к задаче 4.1. Количество компьютеров и распределения ресурсов
Полученное оптимальное решение (рис. 4.1) следующее. Оптимальная структура выпуска при имеющихся ресурсах без задания плана – 30 компьютеров 2 модели, прибыль при этом составляет 969000 ед. ; 4 вид комплектующих израсходован полностью – это дефицитный ресурс. Остальные ресурсы имеют остаток, они недефицитные.
Проведем экономический анализ: как меняется прибыль при изменении структуры выпуска. Ниже показаны листинги расчета нормированной стоимости. Полученные результаты приведены в таблице. Нормированная стоимость – изменение целевой функции при изменении соответствующего управляемого параметра (количество выпускаемого продукта) на единицу. Нормированная стоимость для модели 1 в 1,7 больше, чем для модели 3.
| Переменная | Результирующее значение | Целевой коэффициент | Нормированная стоимость |
| x1 | 0 | 8200 | 24100 |
| x2 | 30 | 32300 | 0 |
| x3 | 0 | 17900 | 14400 |
$$ORIGIN:=1$$
Увеличим 1 вид продукции на 1 единицу.
$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$, $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \\ \end{pmatrix}$$, $$d:=\begin{pmatrix} 8200 32300 17900 \end{pmatrix}$$, $$x:=\begin{pmatrix} 1\\ 1\\ 1 \\ \end{pmatrix}$$
$$Z(x):=d\cdot x$$, $$Z0:=969000$$, $$ZN(x):=Z0-Z(x)$$ – нормированная стоимость
$$Given$$
$$a\cdot x \le B$$
$$x \ge 0 \; x1 \ge 1$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 1 \\ 29 \\ 0 \end{pmatrix}$$
$$Z(x1):=9.449\times 10^5$$, $$ZN(x1):=24100$$
Остаток ресурсов: $$B-a\cdot x:=\begin{pmatrix} 225 \\ 137\\ 145 \\ 54 \\64 \end{pmatrix}$$
Увеличим 2 вид продукции на 1 единицу
$$Given$$
$$a\cdot x \le B$$
$$x \ge 0 \; x2 \ge 1$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 0 \\ 30 \\ 0 \end{pmatrix}$$
$$Z(x1):=969000$$, $$ZN(x1):=0$$
Остаток ресурсов: $$B-a\cdot x:=\begin{pmatrix} 225 \\ 137\\ 145 \\ 54 \\64 \end{pmatrix}$$
Увеличим 3 вид продукции на 1 единицу
$$Given$$
$$a\cdot x \le B$$
$$x \ge 0 \; x3 \ge 1$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 0 \\ 29 \\ 1 \end{pmatrix}$$
$$Z(x1):=954600$$, $$ZN(x1):=14400$$
Остаток ресурсов: $$B-a\cdot x:=\begin{pmatrix} 225 \\ 137\\ 145 \\ 54 \\64 \end{pmatrix}$$
Задача. 4.2.
Фирма по сборке компьютеров (см. задачу 4.1) получила заказ на следующий выпуск компьютеров: 1 модель - не менее 8 шт., 2 модель- не менее 10 шт., 3 модель- не менее 3 шт. Данные по запасам комплектующих и ценам приведены в таблице 4.1. Определить прибыль при заданном плане и имеющихся ресурсах. Можно ли выполнить такой план ?
Решение. Задан план выпуска. Схема решения в программе Mathcad аналогична. Задача имеет решение. Ресурсов достаточно - план выполняется. Структура выпуска – заданный план. Но прибыль составляет $$7333000/969000=0,75$$ от оптимальной.. Дефицитным является 4 вид комплектующих.
Входные данные
$$Z(x)$$ – прибыль
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 8 \\ 15 \\ 3 \end{pmatrix}$$ - план выпуска
Матрица затрат ресурсов: $$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$
$$Z(x):=d\cdot x$$
$$Given$$
$$a\cdot x \le B$$
$$x \ge P$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 8 \\ 19 \\ 3 \end{pmatrix}$$
Прибыль: $$Z(x1):=733000$$
Остаток ресурсов: $$B-a\cdot x1:=\begin{pmatrix} 79 \\ 68\\ 68 \\ -0 \\15 \end{pmatrix}$$
Задача. 4.3.
Фирма по сборке компьютеров (см. задачу 4.1) получила заказ на увеличенный план выпуска компьютеров : 1 модель- 40 шт., 2 модель- 20 шт., 3 модель- 10 шт. Данные по запасам комплектующих и ценам приведены в таблице 4.1. Определить оптимальную прибыль при заданном плане и имеющихся ресурсах. Можно ли выполнить такой план ?
Решение. Для увеличенного плана выпуска задача не имеет решения, система несовместна. Экономическая причина – требуемые значения плана ($$P_j$$) недостижимы при имеющихся запасах ресурсов ($$B_i$$).
Входные данные
$$Z(x)$$ – прибыль
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$ - план выпуска
Матрица затрат ресурсов: >$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$
$$Z(x):=d\cdot x$$
$$Given$$
$$a\cdot x \le B$$
$$x \ge P$$
$$x1:=Maximize(Z,x)$$
$$x1:= \Box $$
Прибыль: $$Z(x1):= \Box$$
Остаток ресурсов: $$B-a\cdot x1:= \Box$$
Возможны два пути решения проблемы:
Решение задачи 4.3 в комплектной постановке. Задача - определить, какую часть плана можно выполнить при имеющихся ресурсах. Для этого случая воспользуемся моделью, приведенной в [21]. Ставится цель определения максимальной доли выпуска требуемого плана при имеющихся ресурсах. Разработана quot;комплектнаяquot; постановка задачи. Вводится новая переменная $$y$$ – возможный процент достижения плана, определяется ее оптимальное значение при уменьшенном плане, ресурсные и технологические ограничения задачи записываются без изменений.: Целевая функция $$K(y,x_j )$$ строится как функция двух аргументов: скаляра $$y$$ и вектора переменных продукции $$x_j,\;j=\overline{1,m}$$, который неявно зависит от $$y$$. .Решение получается в виде вектора $$y1$$ с элементами $$y1_1$$ - .найденная доля выполнения плана и $$y1_2$$.- найденный вектор переменных продукции.
Система уравнений в quot;комплектнойquot; постановке
$$ \left\{ \begin{array}{lc} K(x_j,y)\to\max \sum_{j}^{m}a_{ij}\cdot x_j\le B_i \\ x_j\ge P_j\cdot y\\ x_j\ge 0 \\ \end{array} \right\ $$
Ниже приведен листинг решения в MathCad (комплектная постановка).
Входные данные
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$ - план выпуска
$$Z(x)$$ – прибыль
Матрица затрат ресурсов: >$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$, $$y:=1$$
Решение:
$$Z(x):=d\cdot x$$
$$K(y,x):=y$$ – целевая функция
$$Given$$
$$a\cdot x \le B$$
$$x \ge P \cdot y$$
$$y1:=Maximize(K,y,x)$$, $$y1:=\begin{pmatrix} 0.429\\ \{3.1\} \end{pmatrix}$$
Доля плана: $$y1_1=0.43$$
Количество выпуска: $$y1_2:=\begin{pmatrix} 17 \\ 9\\ 4 \end{pmatrix}$$
Прибыль: $$Z(y1_2):= 494143$$
Израсходовано ресурсов: $$a\cdot y1_2:=\begin{pmatrix} 141 \\ 60\\ 116 \\ 60 \\ 47 \end{pmatrix}$$
Остаток ресурсов: $$B-a\cdot y1_2:=\begin{pmatrix} 99\\ 85\\ 39\\ 0\\23\end{pmatrix}$$
Как видно, план можно выполнен только на 43%, но это оптимальный процент при имеющихся условиях. Полученная прибыль при таком плане еще меньше, чем в задаче 4.2 и ресурсов остается больше.
Решение задачи 4.3 с добавлением ресурсов. Добавление недостающих ресурсов для выполнения полного плана. Воспользуемся t-моделью постановки задачи, представленной в [21], - нахождения минимума дополнительного количества ресурсов, необходимых для выпуска продукции в соответствии с планом. В предлагаемой t-модели вводятся новые переменные $$t_i,\;i=\overline{1,n}$$ – значения дополнительных ресурсов каждого вида продукции $$i$$. Цель задачи – минимум суммарного количества добавляемых ресурсов. В ресурсные ограничения вводятся дополнительные неизвестные ресурсы, плановые и технологические ограничения вводятся в t-модель без изменений. Целевая функция $$T(x,t)$$ вводится как функция двух аргументов: вектора добавочных ресурсов $$t_i,\;i=\overline{1,n}$$ и вектора переменных продукции $$x_j,\;j=\overline{1,m}$$ , который неявно зависит от $$t_j$$
Система уравнений в постановке t -модели
$$ \left\{ \begin{array}{lc} T(x_j,t_i)=\sum_{i}^{n}to\min \sum_{j}^{m}a_{ij}\cdot x_j\le B_i+t_i \\ x_j\ge P_j \\ x_j\ge 0 \\ \end{array} \right\ $$
Листинг решения в Mathcad показан ниже. .Решение получается в виде двумерной переменной $$t1$$ с элементами $$t1_1$$ найденный вектор продукции. и $$t1_2$$, найденный вектор добавочных ресурсов
Далее, имея полученные значения добавочных ресурсов, решаем исходную задачу. На диаграммах показаны старые ресурсы, новые ресурсы. Видны добавочные ресурсы, добавлено ровно столько, чтобы выполнить план. В результате план выполняется и ресурсов не остается
Входные данные
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$ - план выпуска
$$Z(x)$$ – прибыль
Матрица затрат ресурсов: >$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$, $$t:=\begin{pmatrix} 1\\ 1\\ 1 \\ 1\\ 1\end{pmatrix}$$
Решение:
$$Z(x):=d\cdot x$$
$$T(x,t):=t_1+t_2+t_3+t_4+t_5$$ – добавочные ресурсы
$$Given$$
$$a\cdot x \le B+t$$
$$x \ge P$$
$$t1:=Minimize(T,x,t)$$
$$t1:=\begin{pmatrix} \{3.1\}\\ \{5.1\} \end{pmatrix}$$
Вектор решений – количество компьютеров: $$t1_1:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$
Добавочные ресурсы: $$t1_2:=\begin{pmatrix} 90\\ -5\\ 115 \\ 80 \\ 40 \end{pmatrix}$$
Новые ресурсы: $$B+t1_2:=\begin{pmatrix} 330\\ 140\\ 270\\ 140\\ 110\end{pmatrix}$$
Прибыль: $$Z(t1_1)=1153000$$
План: $$P:=\begin{pmatrix} 40\\ 20\\ 10\end{pmatrix}$$
Ресурсы: $$B1:=\begin{pmatrix} 330\\ 140\\ 270\\ 140\\ 110\end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$
$$Z(x):=d\cdot x$$
$$T(x,t):=t_1+t_2+t_3+t_4+t_5$$ – добавочные ресурсы
$$Given$$
$$a\cdot x \le B1$$
$$x \ge P$$
$$x:=Maximize(Z,x)$$
$$x=\begin{pmatrix} 40\\ 20\\ 10\end{pmatrix}$$, $$Z(X)=1153000$$
Новые ресурсы: $$B1=\begin{pmatrix} 330\\ 140\\ 270\\ 140\\ 110\end{pmatrix}$$
Старые ресурсы: $$B=\begin{pmatrix} 240\\ 145\\ 155\\ 60\\ 70\end{pmatrix}$$
Остаточные ресурсы, новый выпуск: $$B1-a\cdot x=\begin{pmatrix} -0\\ 0\\ -0\\ -0\\ -0\end{pmatrix}$$
Транспортная задача – задача поиска оптимального распределения поставок однородных грузов [20]. В общей постановке формулируется так: составить план поставок продукции (грузов) от поставщиков к потребителям, имеющий минимальную стоимость затрат.
Модель задачи.
Входные переменные:
Управляемые переменные - $$x_{ij}$$ - количество единиц продукта, доставленного от $$i$$- го поставщика к $$j$$-му потребителю,
Выходные показатели – суммарные затраты доставки продукции $$F=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}$$.
Целевая функция – результирующий, оптимизируемый параметр – суммарные затраты. Цель решения задачи – нахождение значений управляемых переменных $$x_{ij}$$, обеспечивающих минимум целевой функции $$F$$.
$$F=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}\to \min$$
Математическая модель транспортной задачи может быть закрытой (сбалансированной) - все грузы должны быть вывезены, и все потребности полностью удовлетворены. В этом случае $$\sum_{i}^{m}A_i=\sum_{j}^{n}B_j$$.
На практике обычно встречается случай открытой (несбалансированной) транспортной задачи, когда производство не совпадает с потреблением. В этом случае открытая модель сводится к закрытой. Для этого вводятся либо фиктивный поставщик (случай дефицита), либо фиктивный потребитель (случай перепроизводства). Стоимость перевозок единицы продукции, как от фиктивного поставщика, так и до фиктивного потребителя полагают раной нулю, так как в обоих случаях продукция не перевозится.
$$\sum_{i}^{m}A_i-\sum_{j}^{n}B_j=объем \;продукции\; фиктивного\; поставщика\; (потребителя)$$
При добавлении фиктивного поставщика (потребителя) количество поставщиков $$m$$ (или потребителей $$n$$) увеличивается на единицу.
В результате имеем систему уравнений.
$$ \left\{ \begin{array}{lc} \sum_{i=1}^{m}x_{ij}=A_i \; (i=\overline{1,m}) \\ \sum_{j=1}^{n}x_{ij}=A_j \; (j=\overline{1,n}) \\ x_j\ge 0, \; i=\overline{1,m}, \; j=\overline{1,n} \\ x_j\ge P_j \\ F=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}\to \min \\ \end{array} \right\ $$
Задача 4.4.
Имеется 4 мебельные фирмы и 5 центров распределения товаров - магазинов. Планируется наладить перевозки продукции с фирм в магазины. Фирмы имеют следующие возможности производства: 280, 150, 225, 175 единиц в месяц. Пяти магазинам необходимо поставить 100, 200, 50, 250 и 150 единиц товара в месяц соответственно. Необходимо так спланировать перевозки, чтобы уменьшить (оптимизировать) транспортные расходы.
Стоимость перевозок единиц продукции приведена в таблице.
| Фирмы/магазины | Олимп | Сфера | Квартира | Уют | Товары для дома |
| Томек | 1,50 | 2 | 2,25 | 2,25 | 2,25 |
| СуперМебель | 2,5 | 2,2 | 1,65 | 1 | 1,5 |
| Мебель-лес | 2,3 | 1,7 | 1,5 | 1,4 | 1,6 |
| ЦентрМебель | 2,3 | 0,5 | 1,85 | 1,35 | 1,25 |
Решение (рис. 4.4). Определим тип задачи. Суммарное количество производимого товара составляет $$\sum_{i}^{m}A_i=830$$, количество товара, которое надо доставить $$\sum_{j}^{n}B_j=750$$. Задача "открытого типа". Имеем случай перепроизводства. Сбалансируем задачу, сведем к "закрытому типу", введя фиктивного потребителя с потребностью $$\sum_{i}^{m}A_i-\sum_{j}^{n}B_j=80$$. Стоимость перевозок единицы продукции до фиктивного потребителя считаем равной нулю.
В Mathcad транспортная задача решается аналогично задаче производства – в матричном виде, с помощью блока $$given$$ и в данном случае функции $$miniimize$$. Особенность заключается в том, что матрица неизвестных двумерна. Для построения ограничений – нахождения суммы по строкам и по столбцам вводим единичные векторы. . Порядок действий тот же. Документ Mathcad решения задачи показан на рис.4.3.
$$ORIGIN:=1$$
Входные данные
$$m:=4, \; n:=5$$
$$\underline{i}:=1..\underline{m}$$ - фирмы-поставщики
$$\underline{j}:=1..\underline{n}$$ - магазины-потребители
Производство фирм поставщиков: $$A:=\begin{pmatrix} 280\\ 150\\ 225\\ 175 \end{pmatrix}$$
Потребность магазинов: $$B:=\begin{pmatrix} 100\\ 200\\ 50\\ 250\\ 150\end{pmatrix}$$
$$\sum_{\underline{i}}^{}\underline{A}_{\underline{i}}=830$$, $$\sum_{\underline{j}}^{}\underline{B}_{\underline{j}}=750$$, $$\sum_{\underline{i}}^{}\underline{A}_{\underline{i}}-\sum_{\underline{j}}^{}\underline{B}_{\underline{j}}=80$$
Вводим фиктивного потребителя в магазин с потребностью 80 ед.
$$\underline{n}:=\underline{n}+1=6$$, $$\underline{j}:=1..\underline{n}$$
$$\underline{Потребители}+\underline{фиктивный}$$
$$B:=\begin{pmatrix} 100\\ 200\\ 50\\ 250\\ 150\\ 80\end{pmatrix}$$
Стоимость перевозки ед. продукции: $$с:=\begin{pmatrix} 1.5 2 1.55 2.25 2.25 0\\ 2.5 2.2 1.65 1 1.5 0 \\ 2.3 1.7 1.5 1.4 1.6 0\\ 2.3 0.5 1.85 1.35 1.25 0\end{pmatrix}$$
Решение:
$$\underline {F}(\underline {x})=\sum_{\underline {i}=1}^{m}\sum_{\underline {j}=1}^{\underline {n}}(\underline {x}_{\underline {i}\underline {j}}\cdot \underline {c}_{\underline {i}\underline {j}})$$
Начальные значения: $$\underline{x}_{\underline {i},\underline {j}}:=1$$
Единичный вектор-столбец для магазинов: $$\underline{v}_{\underline {j}}:=1$$
Единичный вектор-столбец для поставщиков: $$\underline {k}_{\underline {j}}:=1$$
$$\underline{Given}$$
$$\underline{x}\cdot \underline{v}=\underline{A}$$
$$\underline{x}^T\cdot \underline{k}=\underline{B}$$
$$x \ge 0$$
$$\underline{x}:=\underline{Minimize}(\underline{F}, \underline{x})$$
Оптимальные перевозки: $$x=\begin{pmatrix} 100 25 50 0 25 80\\ 0 0 0 150 0 0 \\ 0 0 0 100 125 0\\ 0 175 0 0 0 0\end{pmatrix}$$
Затраты: $$\underline {F}(\underline {x})=911.25$$
$$\underline {x}\cdot \underline {y}=\begin{pmatrix} 280\\ 150\\ 225\\ 175 \end{pmatrix}$$
$$\underline {x}^T\cdot \underline {k}=\begin{pmatrix} 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
(рис 4.3) Листинг решения задачи 4.4. Оптимальные перевозки. Показан фиктивный потребитель.
Результат решения показывает, как спланировать доставку. Минимальные затраты составляют F=911ед. Излишек товара выгоднее отправить в "Товары для дома" (магазин 5).
Есть транспортные задачи, в которых пункты отправления и назначения являются промежуточными, через них переправляются товары в конечный пункт назначения. В данной постановке промежуточные пункты выступают и как потребители и как поставщики. В данном случае формируется единая транспортная матрица, в которой количество поставщиков и количество потребителей увеличивается на число промежуточных пунктов.
Задача 4.5.
Усложним условия задачи 4.4. Фирмы производят и вывозят мебель на 3 склада. Необходимо распределить доставку товаров от поставщиков на склады, со складов в магазины по заказам так, чтобы оптимизировать транспортные расходы. Фирмы производят 280, 150, 225, 175 единиц. Вместимость складов 400, 300, 350 единиц. Магазины заказывают 100, 200, 50, 250 и 150 единиц товара, соответственно. Стоимость перевозок единиц продукции с фирм на склады и со склада в магазины приведена в таблице 4.4, таблице 4.5.
| Фирмы | Склад 1 | Склад 2 | Склад 3 | Объемы производства на фирмах |
| Фирма 1 | 2,4 | 3,0 | 2,3 | 280 |
| Фирма 2 | 3,9 | 3,2 | 4,3 | 150 |
| Фирма 3 | 3,3 | 3,3 | 2,1 | 225 |
| Фирма 4 | 4,3 | 2,7 | 3,2 | 175 |
| Вместимость складов | 400 | 300 | 350 |
| Склады | "Олимп" | "Сфера" | "Квартира" | "Уют" | "Товары для дома" |
| Склад 1 | 5,8 | 3,9 | 3,6 | 5,4 | 2,8 |
| Склад 2 | 4,8 | 5,5 | 3,3 | 2,0 | 2,0 |
| Склад 3 | 2,2 | 3,3 | 3,6 | 3,4 | 1,6 |
| Потребности | 100 | 200 | 50 | 250 | 150 |
Модель задачи.
В модель задачи. добавляется входная переменная склады - три склада $$D_k\; (k=\overline{1,s}),\; s=3$$. Склады выступают и как потребители, и как поставщики. Формируется единая матрица, в которой количество элементов поставщиков и количество потребителей увеличивается на число складов: строки = поставщики плюс склады, столбцы = склады плюс магазины. Для запрета перевозок со склада на другой склад и непосредственно от поставщиков в магазины устанавливается очень большой, нереальный тариф (999999).
Таблица стоимости доставки со склада на склад имеет вид:
| Склад 1 | Склад 2 | Склад 3 | |
| Склад 1 | 0 | 999999 | 999999 |
| Склад 2 | 999999 | 0 | 999999 |
| Склад 3 | 999999 | 999999 | 0 |
Таблица стоимости доставки со склада в магазин имеет вид:
| Фирмы | "Олимп" | "Сфера" | "Квартира" | "Уют" | "Товары для дома" |
| Фирма 1 | 999999 | 999999 | 999999 | 999999 | 999999 |
| Фирма 2 | 999999 | 999999 | 999999 | 999999 | 999999 |
| Фирма 3 | 999999 | 999999 | 999999 | 999999 | 999999 |
| Фирма 4 | 999999 | 999999 | 999999 | 999999 | 999999 |
Задача решается в объединенной матрице. $$M_{i+k, k+j}$$ стоимость доставки в объединенной матрице стоимостей. Баланс устанавливается по сумме производства поставщиков и емкости складов, с одной стороны, и емкости складов и потребности магазинов, с другой стороны. $$\sum_{i}^{4}A_i+\sum_{k}^{3}D_k=\sum_{k}^{3}D_k+\sum_{j}^{5}B_j$$.
Здесь $$\sum_{i}^{4}A_i+\sum_{k}^{3}D_k=1880$$, $$\sum_{k}^{3}D_k+\sum_{j}^{5}B_j=1800$$ данной задаче необходим фиктивный потребитель с потребностью 80 ед. В остальном модель аналогична предыдущей модели. Система уравнений:
$$ \left\{ \begin{array}{lc} \sum_{i=1}^{m+s}x_{ij}=A_i(i=\overline{1,m})+D_k(k=\overline{1,s}) \\ \sum_{j=1}^{n+s}x_{ij}=B_j(j=\overline{1,n})+D_k(k=\overline{1,s}) \\ x_j\ge 0, \; i=\overline{1,m+s}, \; j=\overline{1,n+s} \\ F=\sum_{i}^{n+s}\sum_{j}^{m+s}M_{ij}\cdot x_{ij}\to \min \\ \end{array} \right\ $$
Решение. В Mathcad задача строится аналогично транспортной задаче. Данные вводятся в матричном виде, оптимизация реализуется с помощью блока given и функции $$minimize$$, ограничения вводятся с единичные векторы. Здесь ообенность заключается в том, строится объединенная матрица. Для этого используем встроенные функции для матричных операций
Функция $$augment (M1, M2)$$ объединяет в одну матрицы $$М1$$ и $$М2$$, имеющие одинаковое число строк.
Функция $$stack (M1, M2)$$ объединяет в одну матрицы $$М1$$ и $$М2$$, имеющие одинаковое число столбцов. (см. Приложение 2). Документ Mathcad решения задачи показан ниже.
$$ORIGIN:=1$$
Входные данные
$$\underline{i}:=1..4$$ - фирмы-поставщики
$$\underline{j}:=1..5$$ - магазины-потребители
$$\underline{k}=1..3$$ - склады
Производство фирм поставщиков: $$A:=\begin{pmatrix} 280\\ 150\\ 225\\ 175 \end{pmatrix}$$
Емкость складов: $$D:=\begin{pmatrix} 400\\ 300\\ 350 \end{pmatrix}$$
Потребность магазинов: $$B:=\begin{pmatrix} 100\\ 200\\ 50\\ 250\\ 150\end{pmatrix}$$
$$\sum_{\underline{i}=1}^{4}\underline{A}_{\underline{i}}=830$$, $$\sum_{\underline{k}=1}^{3}\underline{D}_{\underline{k}}=1050$$, $$\sum_{\underline{j}=1}^{5}\underline{B}_{\underline{j}}=750$$
$$\underline{поставщики}+\underline{склады}$$: $$\sum_{\underline{i}}^{}\underline{A}_{\underline{i}}+\sum_{\underline{k}}^{}\underline{D}_{\underline{k}}=1880$$
$$\underline{склады}+\underline{магазины}$$: $$\sum_{\underline{j}}^{}\underline{B}_{\underline{j}}+\sum_{\underline{k}}^{}\underline{D}_{\underline{k}}=1800$$
Вводим фиктивного потребителя в магазин с потребностью 80 ед.
$$\underline{j}:=1..6 $$, $$\underline{j}:=1..\underline{n}$$
$$\underline{магазины}+\underline{фиктивный}$$$$\underline {B}:=\begin{pmatrix} 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
Стоимость перевозки ед. продукции от фирмы на склад: $$с:=\begin{pmatrix} 2.4 3 2.3 \\ 3.9 3.2 4.3 \\ 3.3 3.3 2.1\\ 4.3 2.7 3.2 \end{pmatrix}$$
Стоимость перевозки ед. продукции со склада в магазин: $$с:=\begin{pmatrix} 5.8 3.9 3.6 5.4 2.8 0 \\ 4.8 5.5 3.3 2.0 2.0 0 \\ 2.2 3.3 3.6 3.4 1.6 0 \end{pmatrix}$$
Решение
матрица стоимостей фиктивной доставки со склада на склад: $$underline{cc}:=\begin{pmatrix} 0 999999 999999 \\ 999999 0 999999 \\ 999999 999999 0 \end{pmatrix}$$
матрица стоимостей фиктивной доставки с фирмы в магазин: $$underline{cc1}:=\begin{pmatrix} 999999 999999 999999 999999 999999 0 \\ 999999 999999 999999 999999 999999 0 \\ 999999 999999 999999 999999 999999 0 \\ 999999 999999 999999 999999 999999 0 \end{pmatrix}$$
Объединяем матрицы: $$\underline{M1}:=\underline{argument}(\underline{c},\underline{cc1})$$, $$\underline{A1}:=\underline{stack}(\underline{A},\underline{D})$$
$$\underline{M2}:=\underline{argument}(\underline{cc},\underline{c1})$$, $$\underline{B1}:=\underline{stack}(\underline{D},\underline{B})$$
$$\underline {A1}:=\begin{pmatrix} 280\\ 150\\ 225\\ 175\\ 400\\ 300 \\ 350 \end{pmatrix}$$, $$\underline {B1}:=\begin{pmatrix} 400\\ 300\\ 350\\ 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
$$\underline {M1}:=\begin{pmatrix} 2.4 3 2.3 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0\\ 3.9 3.2 4.3 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0\\ 3.3 3.3 2.1 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0 \\ 4.3 2.7 3.2 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0 \end{pmatrix}$$
$$\underline {M2}:=\begin{pmatrix} 0 10\times 10^5 10\times 10^5 5.8 3.9 3.6 5.4 2.8 0\\ 10\times 10^5 0 10\times 10^5 4.8 5.5 3.3 2 2 0\\ 10\times 10^5 10\times 10^5 0 2.2 3.3 3.6 3.4 1.6 0 \end{pmatrix}$$
$$\underline{M}:=\underline{stack}(\underline{M1},\underline{M2})$$, $$\underline {M}:=\begin{pmatrix} 2.4 3 2.3 999999 999999 999999 999999 999999 0\\ 3.9 3.2 4.3 999999 999999 999999 999999 999999 0\\ 3.3 3.3 2.1 999999 999999 999999 999999 999999 0 \\ 4.3 2.7 3.2 999999 999999 999999 999999 999999 0 \\ 0 999999 999999 5.8 3.9 3.6 5.4 2.8 0\\ 999999 0 999999 4.8 5.5 3.3 2 2 0\\ 999999 999999 0 2.2 3.3 3.6 3.4 1.6 0\end{pmatrix}$$
$$i:=1..7.\; j:=1..9$$
Начальные значения: $$x_{i,j}:=1$$
Единичный вектор для строк и столбцов $$v1_i:=1,\; v2_j:=1$$
$$F(x):=\sum_{i=1}^{7}\sum_{j=1}^{9}(x_{i,j}\cdot M_{i,j})$$
$$Civen$$
$$x^T\cdot v1=B1$$
$$x\cdot v2=A1$$
$$x\ge 0$$
Оптимальные перевозки: $$x:=Minimize(F,x)$$
Затраты: $$F(x)=26000065$$
Ограничения:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 1 2 3 4 5 6 7 8 9 \\ \hline 1 113 13 35 0 0 0 0 0 0 \\ \hline 2 4 18 49 0 0 0 0 0 9 \\ \hline 3 110 78 37 0 0 0 0 0 0 \\ \hline 4 100 18 56 0 0 0 0 0 1 \\ \hline 5 73 0 0 39 94 42 27 126 0 \\ \hline 6 0 54 0 10 81 8 137 9 0\\ \hline 7 0 0 173 51 25 0 86 15 0 \\ \hline \end{array}$$
$$x\cdot v2:=\begin{pmatrix} 280\\ 150\\ 225\\ 175\\ 400\\ 300 \\ 350 \end{pmatrix}$$, $$x^T\cdot v1:=\begin{pmatrix} 400\\ 300\\ 350\\ 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
(рис 4.4) Диаграмма доставки
Планирование штатного расписания относится к типу задач оптимального распределения трудовых ресурсов.
Задача 4.6.
Необходимо укомплектовать штат работников в диспетчерской фирме в соответствии со следующими требованиями: каждый день недели должно работать определенное количество работников (см. таблицу). При этом служащие должны иметь два выходных дня. В каждой группе – не менее 2 человек. Руководитель фирмы заинтересован в экономии заработной платы. Обеспечить работу в течение недели фирмы в соответствии с ресурсным планом при минимальном фонде заработной платы.
Потребность в работниках каждый день недели
| День | Вс. | Пн. | Вт. | Ср. | Чт. | Пт. | Сб. |
| Кол. работников | 22 | 17 | 13 | 14 | 15 | 18 | 24 |
Постановка задачи.
Организуем группы, каждая из которых имеет свои выходные дни - два смежных дня. У первой группы выходные - Вс и Пн., у второй - Пн и Вт. и т.д. Всего - 7 групп. Дневная оплата каждой группы приведена в таблице. Задача – определить количество работников в каждой группе при минимальной суммарной оплате.
| № группы | Вых.дни | Количество работников | Оплата P. |
| 1 | Вс.,Пн. | х1 | 50 |
| 2 | Пн. Вт. | х2 | 45 |
| 3 | Вт. Ср. | х3 | 45 |
| 4 | Ср. Чт. | х4 | 45 |
| 5 | Чт. Пт. | х5 | 45 |
| 6 | Пт. Суб. | х6 | 55 |
| 7 | Суб. Вс | х7 | 50 |
Модель задачи.
Выбираем объекты для моделирования: и исходные данные - т.е. что мы имеем.
Входные переменные:
| Группа | Вс. | Пн. | Вт. | Ср. | Чт. | Пт. | Сб. |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 6 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
Управляемые переменные – $$x_i$$ - количество работников в $$i$$ группе,
Ограничения
Ресурсное - $$B_j\;(j=\overline{1,m})$$ - количество работающих в j день недели
Плановое – $$M_i$$ требуемое количество работников в $$i$$ группе .
Выходные показатели – суммарная заработная плата $$S=\sum_{i=1}^{m}P_i\cdot x_i$$.
Целевая функция – результирующий, оптимизируемый параметр – суммарная заработная плата минимальна.
$$S=\sum_{i=1}^{m}P_i\cdot x_i \to \min$$
В результате имеем систему уравнений.
$$ \left\{ \begin{array}{lc} \sum_{i=1}^{m}с_{ij}\cdot x_i=B_j\;(j=\overline{1,m}) \\ x_i\ge 0,\;(i=\overline{1,m}) \\ x_i\ge P_i\\ x_i\ge 2 \\ S=\sum_{i=1}^{m}P_i\cdot x_i \to \min \end{array} \right\ $$
Решение. Данные вводятся в виде матриц. Матрица выхода бригад на работу двумерна. Задача решается с помощью блока $$given$$ и функции $$minimize $$. Документ Mathcad решения задачи показан ниже.
Входные данные
$$ORIGIN:=1$$
$$m:=7$$
$$i=1..m$$ - номер группы, $$j:=1..m$$ – день недели
Потребности работников: $$B:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
Оплата по группам: $$P:=\begin{pmatrix} 50\\ 45\\ 45\\ 45\\ 45\\ 55\\ 50\end{pmatrix}$$
Матрица выхода работников: $$c:=\begin{pmatrix} 0 0 1 1 1 1 1\\ 1 0 0 1 1 1 1\\ 1 1 0 0 1 1 1\\ 1 1 1 0 0 1 1\\ 1 1 1 1 0 0 1\\ 1 1 1 1 1 0 0\\ 0 1 1 1 1 1 0 \end{pmatrix}$$
Решение:
Начальные значения:
$$x_i:=1$$ – количество работников
$$S(x):=P\cdot x$$
$$Given$$
$$c\cdot x \ge B$$
$$x \ge 2$$
$$x1:=Minimize(S,x)$$
$$x1=\begin{pmatrix} 2\\ 4\\ 7\\ 6\\ 5\\ 2\\ 2 \end{pmatrix}$$
Заработная плата: S(x)=335
Ограничение: $$c\cdot x1:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
(рис 4.5) Количество работников в группах, имеющих разные выходные
Потребности работников
$$RR:=c\cdot x1$$
$$RR:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
Ограничение:
$$B:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
(рис 4.6) Количество работающих по дням недели
Возможность оптимизации межотраслевого баланса появляется, если коэффициенты прямых затрат отражают затраты не средние по отрасли, а для каждого способа и технологии производства. В таких моделях межотраслевого баланса представлено отдельно производство каждого вида продукции. Построение оптимизационных моделей межотраслевого баланса позволяет в условиях ограниченности ресурсов находить наиболее эффективные комбинации ресурсов для максимизации конечного продукта [22].
Задача 4.7.
Крупное структурное предприятие состоит из 6 подразделений, каждый из которых выпускает по 1 виду продукции. Отношения между подразделениями определены технологической матрицей прямых затрат. В таблице 4.8 указаны нормы прямых затрат подразделений, используемых в качестве промежуточного продукта для выпуска единицы продукции для каждого подразделения. Известны максимально допустимые ресурсы подразделений предприятия. Известны цены на готовую продукцию, которая направляется на внешний рынок. Оптимизировать новую программу – плановую валовую продукцию, так, чтобы распределение готовой продукции на собственные потребности и экспорт, давало максимальный доход от реализованной продукции.
| Подразделение 1 | Подразделение 2 | Подразделение 3 | Подразделение 4 | Подразделение 5 | Подразделение 6 | Цена | |
| Подразделение 1 | 0,01 | 0,03 | 0,05 | 0,07 | 0,09 | 0,12 | 2 |
| Подразделение 2 | 0,03 | 0,05 | 0,06 | 0,08 | 0,1 | 0,13 | 6 |
| Подразделение 3 | 0,05 | 0,07 | 0,07 | 0,09 | 0,11 | 0,14 | 3 |
| Подразделение 4 | 0,07 | 0,09 | 0,08 | 0,1 | 0,12 | 0,15 | 7 |
| Подразделение 5 | 0,09 | 0,11 | 0,09 | 0,11 | 0,13 | 0,16 | 8 |
| Подразделение 6 | 0,11 | 0,13 | 0,1 | 0,12 | 0,14 | 0,17 | 1 |
| Ресурсы подразделений | 400 | 300 | 900 | 500 | 450 | 250 |
Модель задачи.
Входные переменные:
Управляемые переменные - $$X_j$$ - вектор плановой валовой продукции.
Выходные показатели –
$$Y_j$$ -. конечная продукция подразделений,
$$Y=(E-A)\cdot X$$ - в соответствии с уравнением межотраслевого баланса, $$Z(X)$$ - доход от реализации конечной продукции на внешнем рынке..
Целевая функция –оптимизируемый параметр – доход от реализации конечной продукции.
$$Z(X)= (E-A)\cdot X \cdot C$$
$$Z(X)\to \max$$
Ограничения.
$$X_j\le M_j$$ – ресурсные ограничения
$$(E-A)\cdot X > 0$$ – конечный продут положителен,
$$X_j\ge 0$$
В результате имеем систему уравнений.
$$ \left\{ \begin{array}{lc} X_j\le M_j \\ (E-A)\cdot X > 0 \\ X_j\ge 0\\ Z(X)=(E-A)\cdot X \cdot C \to \max \end{array} \right\ $$
Решение. В программе Mathcad задача решается в матричном виде, аналогично всем приведенным примерам. Система уравнений с оптимизацией решается численно с помощью блока $$given$$ и функции $$maximize()$$.
Входные данные
$$ORIGIN:=1$$
$$i:=1..6, \; j:=1..6$$
Матрица промежуточных потоков затрат: $$A:=\begin{pmatrix} 0.01 0.03 0.05 0.07 0.09 0.12\\ 0.03 0.05 0.06 0.08 0.1 0.13\\ 0.05 0.07 0.07 0.09 0.11 0.14\\ 0.07 0.09 0.08 0.1 0.12 0.15\\ 0.09 0.11 0.09 0.11 0.13 0.16\\ 0.11 0.13 0.1 0.12 0.14 0.17 \end{pmatrix}$$
Ресурсы подразделений: $$M:=\begin{pmatrix} 400\\ 300\\ 900\\ 500\\ 450\\ 250 \end{pmatrix}$$
Цена: $$C:=\begin{pmatrix} 2\\ 6\\ 3\\ 7\\ 8 \\ 1 \end{pmatrix}$$
$$E:=identity(6)$$ – единичная матрица
$$X$$ – валовый планируемый выпуск
$$(E-A)\cdot X$$ – вектор конечной продукции
$$Z$$ – доход от реализации конечной продукции – целевая функция
Оптимизация дохода: $$Z - \max$$
Решение:
$$Z(X):=[(E-A)\cdot X]\cdot C$$, $$v1_i:=1$$ – единичный вектор
Начальные значения:
$$X_j:=1$$, $$A\cdot diag(X)\cdot v1$$ – затраты – сумма по столбцам
$$Given$$
$$X\le M$$
$$(E-A)\cdot X > 0$$
$$X\ge 0$$
$$X1:=Maximixe (Z,X)$$
Оптимальный план валового выпуска: $$X1:=\begin{pmatrix} 131\\ 300\\ 311\\ 500\\ 450\\ 250\end{pmatrix}$$
Конечная продукция: $$Y:=(E-A)\cdot X1$$, $$Y:=\begin{pmatrix} -0\\ 145\\ 132\\ 297\\ 224 \\ 0 \end{pmatrix}$$
Оптимальный доход: $$Z(X1)=5137$$
Промежуточные поставки: $$A\cdot diag(X1)$$, $$A\cdot diag(X1):=\begin{pmatrix} 1.313 9 15.526 35 40.5 30 \\ 3.94 15 18.632 40 45 32.5 \\ 6.567 21 21.737 45 49.5 35\\ 9.194 27 24.842 50 54 37.5 \\ 11.821 33 27.947 55 58.5 40 \\ 14.447 39 31.053 60 63 42.5\end{pmatrix}$$
Затраты – суммы по столбцам $$S:= A\cdot diag(X1) \cdot v1$$, $$S:=\begin{pmatrix} 131.34\\ 155.072\\ 178.804\\ 202.536\\ 226.268\\ 250\end{pmatrix}$$
(рис 4.7) Валовая продукция, конечный продукт
(рис 4.8) Затраты
Рассмотрены основные типы оптимизационных задач.
Задача формирования оптимальной производственной программы - три модели: модель получения максимальной прибыли без заданного плана и с планом, модель в комплектной постановке - получение максимальной доли плана выпуска продукции при нехватке ресурсов, т-модель - нахождения минимума дополнительного количества ресурсов, необходимых для выполнения полного плана. Две модели транспортной задачи. Задача оптимального комплектования штата работников. Задача максимизации конечного продукта в схеме межотраслевого баланса. Для каждой задачи определены входные данные, построена математическая модель. Каждая модель представлена в Mathcad в виде системы матричных уравнений. Системы уравнений решены численно - в блоке $$given\; maximize\; (minimize)$$. Построены диаграммы результирующих данных.
Оптимизационная задача – задача, цель которой состоит в нахождении наилучшего (оптимального) с точки зрения некоторого критерия варианта использования имеющихся ресурсов.
Оптимизационная модель – математическая модель решения оптимизационной задачи.
Математическое программирование - направление математики, изучающее методы решения оптимизационных задач.
Целевая функция – функция, определяющая критерий оптимальности в оптимизационной задаче.
Управляемые переменные - переменные целевой функции, которые подвергаются изменению в процессе поиска решения.
Ограничения – системы уравнений и неравенств, ограничивающих область решения оптимизационной задачи в соответствии с заданными условиями.
Нормированная стоимость - изменение целевой функции при изменении соответствующего управляемого параметра на единицу.
Транспортная задача - оптимизационная задача оптимального прикрепления потребителей к поставщикам при доставке грузов.
Задача оптимального распределения трудовых ресурсов – оптимизационная задача распределения трудовых ресурсов при выбранном критерии оптимальности.
Цель лекции. Научить строить математическую модель оптимизационных задач средствами Mathcad. Выделять управляемые переменные, целевую функции. ограничения, затем строить систему уравнений. Применять блок given - maximize (minimize) для решения матричных уравнений. Анализировать полученное решение. Строить графики результата.
Принятию любого экономического или финансового решения предшествует перебор и оценка вариантов. Экономико-математические задачи, цель которых состоит в нахождении наилучшего (оптимального) с точки зрения некоторого критерия или критериев варианта использования имеющихся ресурсов (труда, капитала и пр.), называются оптимизационными [18, 19].
Типы оптимизационных задач в экономике:
Оптимизационные задачи решаются с помощью оптимизационных моделей. Оптимизационные модели возникают при практической реализации принципа оптимальности в управлении. В каждом случае выделяется объект оптимизации, определяется цель оптимизации, ставится задача нахождения экстремума функции, описывающей оптимизируемую цель при заданных условиях. Структура оптимизационной модели состоит из целевой функции, области допустимых решений и системы ограничений, определяющих эту область. В качестве инструмента используется математическое программирование (планирование): линейное, нелинейное, динамическое, и т.п. В зависимости от типа переменных и функциональных связей различают задачи линейного и нелинейного программирования. Многие экономические задачи формулируются в терминах линейного программирования, поскольку функции прибыли, стоимости затрат - линейные функции переменных, связанных с объемами выпуска, продаж и других факторов.
В общем виде задача линейного программирования ЗЛП ставится следующим образом: найти вектор $$\overline{X}=(x_1,x_2,...,x_n)$$, максимизирующий (минимизирующий) линейную форму $$f(\overline{X})=\sum_{j=1}^{n}c_jx_j\to \max (\min)$$, удовлетворяющий условиям:
$$\sum_{j=1}^{n}a_{ij}\le b_i$$
$$x_j\ge 0,\;j=1..n$$
где $$f$$ — заданная функции, $$a_{ij},\; b_i$$ — некоторые действительные числа.
Линейная функция $$f(\overline{X})$$ - целевая функция задачи, условия ( 4.1) (4.2) - ограничения задачи, вектор $$\overline{X}=(x_1,x_2,...,x_n)$$, компоненты которого удовлетворяют функциональным и прямым ограничениям задачи, называется планом или допустимым решением ЗЛП. Допустимое решение, максимизирующее (минимизирующее) целевую функцию $$f(\overline{X})$$ , называется оптимальным планом задачи: $$f(\overline{X^*})=\max \; f(\overline{X})$$ (или $$\min$$) где $$\overline{X^*}=(x^*_1,x^*_2,...,x^*_n)$$ - оптимальное решение ЗЛП.
В оптимизационной задаче экономический показатель, для которого определяется максимальное или минимальное значение - целевая функция. Управляемые переменные - аргументы целевой функции - переменные задачи, которые подвергаются изменению в процессе поиска решения. Область допустимых решений – это область, в пределах которой осуществляется выбор решений. В экономических задачах она ограничена наличными ресурсами, условиями, которые записываются в виде системы ограничений, состоящей из уравнений и неравенств.
Приведем примеры экономико-математического моделирования оптимизационных задач средствами Mathcad.
Рассмотрим классическую задачу формирования производственной программы [20,21,22]. Пусть осуществляется выпуск $$m$$ видов продукции. Для этого используется n основных видов ресурсов $$B$$, (механизмов, оборудования, времени, специалистов), объем которых на предприятии задан. Известно количество каждого ресурса, идущего на выпуск единицы продукции каждого вида. Отдельная продукция реализуется по цене c, норма переменных затрат для нее составляет $$q$$. Необходимо, чтобы производственная программа была оптимальна и давала наибольшую валовую прибыль,
Постановка задачи. Цель моделирования – получить максимальную прибыль, которая определяется количеством произведенной продукции в имеющихся условиях с учетом всех ограничений. Найти вариант из множества возможных.
Модель задачи
Определение переменных. Введем обозначения:
Входные переменные:
$$m$$ –видов продукции, $$j$$ – текущий номер вида продукции.
$$c_j$$ - прибыль от реализации единицы $$j$$-го вида продукции.
$$q_j$$ - переменные затраты производства единицы $$j$$-го вида продукции
$$В_i$$ - запасы $$i$$-го ресурса $$i$$ – текущий номер вида ресурса, $$m$$ - количество ресурсов.
$$а_{ij}$$ - норма затрат $$i$$ го ресурса для производства $$j$$-го вида продукции
$$Р_j$$ – требуемое количество выпуска продукции каждого вида по плану,
Выходные показатели – суммарная прибыль $$Z(x_1, x_2, x_3,… x_m)$$,
Управляемые переменные. $$x_j$$ - искомый объем продукции $$j$$-го вида.
Целевая функция – показатель, который определяет цель моделирования - результирующий, оптимизируемый параметр – прибыль. Цель решения задачи – нахождение значений управляемых переменных $$x_j$$, доставляющих экстремум целевой функции прибыли $$Z$$.
$$Z(x_j)=\sum_{j=1}^{m}(c_j-q_j)\cdot x_j, \; j=\overline{1,m}$$
$$Z(x_j)\to \max \; j=\overline{1,m}$$
Ограничения. условия, налагаемые на данные задачи, определяющие исследуемую величину, которая оптимизируется. Различают три типа ограничений:
Ресурсные ограничения - ограниченность имеющихся ресурсов; обеспечивающих выпуск:
$$a_{ij}\cdot x_j$$ – планируемые затраты ресурса $$i$$ для производства продукции $$j$$ ,
$$\sum_{j}^{m}a_{ij}\cdot x_j$$ – планируемые затраты ресурса $$i$$ на производство всех видов продукции,
$$\sum_{j}^{m}a_{ij}\cdot x_j \le B_i \; i=\overline{1,n}$$ - условие ограниченности ресурсов
плановые ограничения - необходимость выполнения заданных значений $$P_j$$ для искомых объемов продукции $$j$$-го вида:
$$x_j\ge P_j\; j=\overline{1,m}$$ - условие ограниченности по плану
технологические соотношения между группами управляемых переменных, здесь
$$x_j\ge 0\; j=\overline{1,m}$$
Уравнения. В результате имеем систему уравнений, которую надо решить.
$$ \left\{ \begin{array}{lc} a_{ij}\cdot x_j\le B_i \\ x_j\ge P_j\\ x_j\ge 0 \\ Z(x_j)\to\max \; j=\overline{1,m} \end{array} \right\ $$
Решение, если получено, представляется в виде оптимального решения. Это:
количество управляемых переменных, не равных нулю,
числовые значения управляемых переменных,
полученное значение целевой функции
Рассмотрим решение модели на примере следующей задачи.
Задача. 4.1.
Фирма по сборке компьютеров предполагает производить выпуск 3 новых моделей при использовании комплектующих 5 типов. Маркетинговые исследования показали возможность сбыта компьютеров по приемлемым продажным ценам. Необходимые данные по запасам комплектующих, и ценам приведены в таблице. Определить оптимальные объемы выпуска компьютеров при имеющихся ресурсах для получения максимальной прибыли.
| Вид комплектующих | Расход комплектующих ед./изд. Модели ПК | Запас комплектующих. (ед.) | ||
| Модель 1 | Модель 2 | Модель 3 | ||
| 1 | 4 | 6 | 5 | 240 |
| 2 | 1 | 3 | 4 | 145 |
| 3 | 5 | 2 | 3 | 155 |
| 4 | 2 | 2 | 2 | 60 |
| 5 | 1 | 2 | 3 | 70 |
| Затраты на 1 изд. | 1800 | 2700 | 2100 | |
| Цена реализации(усл.ед.) | 10000 | 35000 | 20000 | |
Решение задачи 4. 1.
Применяем модель, описанную выше. В Mathcad система уравнений с оптимизацией решается численно с помощью блока $$given$$ и функции $$maximize\; (miniimize)$$. Задачу решаем в матричном виде: все данные и уравнения представляем в виде матриц. Порядок действий:
Входные данные
$$\underline{c}:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$\underline{q}:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$\underline{d}:=\underline{c}-\underline{q}$$ - прибыль на один компьютер
$$\underline{Z}(\underline{x})$$ - прибыль
Затраты ресурсов: $$\underline{a}:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Запасы ресурсов: $$\underline{B}:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \\ \end{pmatrix}$$
Начальное значение: $$\underline{x}:=\begin{pmatrix} 1\\ 1\\ 1 \\ \end{pmatrix}$$
$$\underline{Z}(\underline{x}):=\underline{d}\cdot \underline{x}$$
$$\underline{Given}$$
$$\underline{a} \cdot \underline{x}\le B$$
$$\underline{x} \ge 0$$
$$\underline{x}:=\underline{Maximize}(\underline{Z},\underline{x})$$, $$\underline{x}:=\begin{pmatrix} 0\\ 30\\ 0 \\ \end{pmatrix}$$
Максимальная прибыль: $$\underline{Z}(\underline{x})=969000$$
Остаток комплектующих: $$\underline{B}-\underline{a}\cdot \underline{x}:=\begin{pmatrix} 60\\ 55\\ 95 \\ 0 \\10 \\ \end{pmatrix}$$
Оптимальный выпуск компьютеров (рис.4.1):
Продукция: $$\underline{x}^T$$
Ресурсы: $$\underline{B2}:=\underline{a}\cdot \underline{x}$$
$$\underline{B}^T,\;\underline{B2}^T$$
(рис 4.1) Графики к задаче 4.1. Количество компьютеров и распределения ресурсов
Полученное оптимальное решение (рис. 4.1) следующее. Оптимальная структура выпуска при имеющихся ресурсах без задания плана – 30 компьютеров 2 модели, прибыль при этом составляет 969000 ед. ; 4 вид комплектующих израсходован полностью – это дефицитный ресурс. Остальные ресурсы имеют остаток, они недефицитные.
Проведем экономический анализ: как меняется прибыль при изменении структуры выпуска. Ниже показаны листинги расчета нормированной стоимости. Полученные результаты приведены в таблице. Нормированная стоимость – изменение целевой функции при изменении соответствующего управляемого параметра (количество выпускаемого продукта) на единицу. Нормированная стоимость для модели 1 в 1,7 больше, чем для модели 3.
| Переменная | Результирующее значение | Целевой коэффициент | Нормированная стоимость |
| x1 | 0 | 8200 | 24100 |
| x2 | 30 | 32300 | 0 |
| x3 | 0 | 17900 | 14400 |
$$ORIGIN:=1$$
Увеличим 1 вид продукции на 1 единицу.
$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$, $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \\ \end{pmatrix}$$, $$d:=\begin{pmatrix} 8200 32300 17900 \end{pmatrix}$$, $$x:=\begin{pmatrix} 1\\ 1\\ 1 \\ \end{pmatrix}$$
$$Z(x):=d\cdot x$$, $$Z0:=969000$$, $$ZN(x):=Z0-Z(x)$$ – нормированная стоимость
$$Given$$
$$a\cdot x \le B$$
$$x \ge 0 \; x1 \ge 1$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 1 \\ 29 \\ 0 \end{pmatrix}$$
$$Z(x1):=9.449\times 10^5$$, $$ZN(x1):=24100$$
Остаток ресурсов: $$B-a\cdot x:=\begin{pmatrix} 225 \\ 137\\ 145 \\ 54 \\64 \end{pmatrix}$$
Увеличим 2 вид продукции на 1 единицу
$$Given$$
$$a\cdot x \le B$$
$$x \ge 0 \; x2 \ge 1$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 0 \\ 30 \\ 0 \end{pmatrix}$$
$$Z(x1):=969000$$, $$ZN(x1):=0$$
Остаток ресурсов: $$B-a\cdot x:=\begin{pmatrix} 225 \\ 137\\ 145 \\ 54 \\64 \end{pmatrix}$$
Увеличим 3 вид продукции на 1 единицу
$$Given$$
$$a\cdot x \le B$$
$$x \ge 0 \; x3 \ge 1$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 0 \\ 29 \\ 1 \end{pmatrix}$$
$$Z(x1):=954600$$, $$ZN(x1):=14400$$
Остаток ресурсов: $$B-a\cdot x:=\begin{pmatrix} 225 \\ 137\\ 145 \\ 54 \\64 \end{pmatrix}$$
Задача. 4.2.
Фирма по сборке компьютеров (см. задачу 4.1) получила заказ на следующий выпуск компьютеров: 1 модель - не менее 8 шт., 2 модель- не менее 10 шт., 3 модель- не менее 3 шт. Данные по запасам комплектующих и ценам приведены в таблице 4.1. Определить прибыль при заданном плане и имеющихся ресурсах. Можно ли выполнить такой план ?
Решение. Задан план выпуска. Схема решения в программе Mathcad аналогична. Задача имеет решение. Ресурсов достаточно - план выполняется. Структура выпуска – заданный план. Но прибыль составляет $$7333000/969000=0,75$$ от оптимальной.. Дефицитным является 4 вид комплектующих.
Входные данные
$$Z(x)$$ – прибыль
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 8 \\ 15 \\ 3 \end{pmatrix}$$ - план выпуска
Матрица затрат ресурсов: $$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$
$$Z(x):=d\cdot x$$
$$Given$$
$$a\cdot x \le B$$
$$x \ge P$$
$$x1:=Maximize(Z,x)$$
$$x1:=\begin{pmatrix} 8 \\ 19 \\ 3 \end{pmatrix}$$
Прибыль: $$Z(x1):=733000$$
Остаток ресурсов: $$B-a\cdot x1:=\begin{pmatrix} 79 \\ 68\\ 68 \\ -0 \\15 \end{pmatrix}$$
Задача. 4.3.
Фирма по сборке компьютеров (см. задачу 4.1) получила заказ на увеличенный план выпуска компьютеров : 1 модель- 40 шт., 2 модель- 20 шт., 3 модель- 10 шт. Данные по запасам комплектующих и ценам приведены в таблице 4.1. Определить оптимальную прибыль при заданном плане и имеющихся ресурсах. Можно ли выполнить такой план ?
Решение. Для увеличенного плана выпуска задача не имеет решения, система несовместна. Экономическая причина – требуемые значения плана ($$P_j$$) недостижимы при имеющихся запасах ресурсов ($$B_i$$).
Входные данные
$$Z(x)$$ – прибыль
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$ - план выпуска
Матрица затрат ресурсов: >$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$
$$Z(x):=d\cdot x$$
$$Given$$
$$a\cdot x \le B$$
$$x \ge P$$
$$x1:=Maximize(Z,x)$$
$$x1:= \Box $$
Прибыль: $$Z(x1):= \Box$$
Остаток ресурсов: $$B-a\cdot x1:= \Box$$
Возможны два пути решения проблемы:
Решение задачи 4.3 в комплектной постановке. Задача - определить, какую часть плана можно выполнить при имеющихся ресурсах. Для этого случая воспользуемся моделью, приведенной в [21]. Ставится цель определения максимальной доли выпуска требуемого плана при имеющихся ресурсах. Разработана quot;комплектнаяquot; постановка задачи. Вводится новая переменная $$y$$ – возможный процент достижения плана, определяется ее оптимальное значение при уменьшенном плане, ресурсные и технологические ограничения задачи записываются без изменений.: Целевая функция $$K(y,x_j )$$ строится как функция двух аргументов: скаляра $$y$$ и вектора переменных продукции $$x_j,\;j=\overline{1,m}$$, который неявно зависит от $$y$$. .Решение получается в виде вектора $$y1$$ с элементами $$y1_1$$ - .найденная доля выполнения плана и $$y1_2$$.- найденный вектор переменных продукции.
Система уравнений в quot;комплектнойquot; постановке
$$ \left\{ \begin{array}{lc} K(x_j,y)\to\max \sum_{j}^{m}a_{ij}\cdot x_j\le B_i \\ x_j\ge P_j\cdot y\\ x_j\ge 0 \\ \end{array} \right\ $$
Ниже приведен листинг решения в MathCad (комплектная постановка).
Входные данные
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$ - план выпуска
$$Z(x)$$ – прибыль
Матрица затрат ресурсов: >$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$, $$y:=1$$
Решение:
$$Z(x):=d\cdot x$$
$$K(y,x):=y$$ – целевая функция
$$Given$$
$$a\cdot x \le B$$
$$x \ge P \cdot y$$
$$y1:=Maximize(K,y,x)$$, $$y1:=\begin{pmatrix} 0.429\\ \{3.1\} \end{pmatrix}$$
Доля плана: $$y1_1=0.43$$
Количество выпуска: $$y1_2:=\begin{pmatrix} 17 \\ 9\\ 4 \end{pmatrix}$$
Прибыль: $$Z(y1_2):= 494143$$
Израсходовано ресурсов: $$a\cdot y1_2:=\begin{pmatrix} 141 \\ 60\\ 116 \\ 60 \\ 47 \end{pmatrix}$$
Остаток ресурсов: $$B-a\cdot y1_2:=\begin{pmatrix} 99\\ 85\\ 39\\ 0\\23\end{pmatrix}$$
Как видно, план можно выполнен только на 43%, но это оптимальный процент при имеющихся условиях. Полученная прибыль при таком плане еще меньше, чем в задаче 4.2 и ресурсов остается больше.
Решение задачи 4.3 с добавлением ресурсов. Добавление недостающих ресурсов для выполнения полного плана. Воспользуемся t-моделью постановки задачи, представленной в [21], - нахождения минимума дополнительного количества ресурсов, необходимых для выпуска продукции в соответствии с планом. В предлагаемой t-модели вводятся новые переменные $$t_i,\;i=\overline{1,n}$$ – значения дополнительных ресурсов каждого вида продукции $$i$$. Цель задачи – минимум суммарного количества добавляемых ресурсов. В ресурсные ограничения вводятся дополнительные неизвестные ресурсы, плановые и технологические ограничения вводятся в t-модель без изменений. Целевая функция $$T(x,t)$$ вводится как функция двух аргументов: вектора добавочных ресурсов $$t_i,\;i=\overline{1,n}$$ и вектора переменных продукции $$x_j,\;j=\overline{1,m}$$ , который неявно зависит от $$t_j$$
Система уравнений в постановке t -модели
$$ \left\{ \begin{array}{lc} T(x_j,t_i)=\sum_{i}^{n}to\min \sum_{j}^{m}a_{ij}\cdot x_j\le B_i+t_i \\ x_j\ge P_j \\ x_j\ge 0 \\ \end{array} \right\ $$
Листинг решения в Mathcad показан ниже. .Решение получается в виде двумерной переменной $$t1$$ с элементами $$t1_1$$ найденный вектор продукции. и $$t1_2$$, найденный вектор добавочных ресурсов
Далее, имея полученные значения добавочных ресурсов, решаем исходную задачу. На диаграммах показаны старые ресурсы, новые ресурсы. Видны добавочные ресурсы, добавлено ровно столько, чтобы выполнить план. В результате план выполняется и ресурсов не остается
Входные данные
$$c:=\begin{pmatrix} 10000 35000 20000 \end{pmatrix}$$ - цена реализации
$$q:=\begin{pmatrix} 1800 2700 2100\end{pmatrix}$$ - затраты на один компьютер
$$d:=c-q$$ - прибыль на один компьютер
$$P:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$ - план выпуска
$$Z(x)$$ – прибыль
Матрица затрат ресурсов: >$$a:=\begin{pmatrix} 4 6 5 \\ 1 3 4 \\ 5 2 3 \\ 2 2 2 \\ 1 2 3 \\ \end{pmatrix}$$
Матрица запасов ресурсов: $$B:=\begin{pmatrix} 240 \\ 145\\ 155 \\ 60 \\ 70 \end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$, $$t:=\begin{pmatrix} 1\\ 1\\ 1 \\ 1\\ 1\end{pmatrix}$$
Решение:
$$Z(x):=d\cdot x$$
$$T(x,t):=t_1+t_2+t_3+t_4+t_5$$ – добавочные ресурсы
$$Given$$
$$a\cdot x \le B+t$$
$$x \ge P$$
$$t1:=Minimize(T,x,t)$$
$$t1:=\begin{pmatrix} \{3.1\}\\ \{5.1\} \end{pmatrix}$$
Вектор решений – количество компьютеров: $$t1_1:=\begin{pmatrix} 40 \\ 20 \\ 10 \end{pmatrix}$$
Добавочные ресурсы: $$t1_2:=\begin{pmatrix} 90\\ -5\\ 115 \\ 80 \\ 40 \end{pmatrix}$$
Новые ресурсы: $$B+t1_2:=\begin{pmatrix} 330\\ 140\\ 270\\ 140\\ 110\end{pmatrix}$$
Прибыль: $$Z(t1_1)=1153000$$
План: $$P:=\begin{pmatrix} 40\\ 20\\ 10\end{pmatrix}$$
Ресурсы: $$B1:=\begin{pmatrix} 330\\ 140\\ 270\\ 140\\ 110\end{pmatrix}$$
Начальные значения: $$x:=\begin{pmatrix} 1\\ 1\\ 1\end{pmatrix}$$
$$Z(x):=d\cdot x$$
$$T(x,t):=t_1+t_2+t_3+t_4+t_5$$ – добавочные ресурсы
$$Given$$
$$a\cdot x \le B1$$
$$x \ge P$$
$$x:=Maximize(Z,x)$$
$$x=\begin{pmatrix} 40\\ 20\\ 10\end{pmatrix}$$, $$Z(X)=1153000$$
Новые ресурсы: $$B1=\begin{pmatrix} 330\\ 140\\ 270\\ 140\\ 110\end{pmatrix}$$
Старые ресурсы: $$B=\begin{pmatrix} 240\\ 145\\ 155\\ 60\\ 70\end{pmatrix}$$
Остаточные ресурсы, новый выпуск: $$B1-a\cdot x=\begin{pmatrix} -0\\ 0\\ -0\\ -0\\ -0\end{pmatrix}$$
Транспортная задача – задача поиска оптимального распределения поставок однородных грузов [20]. В общей постановке формулируется так: составить план поставок продукции (грузов) от поставщиков к потребителям, имеющий минимальную стоимость затрат.
Модель задачи.
Входные переменные:
Управляемые переменные - $$x_{ij}$$ - количество единиц продукта, доставленного от $$i$$- го поставщика к $$j$$-му потребителю,
Выходные показатели – суммарные затраты доставки продукции $$F=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}$$.
Целевая функция – результирующий, оптимизируемый параметр – суммарные затраты. Цель решения задачи – нахождение значений управляемых переменных $$x_{ij}$$, обеспечивающих минимум целевой функции $$F$$.
$$F=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}\to \min$$
Математическая модель транспортной задачи может быть закрытой (сбалансированной) - все грузы должны быть вывезены, и все потребности полностью удовлетворены. В этом случае $$\sum_{i}^{m}A_i=\sum_{j}^{n}B_j$$.
На практике обычно встречается случай открытой (несбалансированной) транспортной задачи, когда производство не совпадает с потреблением. В этом случае открытая модель сводится к закрытой. Для этого вводятся либо фиктивный поставщик (случай дефицита), либо фиктивный потребитель (случай перепроизводства). Стоимость перевозок единицы продукции, как от фиктивного поставщика, так и до фиктивного потребителя полагают раной нулю, так как в обоих случаях продукция не перевозится.
$$\sum_{i}^{m}A_i-\sum_{j}^{n}B_j=объем \;продукции\; фиктивного\; поставщика\; (потребителя)$$
При добавлении фиктивного поставщика (потребителя) количество поставщиков $$m$$ (или потребителей $$n$$) увеличивается на единицу.
В результате имеем систему уравнений.
$$ \left\{ \begin{array}{lc} \sum_{i=1}^{m}x_{ij}=A_i \; (i=\overline{1,m}) \\ \sum_{j=1}^{n}x_{ij}=A_j \; (j=\overline{1,n}) \\ x_j\ge 0, \; i=\overline{1,m}, \; j=\overline{1,n} \\ x_j\ge P_j \\ F=\sum_{i=1}^{m}\sum_{j=1}^{n}c_{ij}x_{ij}\to \min \\ \end{array} \right\ $$
Задача 4.4.
Имеется 4 мебельные фирмы и 5 центров распределения товаров - магазинов. Планируется наладить перевозки продукции с фирм в магазины. Фирмы имеют следующие возможности производства: 280, 150, 225, 175 единиц в месяц. Пяти магазинам необходимо поставить 100, 200, 50, 250 и 150 единиц товара в месяц соответственно. Необходимо так спланировать перевозки, чтобы уменьшить (оптимизировать) транспортные расходы.
Стоимость перевозок единиц продукции приведена в таблице.
| Фирмы/магазины | Олимп | Сфера | Квартира | Уют | Товары для дома |
| Томек | 1,50 | 2 | 2,25 | 2,25 | 2,25 |
| СуперМебель | 2,5 | 2,2 | 1,65 | 1 | 1,5 |
| Мебель-лес | 2,3 | 1,7 | 1,5 | 1,4 | 1,6 |
| ЦентрМебель | 2,3 | 0,5 | 1,85 | 1,35 | 1,25 |
Решение (рис. 4.4). Определим тип задачи. Суммарное количество производимого товара составляет $$\sum_{i}^{m}A_i=830$$, количество товара, которое надо доставить $$\sum_{j}^{n}B_j=750$$. Задача "открытого типа". Имеем случай перепроизводства. Сбалансируем задачу, сведем к "закрытому типу", введя фиктивного потребителя с потребностью $$\sum_{i}^{m}A_i-\sum_{j}^{n}B_j=80$$. Стоимость перевозок единицы продукции до фиктивного потребителя считаем равной нулю.
В Mathcad транспортная задача решается аналогично задаче производства – в матричном виде, с помощью блока $$given$$ и в данном случае функции $$miniimize$$. Особенность заключается в том, что матрица неизвестных двумерна. Для построения ограничений – нахождения суммы по строкам и по столбцам вводим единичные векторы. . Порядок действий тот же. Документ Mathcad решения задачи показан на рис.4.3.
$$ORIGIN:=1$$
Входные данные
$$m:=4, \; n:=5$$
$$\underline{i}:=1..\underline{m}$$ - фирмы-поставщики
$$\underline{j}:=1..\underline{n}$$ - магазины-потребители
Производство фирм поставщиков: $$A:=\begin{pmatrix} 280\\ 150\\ 225\\ 175 \end{pmatrix}$$
Потребность магазинов: $$B:=\begin{pmatrix} 100\\ 200\\ 50\\ 250\\ 150\end{pmatrix}$$
$$\sum_{\underline{i}}^{}\underline{A}_{\underline{i}}=830$$, $$\sum_{\underline{j}}^{}\underline{B}_{\underline{j}}=750$$, $$\sum_{\underline{i}}^{}\underline{A}_{\underline{i}}-\sum_{\underline{j}}^{}\underline{B}_{\underline{j}}=80$$
Вводим фиктивного потребителя в магазин с потребностью 80 ед.
$$\underline{n}:=\underline{n}+1=6$$, $$\underline{j}:=1..\underline{n}$$
$$\underline{Потребители}+\underline{фиктивный}$$
$$B:=\begin{pmatrix} 100\\ 200\\ 50\\ 250\\ 150\\ 80\end{pmatrix}$$
Стоимость перевозки ед. продукции: $$с:=\begin{pmatrix} 1.5 2 1.55 2.25 2.25 0\\ 2.5 2.2 1.65 1 1.5 0 \\ 2.3 1.7 1.5 1.4 1.6 0\\ 2.3 0.5 1.85 1.35 1.25 0\end{pmatrix}$$
Решение:
$$\underline {F}(\underline {x})=\sum_{\underline {i}=1}^{m}\sum_{\underline {j}=1}^{\underline {n}}(\underline {x}_{\underline {i}\underline {j}}\cdot \underline {c}_{\underline {i}\underline {j}})$$
Начальные значения: $$\underline{x}_{\underline {i},\underline {j}}:=1$$
Единичный вектор-столбец для магазинов: $$\underline{v}_{\underline {j}}:=1$$
Единичный вектор-столбец для поставщиков: $$\underline {k}_{\underline {j}}:=1$$
$$\underline{Given}$$
$$\underline{x}\cdot \underline{v}=\underline{A}$$
$$\underline{x}^T\cdot \underline{k}=\underline{B}$$
$$x \ge 0$$
$$\underline{x}:=\underline{Minimize}(\underline{F}, \underline{x})$$
Оптимальные перевозки: $$x=\begin{pmatrix} 100 25 50 0 25 80\\ 0 0 0 150 0 0 \\ 0 0 0 100 125 0\\ 0 175 0 0 0 0\end{pmatrix}$$
Затраты: $$\underline {F}(\underline {x})=911.25$$
$$\underline {x}\cdot \underline {y}=\begin{pmatrix} 280\\ 150\\ 225\\ 175 \end{pmatrix}$$
$$\underline {x}^T\cdot \underline {k}=\begin{pmatrix} 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
(рис 4.3) Листинг решения задачи 4.4. Оптимальные перевозки. Показан фиктивный потребитель.
Результат решения показывает, как спланировать доставку. Минимальные затраты составляют F=911ед. Излишек товара выгоднее отправить в "Товары для дома" (магазин 5).
Есть транспортные задачи, в которых пункты отправления и назначения являются промежуточными, через них переправляются товары в конечный пункт назначения. В данной постановке промежуточные пункты выступают и как потребители и как поставщики. В данном случае формируется единая транспортная матрица, в которой количество поставщиков и количество потребителей увеличивается на число промежуточных пунктов.
Задача 4.5.
Усложним условия задачи 4.4. Фирмы производят и вывозят мебель на 3 склада. Необходимо распределить доставку товаров от поставщиков на склады, со складов в магазины по заказам так, чтобы оптимизировать транспортные расходы. Фирмы производят 280, 150, 225, 175 единиц. Вместимость складов 400, 300, 350 единиц. Магазины заказывают 100, 200, 50, 250 и 150 единиц товара, соответственно. Стоимость перевозок единиц продукции с фирм на склады и со склада в магазины приведена в таблице 4.4, таблице 4.5.
| Фирмы | Склад 1 | Склад 2 | Склад 3 | Объемы производства на фирмах |
| Фирма 1 | 2,4 | 3,0 | 2,3 | 280 |
| Фирма 2 | 3,9 | 3,2 | 4,3 | 150 |
| Фирма 3 | 3,3 | 3,3 | 2,1 | 225 |
| Фирма 4 | 4,3 | 2,7 | 3,2 | 175 |
| Вместимость складов | 400 | 300 | 350 |
| Склады | "Олимп" | "Сфера" | "Квартира" | "Уют" | "Товары для дома" |
| Склад 1 | 5,8 | 3,9 | 3,6 | 5,4 | 2,8 |
| Склад 2 | 4,8 | 5,5 | 3,3 | 2,0 | 2,0 |
| Склад 3 | 2,2 | 3,3 | 3,6 | 3,4 | 1,6 |
| Потребности | 100 | 200 | 50 | 250 | 150 |
Модель задачи.
В модель задачи. добавляется входная переменная склады - три склада $$D_k\; (k=\overline{1,s}),\; s=3$$. Склады выступают и как потребители, и как поставщики. Формируется единая матрица, в которой количество элементов поставщиков и количество потребителей увеличивается на число складов: строки = поставщики плюс склады, столбцы = склады плюс магазины. Для запрета перевозок со склада на другой склад и непосредственно от поставщиков в магазины устанавливается очень большой, нереальный тариф (999999).
Таблица стоимости доставки со склада на склад имеет вид:
| Склад 1 | Склад 2 | Склад 3 | |
| Склад 1 | 0 | 999999 | 999999 |
| Склад 2 | 999999 | 0 | 999999 |
| Склад 3 | 999999 | 999999 | 0 |
Таблица стоимости доставки со склада в магазин имеет вид:
| Фирмы | "Олимп" | "Сфера" | "Квартира" | "Уют" | "Товары для дома" |
| Фирма 1 | 999999 | 999999 | 999999 | 999999 | 999999 |
| Фирма 2 | 999999 | 999999 | 999999 | 999999 | 999999 |
| Фирма 3 | 999999 | 999999 | 999999 | 999999 | 999999 |
| Фирма 4 | 999999 | 999999 | 999999 | 999999 | 999999 |
Задача решается в объединенной матрице. $$M_{i+k, k+j}$$ стоимость доставки в объединенной матрице стоимостей. Баланс устанавливается по сумме производства поставщиков и емкости складов, с одной стороны, и емкости складов и потребности магазинов, с другой стороны. $$\sum_{i}^{4}A_i+\sum_{k}^{3}D_k=\sum_{k}^{3}D_k+\sum_{j}^{5}B_j$$.
Здесь $$\sum_{i}^{4}A_i+\sum_{k}^{3}D_k=1880$$, $$\sum_{k}^{3}D_k+\sum_{j}^{5}B_j=1800$$ данной задаче необходим фиктивный потребитель с потребностью 80 ед. В остальном модель аналогична предыдущей модели. Система уравнений:
$$ \left\{ \begin{array}{lc} \sum_{i=1}^{m+s}x_{ij}=A_i(i=\overline{1,m})+D_k(k=\overline{1,s}) \\ \sum_{j=1}^{n+s}x_{ij}=B_j(j=\overline{1,n})+D_k(k=\overline{1,s}) \\ x_j\ge 0, \; i=\overline{1,m+s}, \; j=\overline{1,n+s} \\ F=\sum_{i}^{n+s}\sum_{j}^{m+s}M_{ij}\cdot x_{ij}\to \min \\ \end{array} \right\ $$
Решение. В Mathcad задача строится аналогично транспортной задаче. Данные вводятся в матричном виде, оптимизация реализуется с помощью блока given и функции $$minimize$$, ограничения вводятся с единичные векторы. Здесь ообенность заключается в том, строится объединенная матрица. Для этого используем встроенные функции для матричных операций
Функция $$augment (M1, M2)$$ объединяет в одну матрицы $$М1$$ и $$М2$$, имеющие одинаковое число строк.
Функция $$stack (M1, M2)$$ объединяет в одну матрицы $$М1$$ и $$М2$$, имеющие одинаковое число столбцов. (см. Приложение 2). Документ Mathcad решения задачи показан ниже.
$$ORIGIN:=1$$
Входные данные
$$\underline{i}:=1..4$$ - фирмы-поставщики
$$\underline{j}:=1..5$$ - магазины-потребители
$$\underline{k}=1..3$$ - склады
Производство фирм поставщиков: $$A:=\begin{pmatrix} 280\\ 150\\ 225\\ 175 \end{pmatrix}$$
Емкость складов: $$D:=\begin{pmatrix} 400\\ 300\\ 350 \end{pmatrix}$$
Потребность магазинов: $$B:=\begin{pmatrix} 100\\ 200\\ 50\\ 250\\ 150\end{pmatrix}$$
$$\sum_{\underline{i}=1}^{4}\underline{A}_{\underline{i}}=830$$, $$\sum_{\underline{k}=1}^{3}\underline{D}_{\underline{k}}=1050$$, $$\sum_{\underline{j}=1}^{5}\underline{B}_{\underline{j}}=750$$
$$\underline{поставщики}+\underline{склады}$$: $$\sum_{\underline{i}}^{}\underline{A}_{\underline{i}}+\sum_{\underline{k}}^{}\underline{D}_{\underline{k}}=1880$$
$$\underline{склады}+\underline{магазины}$$: $$\sum_{\underline{j}}^{}\underline{B}_{\underline{j}}+\sum_{\underline{k}}^{}\underline{D}_{\underline{k}}=1800$$
Вводим фиктивного потребителя в магазин с потребностью 80 ед.
$$\underline{j}:=1..6 $$, $$\underline{j}:=1..\underline{n}$$
$$\underline{магазины}+\underline{фиктивный}$$$$\underline {B}:=\begin{pmatrix} 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
Стоимость перевозки ед. продукции от фирмы на склад: $$с:=\begin{pmatrix} 2.4 3 2.3 \\ 3.9 3.2 4.3 \\ 3.3 3.3 2.1\\ 4.3 2.7 3.2 \end{pmatrix}$$
Стоимость перевозки ед. продукции со склада в магазин: $$с:=\begin{pmatrix} 5.8 3.9 3.6 5.4 2.8 0 \\ 4.8 5.5 3.3 2.0 2.0 0 \\ 2.2 3.3 3.6 3.4 1.6 0 \end{pmatrix}$$
Решение
матрица стоимостей фиктивной доставки со склада на склад: $$underline{cc}:=\begin{pmatrix} 0 999999 999999 \\ 999999 0 999999 \\ 999999 999999 0 \end{pmatrix}$$
матрица стоимостей фиктивной доставки с фирмы в магазин: $$underline{cc1}:=\begin{pmatrix} 999999 999999 999999 999999 999999 0 \\ 999999 999999 999999 999999 999999 0 \\ 999999 999999 999999 999999 999999 0 \\ 999999 999999 999999 999999 999999 0 \end{pmatrix}$$
Объединяем матрицы: $$\underline{M1}:=\underline{argument}(\underline{c},\underline{cc1})$$, $$\underline{A1}:=\underline{stack}(\underline{A},\underline{D})$$
$$\underline{M2}:=\underline{argument}(\underline{cc},\underline{c1})$$, $$\underline{B1}:=\underline{stack}(\underline{D},\underline{B})$$
$$\underline {A1}:=\begin{pmatrix} 280\\ 150\\ 225\\ 175\\ 400\\ 300 \\ 350 \end{pmatrix}$$, $$\underline {B1}:=\begin{pmatrix} 400\\ 300\\ 350\\ 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
$$\underline {M1}:=\begin{pmatrix} 2.4 3 2.3 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0\\ 3.9 3.2 4.3 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0\\ 3.3 3.3 2.1 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0 \\ 4.3 2.7 3.2 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 10\times 10^5 0 \end{pmatrix}$$
$$\underline {M2}:=\begin{pmatrix} 0 10\times 10^5 10\times 10^5 5.8 3.9 3.6 5.4 2.8 0\\ 10\times 10^5 0 10\times 10^5 4.8 5.5 3.3 2 2 0\\ 10\times 10^5 10\times 10^5 0 2.2 3.3 3.6 3.4 1.6 0 \end{pmatrix}$$
$$\underline{M}:=\underline{stack}(\underline{M1},\underline{M2})$$, $$\underline {M}:=\begin{pmatrix} 2.4 3 2.3 999999 999999 999999 999999 999999 0\\ 3.9 3.2 4.3 999999 999999 999999 999999 999999 0\\ 3.3 3.3 2.1 999999 999999 999999 999999 999999 0 \\ 4.3 2.7 3.2 999999 999999 999999 999999 999999 0 \\ 0 999999 999999 5.8 3.9 3.6 5.4 2.8 0\\ 999999 0 999999 4.8 5.5 3.3 2 2 0\\ 999999 999999 0 2.2 3.3 3.6 3.4 1.6 0\end{pmatrix}$$
$$i:=1..7.\; j:=1..9$$
Начальные значения: $$x_{i,j}:=1$$
Единичный вектор для строк и столбцов $$v1_i:=1,\; v2_j:=1$$
$$F(x):=\sum_{i=1}^{7}\sum_{j=1}^{9}(x_{i,j}\cdot M_{i,j})$$
$$Civen$$
$$x^T\cdot v1=B1$$
$$x\cdot v2=A1$$
$$x\ge 0$$
Оптимальные перевозки: $$x:=Minimize(F,x)$$
Затраты: $$F(x)=26000065$$
Ограничения:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline 1 2 3 4 5 6 7 8 9 \\ \hline 1 113 13 35 0 0 0 0 0 0 \\ \hline 2 4 18 49 0 0 0 0 0 9 \\ \hline 3 110 78 37 0 0 0 0 0 0 \\ \hline 4 100 18 56 0 0 0 0 0 1 \\ \hline 5 73 0 0 39 94 42 27 126 0 \\ \hline 6 0 54 0 10 81 8 137 9 0\\ \hline 7 0 0 173 51 25 0 86 15 0 \\ \hline \end{array}$$
$$x\cdot v2:=\begin{pmatrix} 280\\ 150\\ 225\\ 175\\ 400\\ 300 \\ 350 \end{pmatrix}$$, $$x^T\cdot v1:=\begin{pmatrix} 400\\ 300\\ 350\\ 100\\ 200\\ 50\\ 250 \\ 150 \\ 80\end{pmatrix}$$
(рис 4.4) Диаграмма доставки
Планирование штатного расписания относится к типу задач оптимального распределения трудовых ресурсов.
Задача 4.6.
Необходимо укомплектовать штат работников в диспетчерской фирме в соответствии со следующими требованиями: каждый день недели должно работать определенное количество работников (см. таблицу). При этом служащие должны иметь два выходных дня. В каждой группе – не менее 2 человек. Руководитель фирмы заинтересован в экономии заработной платы. Обеспечить работу в течение недели фирмы в соответствии с ресурсным планом при минимальном фонде заработной платы.
Потребность в работниках каждый день недели
| День | Вс. | Пн. | Вт. | Ср. | Чт. | Пт. | Сб. |
| Кол. работников | 22 | 17 | 13 | 14 | 15 | 18 | 24 |
Постановка задачи.
Организуем группы, каждая из которых имеет свои выходные дни - два смежных дня. У первой группы выходные - Вс и Пн., у второй - Пн и Вт. и т.д. Всего - 7 групп. Дневная оплата каждой группы приведена в таблице. Задача – определить количество работников в каждой группе при минимальной суммарной оплате.
| № группы | Вых.дни | Количество работников | Оплата P. |
| 1 | Вс.,Пн. | х1 | 50 |
| 2 | Пн. Вт. | х2 | 45 |
| 3 | Вт. Ср. | х3 | 45 |
| 4 | Ср. Чт. | х4 | 45 |
| 5 | Чт. Пт. | х5 | 45 |
| 6 | Пт. Суб. | х6 | 55 |
| 7 | Суб. Вс | х7 | 50 |
Модель задачи.
Выбираем объекты для моделирования: и исходные данные - т.е. что мы имеем.
Входные переменные:
| Группа | Вс. | Пн. | Вт. | Ср. | Чт. | Пт. | Сб. |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
| 3 | 1 | 1 | 0 | 0 | 1 | 1 | 1 |
| 4 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 6 | 1 | 1 | 1 | 1 | 1 | 0 | 0 |
| 7 | 0 | 1 | 1 | 1 | 1 | 1 | 0 |
Управляемые переменные – $$x_i$$ - количество работников в $$i$$ группе,
Ограничения
Ресурсное - $$B_j\;(j=\overline{1,m})$$ - количество работающих в j день недели
Плановое – $$M_i$$ требуемое количество работников в $$i$$ группе .
Выходные показатели – суммарная заработная плата $$S=\sum_{i=1}^{m}P_i\cdot x_i$$.
Целевая функция – результирующий, оптимизируемый параметр – суммарная заработная плата минимальна.
$$S=\sum_{i=1}^{m}P_i\cdot x_i \to \min$$
В результате имеем систему уравнений.
$$ \left\{ \begin{array}{lc} \sum_{i=1}^{m}с_{ij}\cdot x_i=B_j\;(j=\overline{1,m}) \\ x_i\ge 0,\;(i=\overline{1,m}) \\ x_i\ge P_i\\ x_i\ge 2 \\ S=\sum_{i=1}^{m}P_i\cdot x_i \to \min \end{array} \right\ $$
Решение. Данные вводятся в виде матриц. Матрица выхода бригад на работу двумерна. Задача решается с помощью блока $$given$$ и функции $$minimize $$. Документ Mathcad решения задачи показан ниже.
Входные данные
$$ORIGIN:=1$$
$$m:=7$$
$$i=1..m$$ - номер группы, $$j:=1..m$$ – день недели
Потребности работников: $$B:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
Оплата по группам: $$P:=\begin{pmatrix} 50\\ 45\\ 45\\ 45\\ 45\\ 55\\ 50\end{pmatrix}$$
Матрица выхода работников: $$c:=\begin{pmatrix} 0 0 1 1 1 1 1\\ 1 0 0 1 1 1 1\\ 1 1 0 0 1 1 1\\ 1 1 1 0 0 1 1\\ 1 1 1 1 0 0 1\\ 1 1 1 1 1 0 0\\ 0 1 1 1 1 1 0 \end{pmatrix}$$
Решение:
Начальные значения:
$$x_i:=1$$ – количество работников
$$S(x):=P\cdot x$$
$$Given$$
$$c\cdot x \ge B$$
$$x \ge 2$$
$$x1:=Minimize(S,x)$$
$$x1=\begin{pmatrix} 2\\ 4\\ 7\\ 6\\ 5\\ 2\\ 2 \end{pmatrix}$$
Заработная плата: S(x)=335
Ограничение: $$c\cdot x1:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
(рис 4.5) Количество работников в группах, имеющих разные выходные
Потребности работников
$$RR:=c\cdot x1$$
$$RR:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
Ограничение:
$$B:=\begin{pmatrix} 22\\ 17\\ 13\\ 14\\ 15\\ 18\\ 24 \end{pmatrix}$$
(рис 4.6) Количество работающих по дням недели
Возможность оптимизации межотраслевого баланса появляется, если коэффициенты прямых затрат отражают затраты не средние по отрасли, а для каждого способа и технологии производства. В таких моделях межотраслевого баланса представлено отдельно производство каждого вида продукции. Построение оптимизационных моделей межотраслевого баланса позволяет в условиях ограниченности ресурсов находить наиболее эффективные комбинации ресурсов для максимизации конечного продукта [22].
Задача 4.7.
Крупное структурное предприятие состоит из 6 подразделений, каждый из которых выпускает по 1 виду продукции. Отношения между подразделениями определены технологической матрицей прямых затрат. В таблице 4.8 указаны нормы прямых затрат подразделений, используемых в качестве промежуточного продукта для выпуска единицы продукции для каждого подразделения. Известны максимально допустимые ресурсы подразделений предприятия. Известны цены на готовую продукцию, которая направляется на внешний рынок. Оптимизировать новую программу – плановую валовую продукцию, так, чтобы распределение готовой продукции на собственные потребности и экспорт, давало максимальный доход от реализованной продукции.
| Подразделение 1 | Подразделение 2 | Подразделение 3 | Подразделение 4 | Подразделение 5 | Подразделение 6 | Цена | |
| Подразделение 1 | 0,01 | 0,03 | 0,05 | 0,07 | 0,09 | 0,12 | 2 |
| Подразделение 2 | 0,03 | 0,05 | 0,06 | 0,08 | 0,1 | 0,13 | 6 |
| Подразделение 3 | 0,05 | 0,07 | 0,07 | 0,09 | 0,11 | 0,14 | 3 |
| Подразделение 4 | 0,07 | 0,09 | 0,08 | 0,1 | 0,12 | 0,15 | 7 |
| Подразделение 5 | 0,09 | 0,11 | 0,09 | 0,11 | 0,13 | 0,16 | 8 |
| Подразделение 6 | 0,11 | 0,13 | 0,1 | 0,12 | 0,14 | 0,17 | 1 |
| Ресурсы подразделений | 400 | 300 | 900 | 500 | 450 | 250 |
Модель задачи.
Входные переменные:
Управляемые переменные - $$X_j$$ - вектор плановой валовой продукции.
Выходные показатели –
$$Y_j$$ -. конечная продукция подразделений,
$$Y=(E-A)\cdot X$$ - в соответствии с уравнением межотраслевого баланса, $$Z(X)$$ - доход от реализации конечной продукции на внешнем рынке..
Целевая функция –оптимизируемый параметр – доход от реализации конечной продукции.
$$Z(X)= (E-A)\cdot X \cdot C$$
$$Z(X)\to \max$$
Ограничения.
$$X_j\le M_j$$ – ресурсные ограничения
$$(E-A)\cdot X > 0$$ – конечный продут положителен,
$$X_j\ge 0$$
В результате имеем систему уравнений.
$$ \left\{ \begin{array}{lc} X_j\le M_j \\ (E-A)\cdot X > 0 \\ X_j\ge 0\\ Z(X)=(E-A)\cdot X \cdot C \to \max \end{array} \right\ $$
Решение. В программе Mathcad задача решается в матричном виде, аналогично всем приведенным примерам. Система уравнений с оптимизацией решается численно с помощью блока $$given$$ и функции $$maximize()$$.
Входные данные
$$ORIGIN:=1$$
$$i:=1..6, \; j:=1..6$$
Матрица промежуточных потоков затрат: $$A:=\begin{pmatrix} 0.01 0.03 0.05 0.07 0.09 0.12\\ 0.03 0.05 0.06 0.08 0.1 0.13\\ 0.05 0.07 0.07 0.09 0.11 0.14\\ 0.07 0.09 0.08 0.1 0.12 0.15\\ 0.09 0.11 0.09 0.11 0.13 0.16\\ 0.11 0.13 0.1 0.12 0.14 0.17 \end{pmatrix}$$
Ресурсы подразделений: $$M:=\begin{pmatrix} 400\\ 300\\ 900\\ 500\\ 450\\ 250 \end{pmatrix}$$
Цена: $$C:=\begin{pmatrix} 2\\ 6\\ 3\\ 7\\ 8 \\ 1 \end{pmatrix}$$
$$E:=identity(6)$$ – единичная матрица
$$X$$ – валовый планируемый выпуск
$$(E-A)\cdot X$$ – вектор конечной продукции
$$Z$$ – доход от реализации конечной продукции – целевая функция
Оптимизация дохода: $$Z - \max$$
Решение:
$$Z(X):=[(E-A)\cdot X]\cdot C$$, $$v1_i:=1$$ – единичный вектор
Начальные значения:
$$X_j:=1$$, $$A\cdot diag(X)\cdot v1$$ – затраты – сумма по столбцам
$$Given$$
$$X\le M$$
$$(E-A)\cdot X > 0$$
$$X\ge 0$$
$$X1:=Maximixe (Z,X)$$
Оптимальный план валового выпуска: $$X1:=\begin{pmatrix} 131\\ 300\\ 311\\ 500\\ 450\\ 250\end{pmatrix}$$
Конечная продукция: $$Y:=(E-A)\cdot X1$$, $$Y:=\begin{pmatrix} -0\\ 145\\ 132\\ 297\\ 224 \\ 0 \end{pmatrix}$$
Оптимальный доход: $$Z(X1)=5137$$
Промежуточные поставки: $$A\cdot diag(X1)$$, $$A\cdot diag(X1):=\begin{pmatrix} 1.313 9 15.526 35 40.5 30 \\ 3.94 15 18.632 40 45 32.5 \\ 6.567 21 21.737 45 49.5 35\\ 9.194 27 24.842 50 54 37.5 \\ 11.821 33 27.947 55 58.5 40 \\ 14.447 39 31.053 60 63 42.5\end{pmatrix}$$
Затраты – суммы по столбцам $$S:= A\cdot diag(X1) \cdot v1$$, $$S:=\begin{pmatrix} 131.34\\ 155.072\\ 178.804\\ 202.536\\ 226.268\\ 250\end{pmatrix}$$
(рис 4.7) Валовая продукция, конечный продукт
(рис 4.8) Затраты
Рассмотрены основные типы оптимизационных задач.
Задача формирования оптимальной производственной программы - три модели: модель получения максимальной прибыли без заданного плана и с планом, модель в комплектной постановке - получение максимальной доли плана выпуска продукции при нехватке ресурсов, т-модель - нахождения минимума дополнительного количества ресурсов, необходимых для выполнения полного плана. Две модели транспортной задачи. Задача оптимального комплектования штата работников. Задача максимизации конечного продукта в схеме межотраслевого баланса. Для каждой задачи определены входные данные, построена математическая модель. Каждая модель представлена в Mathcad в виде системы матричных уравнений. Системы уравнений решены численно - в блоке $$given\; maximize\; (minimize)$$. Построены диаграммы результирующих данных.
Оптимизационная задача – задача, цель которой состоит в нахождении наилучшего (оптимального) с точки зрения некоторого критерия варианта использования имеющихся ресурсов.
Оптимизационная модель – математическая модель решения оптимизационной задачи.
Математическое программирование - направление математики, изучающее методы решения оптимизационных задач.
Целевая функция – функция, определяющая критерий оптимальности в оптимизационной задаче.
Управляемые переменные - переменные целевой функции, которые подвергаются изменению в процессе поиска решения.
Ограничения – системы уравнений и неравенств, ограничивающих область решения оптимизационной задачи в соответствии с заданными условиями.
Нормированная стоимость - изменение целевой функции при изменении соответствующего управляемого параметра на единицу.
Транспортная задача - оптимизационная задача оптимального прикрепления потребителей к поставщикам при доставке грузов.
Задача оптимального распределения трудовых ресурсов – оптимизационная задача распределения трудовых ресурсов при выбранном критерии оптимальности.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.