Окончательная формулировка задачи (формальная постановка задачи)

Практическое занятие № 5.

Проектирование математического обеспечения.

Постановка задачи

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

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

Все параметры, от которых зависит решение оптимизационной задачи, делятся на две группы:

- заданные заранее известные неизменяемые параметры: a=(α₁, α₂..);

- изменяемые параметры x=(х₁, х₂,…) значения которых необходимо определить при решении задачи.

Оптимальным называют решение, которое предпочтительнее других. Чтобы судить об эффективности решения, определяются численный критерий c=(c₁, c₂, …)и количественные связи между параметрами и критериями, т.е. целевая функция (c= W(x,a)).Целевую функцию требуют обратить в максимум или минимум («чем больше, тем лучше» или «чем меньше, тем лучше»).

Задача оптимизации формулируется следующим образом:

При заданных значениях α₁, α₂, …найти значения параметров х₁, х₂, …, из области допустимых значений которые обращают целевую функцию W в максимум (минимум). При постановке оптимизационной задачи выполняются поэтапно следующие действия:

- постановка задачи;

- выбор или разработка метода решения задачи;

- решение задачи на контрольном примере.

Постановка задачи

Постановка задачи предполагает определение следующих компонентов:

1. Набор переменных, нахождение наилучших значений которых подлежит определению при решении задачи.

2. Ограничения задачи, которые связывают значения набора переменных и определяют область допустимых значений.

3. Критерии решения, определяющие оценку качества решения задачи.

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

Постановка задачи выполняется поэтапно:

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

- список обозначений переменных;

- формирование ограничений (условий) в форме равенств или неравенств;

- запись целевой функции;

- окончательная формулировка задачи.

Рассмотрим пример постановки задачи о выборе рациона питания.

Вербальное описание (неформальная постановка задачи)

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

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

Список обозначений приведен в таблице 1.

Таблица 1. Список обозначений

Формирование ограничений.

Зададим область допустимых значений в форме неравенств:

1. Количество продуктов x_i, (i=1,4) в рационе не может быть отрицательным числом:

x_i ≥ 0, i = 1,2,3,4 (1).

2. Запишем условие: «Белков в рационе должно быть не менее b₁ единиц» в форме неравенства. В одной единице первого продукта содержится а₁₁ единиц белка, поэтому в х₁ единицах содержится а₁₁х₁ единиц белка; соответственно в х₂ единицах продукта второго продукта содержится а₂₁х₂ единиц белка, и т. д. Количество белков, содержащиеся в рационе, не должно быть меньше b_1. Следовательно, справедливо неравенство:

а₁₁х₁+а₂₁х₂+а₃₁х₃+а₄₁х₄≥b₁; (2)

3. Углеводов в рационе должно быть не менее b₂ единиц:

а₁₂х₁+а₂₂х₂+а₃₂х₃+а₄₂х₄≥b₂ (3)_.

4. Жиров в рационе должно быть не менее b₃ единиц:

а₁₃х₁+а₂₃х₃+а₃₃х₃+а₄₃х₄≥b₃ (4)_.

Целевая функция.

Критерием выбора рациона является его стоимость. Значение целевой функции, значение которой равно стоимости рациона, определяется выражением:

С=c₁x₁+c₂x₂+c₃x₃+c₄x₄

или

(5).

Окончательная формулировка задачи (формальная постановка задачи)

Необходимо найти такие неотрицательные значения переменных х₁, х₂, х₃, х₄, удовлетворяющие линейным неравенствам (1-4), при которых линейная функция от этих переменных (5) обращалась в минимум.

Таким образом, формальная постановка задачи имеет вид:

а₁₁х₁+а₂₁х₂+а₃₁х₃+а₄₁х₄≥b₁;

а₁₂х₁+а₂₂х₂+а₃₂х₃+а₄₂х₄≥b₂;

а₁₃х₁+а₂₃х₃+а₃₃х₃+а₄₃х₄≥b₃;

x_i ≥ 0, i = 1, 2, 3, 4;

С=c₁x₁+c₂x₂+c₃x₃+c₄x₄ ® min.

Приложение 1.

Множество значений переменных могут удовлетворять следующим свойствами:

· непрерывность (н), дискретность (д), целочисленность (ц);

· отрицательность (о), неотрицательность (н);

· бесконечность (б), конечность (к) ;

· бинарность (B), не бинарность (N).

Варианты множеств значений переменных представлены в табл. 3.2.:

Таблица.2

Задания практического занятия № 5.

Ввести обозначения.

Не нашли, что искали? Воспользуйтесь поиском по сайту: