Материал: 1263
решении задачи на компьютере. Построение модели это творческий процесс, требующий глубоких знаний и немалых способностей. Алгоритмы задач поиска оптимального решения достаточно сложны. Изложение методов решения (например, симплекс-метода) нам не понадобится, так как компьютер с помощью программного обеспечения MS Excel позволяет реализовать алгоритм поиска оптимального решения. Наша задача научиться строить математическую модель и пользоваться этим алгоритмом.
5.1. Общий случай задачи оптимизации
Процесс построения модели нужно начинать с ответа на следующие четыре вопроса:
1.Для каких величин строится модель, то есть каковы
переменные модели xj? Здесь j текущее значение переменных, общее количество которых равно n.
2.В чем состоит цель, для достижения которой из множества всех допустимых значений выбираются оптимальные? То есть надо
знать функцию цели (ЦФ целевая функция) или критерий
оптимизации
F= f(хj).
Критерий оптимизации (ЦФ) показывает, в каком смысле решение должно быть оптимальным. При этом возможны три вида назначения целевой функции:
максимизация;
минимизация;
назначение заданного значения.
3.Каким ограничениям должны удовлетворять неизвестные (ОГР)? Ограничения устанавливают зависимости между переменными. Они могут быть как односторонними
qi(xj) bi,
так и двусторонними
ai qi(xj) bi,
здесь i текущее значение зависимостей, общее количество которых равно m.
40
4. Каковы граничные условия для искомых величин (ГРУ)? То есть в каких пределах могут быть значения искомых переменных?
dj xj Dj.
Таким образом, общая форма записи задачи оптимизации в
математическом виде выглядит так:
F f (xj ) max(min,сonst)
qi(xj ) bi
dj xj Dj
ЦФ
ОГР
(10)
ГРУ
i 1 m; |
j 1 n. |
Решение задачи, удовлетворяющее всем ограничениям и граничным условиям, называется допустимым.
Соотношение числа переменных n и числа ограничений m является определяющим при постановке задачи оптимизации. Возможны три соотношения:
x1 2 5;
а) n < m, например,
x1 8 15,
здесь n=1; m=2. Очевидно, что такие задачи решения не имеют;
x1 х2 5;
б) n = m, например,
x1 х2 1,
здесь n=2; m=2. Это необходимое условие для решения системы (в том случае, если уравнения системы независимы);
в) n > m, например, x1 + x2 = 5,
здесь n=2; m=1. В этом случае может быть бесконечное множество решений.
Часто ограничения записываются в виде неравенств, например,
х1 5.
Если ввести дополнительную переменную х2 0, то от неравенства перейдем к уравнению x1 + x2 = 5. Следовательно, если ограничениями являются неравенства, то система имеет бесконечное множество решений. Таким образом, условие n > m является необходимым для задач оптимизации. Важно, чтобы было из чего выбирать. Это значит, что из всех допустимых решений нужно выбрать оптимальное, а для достаточности решения нужен критерий
41
(целевая функция), по которому выбирается одно из допустимых решений.
5.2. Классификация математических моделей
Научный подход к любой проблеме это систематизация. Систематизация это классификация по ряду признаков.
Исходными данными для математической модели являются: целевая функция F(xj), левые q(xj) и правые bi части ограничений. Если значения исходных данных точно известны, то такие данные называются детерминированными. Если их значения заранее не определены, то эти данные являются случайными величинами.
Искомые переменные могут быть непрерывными и дискретными. Непрерывными называются такие величины, которые в заданных граничных условиях могут принимать любые значения. Дискретные принимают только заданные значения. Целочисленными называются такие дискретные переменные, которые могут принимать только целые значения.
Зависимости между переменными, как в целевой функции, так и в ограничениях, могут быть линейными и нелинейными. Линейными называются зависимости, в которых переменные входят в первой степени и с ними выполняются только действия сложения, вычитания и умножения на постоянный множитель. В противном случае зависимости являются нелинейными. При этом следует иметь в виду, что если в задаче хотя бы одна зависимость нелинейная, то и вся задача является нелинейной.
Сочетание различных элементов модели образуют различные классы задач оптимизации, которые требуют различных методов решения (табл. 3).
|
|
|
Таблица 3. |
|
|
Классификация задач оптимизации. |
|||
|
|
|
|
|
Исходные |
Искомые |
Зависимости |
Классы |
|
данные |
переменные |
|
задач |
|
Детерминированные |
Непрерывные |
Линейные |
Линейное |
|
|
|
|
программирование |
|
Детерминированные |
Целочисленные |
Линейные |
Целочисленное |
|
|
|
|
программирование |
|
Детерминированные |
Непрерывные и |
Нелинейные |
Нелинейное |
|
|
целочисленные |
|
программирование |
|
|
|
|
|
|
Случайные |
Непрерывные |
Линейные |
Стохастическое |
|
|
|
|
программирование |
|
42
5.3. Задача распределения ресурсов
Если финансы, оборудование, сырье и даже людей полагать ресурсами, то значительную часть задач в экономике можно рассматривать как задачи распределения ресурсов. Как правило, это задачи линейного программирования.
Пример.
Пусть требуется определить, в каком количестве надо выпускать продукцию четырех типов, для изготовления которых требуются ресурсы трех видов (трудовые, сырье и финансы) с целью получения максимальной прибыли.
Первоначально для построения математической модели сформируем табл. 4, в которую будут входить: нормы расхода1; наличие располагаемого ресурса и прибыль в денежных единицах, полученная от реализации данного вида продукции.
|
Распределение ресурсов по продуктам |
|
Таблица 4 |
|||||
|
|
|
|
|||||
Ресурс |
Прод1 |
Прод2 |
Прод3 |
Прод4 |
|
Знак |
|
Наличие |
Трудовые |
1 |
1 |
1 |
1 |
|
<= |
|
16 |
Сырье |
5 |
6 |
4 |
3 |
|
<= |
|
110 |
Финансы |
4 |
6 |
10 |
13 |
|
<= |
|
100 |
Прибыль |
60 |
70 |
120 |
130 |
|
max |
|
|
Составим математическую модель, для чего введем следующие обозначения:
xj количество выпускаемой продукции j-го типа, j=1 4; bi количество располагаемого ресурса i-го вида, i=1 3;
aij норма расхода i го ресурса для выпуска единицы продукции j-го типа;
сj прибыль, получаемая от реализации единицы продукции j-го
типа.
Как видно из табл. 4, для выпуска единицы Прод1 требуется 5 единиц сырья, значит, для выпуска всей продукции Прод1 требуется 5x1 единиц сырья. С учетом того, что для других видов продукции зависимости аналогичны, ограничение по сырью будет иметь вид
5x1 + 6x2 + 4x3 + 3x4 110.
1 Количество ресурса каждого вида, необходимого для выпуска единицы продукции каждого типа, называется нормой расхода.
43
В этом ограничении левая часть равна величине потребного ресурса, а правая показывает количество имеющегося ресурса.
Аналогично можно составить ограничения для остальных ресурсов и написать зависимость для целевой функции. Тогда математическая модель задачи будет иметь вид
ЦФ |
F = 60x1 + 70x2 |
+ 120x3 + 130x4 max; |
|
||
|
x1 + x2 + x3 + x4 |
16; |
|
||
ОГР |
5x1 + 6x2 |
+ |
4x3 + 3x4 110; |
(11) |
|
|
4x1 + 6x2 |
+ |
10x3 + 13x4 100; |
|
|
ГРУ |
xj 0; j |
= 1 4. |
|
||
Алгоритм ввода данных и решения задачи линейного программирования в Excel.
Ввести тексты (рис. 30).
Рис. 30. Текстовое оформление задачи в Excel
Весь текст на рис. 30 является комментарием и на решение задачи не влияет.
Вести в таблицу Excel зависимости из математической модели
(11) (рис. 31).
Рис. 31. Пример ввода математической модели оптимизации
44