Def.Оптимизационной моделью (моделью оптимального синтеза) называется модель синтеза, в которой одним из обязательных свойств синтезируемого объекта является оптимальность в смысле некоторого критерия его структуры либо значений параметров.
В общем случае задачу оптимального параметрического синтеза можно представить в виде
, (3.7)
где q – критерий задачи (целевая функция); – n-мерный вектор контролируемых входных параметров; D Í En – область допустимых решений задачи (ОДР). (Значок вектора в дальнейшем будем употреблять лишь в тех случаях, когда это необходимо чтобы избежать недоразумений.) Часто ОДР задается в виде системы неравенств
D = {xÎEn | "j fj(x) £ 0}.
В этом случае говорят, что поставлена задача математического программирования. Термин “программирование” в данном случае имеет свой устаревший смысл, означающий планирование некоторых действий.
. Задачей безусловной оптимизации называется задача (3.7), в которой на значения контролируемых входных переменных хj не наложено ограничений: D = En; при D Ì En (строгое включение) имеем задачу условной оптимизации.
В задаче линейного программирования (ЛП) функция критерия q(x) и ограничений fi(x) линейны; если хотя бы одна из этих функций нелинейна, то имеем задачу нелинейного программирования (НЛП).
Рассмотрим примеры прикладных задач, сводящихся к задаче линейного программирования.
Пример 3.3.Предприятие выпускает стулья двух типов. Один стул 1-го типа приносит $8 прибыли, в 2-го – $12. Под этот заказ выделены материальные и людские ресурсы. Количество единиц ресурсов, необходимое для выпуска каждого вида стульев приведено в табл. 3.2.
Как спланировать производство для получения максимальной прибыли?
Таблица 3.2
Расход досок (м2)
Расход ткани (м2)
Расход времени (чел/час)
Стул 1 типа
0,5
Стул 2 типа
0,25
2,5
Ресурс
Решение. Составим модель описания.
Шаг 1. Определим параметры, оптимальные значения которых требуется найти в задаче. В данном случае надо найти оптимальное количество стульев каждого типа. Обозначим x1 – выпуск стульев первого типа и x2 – выпуск стульев второго типа.
Шаг 2. Запишем формулы для вычисления целевой функции и функций ограничений через значения параметров хj.
Критерием эффективности является размер полученной прибыли. Используем следующий ход рассуждений, типичный для синтеза моделей ЛП. За один стул 1-го типа получим $8 прибыли. Следовательно, за х1 шт. получим 8×х1. Аналогично, за х2 стульев 2-го типа получим прибыль в размере 12×х2. Общая прибыль от выпуска продукции составит
q = 8×x1+12×x2 ® max.
При составлении ограничений используются те же рассуждения. Затраты досок составят 2х1 + 4х2 м2. Так как нельзя тратить сырья больше, чем есть в наличии, то получаем неравенство: 2х1 + 4х2 £ 490. Аналогично получаем ограничение на расход ткани: 0.5х1 + 0.25х2 £ 65 и времени 2х1 + 2.5х2 £ 319.
Кроме того, по физическому смыслу параметров хj, должны выполняться неравенства х1 ³ 0; х2 ³ 0, т.к. нельзя выпускать отрицательное количество стульев.
Итак, получаем задачу ЛП: найти максимум q = 8х1 + 12х2 при ограничениях
.
Пример 3.4.Завод выпускает детали А и Б. Цех №1 может изготовить за смену 600 деталей А или 1200 деталей Б. Эти детали затем поступают в цех №2, где за 1 час могут обработать 150 деталей А или 100 деталей Б. Сколько деталей А и Б может выпускать завод за 8-ми часовую смену, чтобы их общее количество было максимально.
Решение.Обозначим х1 и х2 – выпуск деталей А и Б за смену. Если за смену изготовить 600 деталей А, то на одну деталь тратиться 1/600 часть смены; на х1 деталь – надо х1/600 частей смены. Аналогично на х2 деталей Б надо х2/1200 частей смены. Получаем:
Аналогично, в цехе №2 на обработку деталей А надо х1/150 часа, на детали Б – надо х2/100 часа.
Целевая функция: q = x1 + x2® max.
Пример 3.5. Имеется m = 2 пункта производства А1, А2, и n = 3 пункта потребления В1, В2, В3 некоторого продукта. Перевозка из пунктов производства в пункты потребления 1 ед. продукции обходится в некоторую сумму, указанную в тарифной матрице.
Тарифная матрица
В1
В2
В3
Количество производимого продукта
А1
А2
Количество потребляемого продукта
Известно количество производимого продукта в каждом пункте производства и количество потребляемого в пункте потребления.
Составить план перевозок, при котором затраты минимальны.
Решение. Данная задача называется транспортной задачей. Нам надо определить, какое количество продукта надо перевозить из каждого пункта производства в каждый пункт потребления.
1. Обозначаем Х1 – количество продукта, перевозимого из А1 в В1;
Х2 – из А1в В2;
Х3 – из А1 в В3;
Х4 – из А2 в В1;
Х5 – из А2 в В2;
Х6 – из А2 в В3.
Для запоминания закономерности приведем схему нумерации Хj:
В1
В2
В3
A1
X1
X2
X3
A2
X4
X5
X6
2. Общие затраты на перевозку будут равны
q = 10x1 + 5x2 + 6x3 + 7x4 + 8x5 +12x6 → min
3.1 Ограничения на вывоз: из каждого пункта производства нельзя вывезти больше, чем там производят. Из А1 надо вывезти в В1 – х1 ед., в В2 – х2 ед., в В3 – х3 ед. Следовательно, х1+ х2 +х3 ≤ 50. Аналогично для А2: х4+ х5 +х6 ≤ 40.
3.2 Ограничения на привоз: в каждый пункт потребления нельзя привозить меньше, чем там потребляют.
В1: х1+х4 ≥ 30
В2: х2+х5 ≥ 30
В3: х3+х6 ≥ 25
Запишем общую систему ограничений, оставляя пустые места для нулевых элементов:
х1 + х2 + х3 ≤ 50
х4 + х5 + х6 ≤ 40
х1+ х4 ≥ 30
х2 + х5 ≥ 30
х3 + х6 ≥ 25
q = 10x1 + 5x2 + 6x3 + 7x4 + 8x5 +12x6 → min
Замечание. Типичная ошибка: при составлении модели коэффициенты целевой функции матрицы (тариф на перевозку 10, 5 и т. д.) заносят в ограничения. Следует помнить, в ограничениях на ввоз вывоз коэффициенты могут быть равны только 1 или 0, а тарифные коэффициенты встречаются только в целевой функции.
, (3.7)
– n-мерный вектор контролируемых входных параметров; D Í En – область допустимых решений задачи (ОДР). (Значок вектора в дальнейшем будем употреблять лишь в тех случаях, когда это необходимо чтобы избежать недоразумений.) Часто ОДР задается в виде системы неравенств
.
