Формальная постановка задачи оптимизации

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

Почти формальная запись задачи оптимизации имеет вид:

                                             (1)

где  – вектор искомых переменных ;

 – целевая функция;

exstremum – абстрактный идентификатор, заменяемый в конкретных задачах идентификатором  или ;

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

Представив  в виде системы, можно получить следующую формальную запись задачи оптимизации:

                                             (2)

где ,  – символы операций отношения, т. е. элементы множества ;

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

А теперь вспоминаем следующее: фактически и целевая функция, и вспомогательные функции являются функциями не только искомых переменных, но и констант задачи, т. е. правильнее было бы вместо , , писать так: , , где  – вектор констант задачи. К сожалению, так писать не принято: из-за стремления к компактности записи формул и желания «сосредоточить внимание на главном», кроме того, константы, вообще не принято называть аргументами, их называют параметрами, и в обозначение функции обычно не включают. Итак, запоминаем: и целевая функция, и вспомогательные функции в общем случае имеют неотображаемые в обозначениях этих функций параметры – константы задачи.

Формула (2) более точна по сравнению с нечёткой формулой (1), но одновременно и менее наглядна. Повысить наглядность формальной записи задачи оптимизации без сокращения её содержательности можно, если учесть следующие факты:

1) задачи вида  и  могут быть сведены к задаче  путём незначительной модификации выражения целевой функции; действительно,  эквивалентно , а  эквивалентно ;

2) отношение  любого вида может быть сведено к виду  следующим путём:

·  правая часть отношения переносится влево для получения нуля в правой части и одного выражения  в левой;

· строгое неравенство можно преобразовать в нестрогое с помощью малой положительной константы , – значение которой пренебрежимо мало в рамках рассматриваемой предметной области:  вычислительно эквивалентно

· равенство  заменяется парой нестрогих неравенств ; .

Учёт перечисленных фактов позволяет получить типичную запись формальной постановки задачи оптимизации в учебнике:

                                                       (3)

А иногда записывают и вовсе просто:

                                             (4)

Ну, теперь корректная формальная запись задачи (4) ничуть не сложнее упрощенной записи (1).

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

И, наконец, главное: всё, что вы прочитали в этом пункте – чистой воды гимнастика для ума, практически полезного здесь ничего нет; в реальной практике задачу оптимизации следует формулировать в наиболее подходящем для восприятия виде, а это тот вид, который наиболее просто и естественно отражает конкретику предметной области, формально ему соответствует «несуразная» формула (2). Так зачем же я этот пункт написал? Ну, во-первых, ум тренировать полезно: умные люди живут дольше (в среднем), а во-вторых, надо быть готовым к чтению учебников.

Задания к контрольной работе

2.1 Формулировка задания

А, вот оно и задание. Очень простое, хотя «с непривычки» может показаться и сложным. Но трудности ограничиваются только освоением инструмента Excel, называемого поиском решения.

Решить три задачи оптимизации по следующим темам.

1 Планирование производства

2 Транспортная задача

3 Планирование персонала

Для этого предварительно знакомиться с образцами решения, представленными в файле Smpls.xls, затем составить и решить собственные варианты указанных задач.

2.2 Собственный вариант задачи «Планирование производства»

О таком можно только мечтать: сами себе выбираем что будем делать. Как в супермаркете: хотим берём, не хотим не берём.

Собственный вариант задачи «Планирование производства» создаётся на основе варианта образца путём следующих изменений:

1) изменения значений констант;

2) изменения состава комплектующих деталей и производимых изделий;

3) изменение целевой функции – вместо дохода можно использовать получаемую прибыль; для этого предусмотреть дополнительный столбец констант со значениями цен комплектующих деталей.

Количество изменений выбирается самостоятельно. Степень отличия от образца будет влиять на выставляемую оценку.

2.3 Собственный вариант «Транспортной задачи»

В этой задаче возможных изменений не много, они просты в реализации, но заметно отличают предлагаемый вариант от образца.

Собственный вариант «Транспортной задачи» создаётся из варианта образца путём следующих возможных изменений:

1) изменения значений констант;

2) изменения состава заводов-производителей;

3) изменения состава складов-получателей.

Количество изменений выбирается самостоятельно. Степень отличия от образца будет влиять на выставляемую оценку.

2.4 Собственный вариант задачи «Планирование персонала»

Эта задача очень проста. Для неё трудно придумать возможные направления «удаления» от образца. Изменение целевой функции кажется сложным, но требует только знания стандартной функции МАКС().

Собственный вариант задачи «Планирование персонала» создаётся из варианта образца путём следующих возможных изменений:

1) изменения значений констант;

2) изменение целевой функции – вместо «Общая недельная зарплата» использовать «Максимальное количество лишних работников».

Количество изменений выбирается самостоятельно. Степень отличия от образца будет влиять на выставляемую оценку.