«УДК 669:519.216 ББК 34.3-02 М74 Электронный учебно-методический комплекс по дисциплине Моделирование процессов и объектов в металлургии подготовлен в рамках инновационной образовательной программы Многоуровневая ...»

Коэффициент корреляции r характеризует степень тесноты линейной связи между Y и Y, приближенное значение r определяется по формуле где n – число экспериментальных данных. Коэффициент корреляции изменяется от –1 до +1.

Корреляционное отношение характеризует степень тесноты нелинейной связи между переменными Y и Y:

где Y i – текущее значение, вычисленное по математической модели значение параметра Y; Yi – текущее значение, полученное на объекте; Y – выборочное среднее значение, Корреляционное отношение изменяется от 0 до +1.

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

Выводы о степени адекватности модели делаются не только на основании значения коэффициента корреляции или корреляционного отношения, но и на основании гистограммы распределения и содержательного анализа остатков модели.

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

Содержательный анализ остатков модели состоит в построении распределения остатков модели в зависимости от входного параметра X.

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

1. Для оформления решения составить таблицу в ППП Microsoft Office Excel (рис. 1.2) и, исходя из задания, занести экспериментальные данные в ячейки A3:B12.

2. Построить точечный график по диапазону ячеек A3:B12, выделить точки графика щелчком левой кнопки мыши в диапазоне точек на графике, а затем щелкнуть на них правой кнопкой.

В раскрывшемся контекстном меню следует выбрать команду Добавить линию тренда (рис. 1.3).

В диалоговом окне Линия тренда (Trendline) (рис. 1.4) на вкладке Тип (Type) в группе Построение линии тренда (аппроксимация и сглаживание) (Trend/Regression type) выбрать параметр Линейная (Linear).

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

Например, если этот флажок установлен и в его поле введен 0, это означает, что ищется модель y = b1 X.

Результат выполнения команды Линия тренда представлен на (рис. 1.6).

3. По приведенному выше алгоритму выполнить регрессионный анализ для нелинейных моделей, в частности построить полиномиальную модель второго порядка, последовательно увеличить порядок уравнения до шестого. Для этого выделить линию тренда с помощью щелчка левой кнопки и вызвать контекстное меню с помощью правой кнопки мыши. Выбрать опцию Формат линии тренда, далее выбрать соответствующий параметр Полиномиальная модель, увеличить показатель степени, найти уравнение и коэффициент корреляции.

4. Проанализировать полученные данные и по наиболее высокому значению коэффициента корреляции определиться с типом модели, адекватным объекту (рис. 1.7).

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

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

6. Вычислить ошибку модели в ячейке D3 по формуле =B3-C3 и скопировать на весь столбец D (рис. 1.8).

7. Для проверки модели на адекватность построить гистограмму распределения ее остатков. Это сделать следующим образом. Составить диапазон изменения остатков, определить их минимальное и максимальное значения с помощью функций МАКС() и МИН(). Затем весь диапазон изменения остатков разбить на несколько равных поддиапазонов (от 6 до 20) и рассчитать число попаданий ошибки (остатков) в каждый поддиапазон.

Все границы интервалов записать в отдельную строку или столбец (рис. 1.9).

Далее для построения гистограммы распределения остатков выбрать команду Сервис, Анализ данных (если этой опции не будет, необходимо выбрать команду Надстройки... и в появившемся диалоговом окне отметить флажком опцию Пакет анализа). В появившемся диалоговом окне Анализ данных в разделе Инструменты анализа выбрать опцию Гистограмма.

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

Результаты построения приведены на рис. 1.11.

Рис. 1.10. Построение гистограммы распределения остатков модели 8. Для проверки модели на адекватность построить график содержательного анализа остатков модели в зависимости от входной переменной Х.

Построить точечный график по диапазону ячеек в столбцах A3:A12 и D3:D12. По полученным результатам сделать выводы об адекватности построения модели экспериментальным данным и оформить отчет.

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

Для кремнистых бронз определить зависимость указанного параметра от содержания кремния (табл. 1.3).

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

ЛАБ. Р. 1. ОПР-Е ПАРАМЕТРОВ РЕГРЕСС. МОДЕЛИ ПО ЭКСПЕРИМЕНТ-М ДАННЫМ МЕТОДОМ НАИМЕНЬШИХ КВАДРАТОВ

2. В чем заключается задача регрессионного анализа?

3. Какую величину называют случайной? Опишите основные типы случайных величин.

4. Сформулируйте закон распределения случайной величины.

5. Назовите виды регрессионных зависимостей.

6. Какая характеристика служит для оценки качества линейной модели? Какие она может принимать значения?

7. Описать сущность МНК.

8. Какая характеристика служит для оценки качества нелинейной модели? Какие она может принимать значения?

9. Дайте определение корреляции. Какие виды корреляции вы знаете?

10. Можно ли считать, что математическая модель и линия регрессии одно и то же? Как строится линия регрессии?

11. Опишите метод построения гистограммы.

12. В чем заключается содержательный анализ остатков модели?

13. В каких случаях используется корреляционный коэффициент, а в каких – корреляционное отношение как критерий адекватности модели?

14. Назовите этапы построения и исследования регрессионной модели.

15. Каковы методы проверки адекватности структуры модели?

ЛАБОРАТОРНАЯ РАБОТА

МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Решение всякой задачи оптимизации начинается с ее математической постановки.

Постановка задачи безусловной оптимизации Общая постановка задачи состоит в следующем.

Задано: множество X и функция f(x), определённая на Х.

Требуется: найти точки минимума или максимума функции f на X.

Будем записывать задачу на минимум в виде Задача (2.1) сформулирована как задача нахождения минимума функции f(x), или минимизации f(x). На практике же приходится сталкиваться как с задачами минимизации, так и с задачами максимизации f(x), т.е. нахождения точек максимума f(x):

С математической точки зрения различия между задачами минимизации и максимизации не существенны, поскольку максимизация f(x) эквивалентна минимизации функции f(x). Поэтому всегда можно ставить задачу оптимизации как задачу минимизации (2.1).

Функция f(x) в выражении (2.1), т.е. функция, которую мы минимизируем, называется целевой. Множество Х в формуле (2.1), на котором мы минимизируем f(x), называется допустимым множеством задачи, а любой элемент х Х допустимой точкой задачи. Допустимая точка х*Х, в которой

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Следует иметь в виду, что на практике допустимая точка х может представлять собой некоторый набор параметров х = (х1,..., хn). Причём значения этих параметров могут подчиняться ограничениям или изменяться без ограничений. Если, например, хi выражает количество производимого продукта i-го вида (сплав соответствующей марки и пр.) для каждого i = 1,..., n, то при этом будет существовать ограничение на производственную мощность (например, 0 хi аi, i = 1,..., n) и ограничение на количество товара, которое может поглотить рынок (например, 1х1 + 2х2 + … + nхn b, где i – рыночная цена i-го товара; b – общая денежная масса).

Необходимо подчеркнуть, что само понятие точки минимума (решения задачи (2.1)) неоднозначно и требует уточнения.

Точка х* Х называется точкой глобального минимума функции f(x) на множестве Х или глобальным решением задачи (2.1), если Точка х* Х называется точкой локального минимума f на Х или локальным решением задачи (2.1), если существует такое подмножество U (х*) = {xx X, || x x*|| }, что Очевидно, что глобальное решение является и локальным, обратное неверно.

Для отражения того факта, что точка x* X является точкой глобального минимума функции f на X, будем использовать запись Если неравенство в (2.2) или (2.3) выполняется как строгое при x x*, т.е. f(x) < f(x*), x X (или x U(x*)), то говорят, что x* – точка строгого минимума (строгое решение).

При изучении задач оптимизации в первую очередь возникает вопрос о существовании решения. Условия, гарантирующие разрешимость задачи (2.1), содержатся в следующей теореме из курса высшей математики [1, 2, 4].

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Эта теорема отвечает на вопрос о существовании решения, но не даёт конструктивного алгоритма нахождения этого решения. Следует также учесть, что задача оптимизации может иметь несколько решений. Вопрос о единственности решения рассматривается отдельно для каждого класса задач (классификацию задач оптимизации можно найти, например, в учебной литературе [1, 2]).

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

Постановка задачи безусловной оптимизации Если допустимое множество Х = Rn, то задача (2.1) называется задачей безусловной оптимизации. Приведем ее математическую постановку.

Задано: функция f(х), определенная на Rn.

Требуется: найти точки минимума функции f на Rn. Иначе говоря, Теория необходимых и достаточных условий оптимальности в задачах безусловной оптимизации излагается в любом курсе высшей математики [2, 3].

Необходимое условие оптимальности. Пусть функция f дифференцируема в точке х*Rn. Если х* – локальное решение задачи (2.4), то все первые производные функции f в точке х* равны нулю:

Достаточное условие безусловного локального минимума связано со вторыми производными функции f. При n = 2 наличие экстремума в точке х* зависит от знака определителя

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Для функции f числового аргумента (n = 1) достаточные условия экстремума означают, что если f (x*) = 0 и f (x*) > 0, то x* решение задачи (2.4).

Методы одномерной безусловной минимизации Изучение методов безусловной оптимизации начинается с наиболее простого типа оптимизационных задач, в которых целевая функция зависит от одной переменной.

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

Рассмотрим методы одномерной минимизации так называемых унимодальных функций.

Функция f называется унимодальной на Х, если существует такая точка х*Х, что для любых x1, x2 X Для непрерывных функций свойство унимодальности означает наличие у неё единственного локального минимума. Предположение об унимо-

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Если известен какой-либо отрезок [хk, хm], которому принадлежит х*, будем говорить, что точка минимума х* локализована в отрезке [хk, хm]. Сам отрезок при этом будем называть отрезком локализации минимума. В литературе интервал (хk, хm) называется интервалом неопределённости.

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

Т е о р е м а 2. Пусть функция f унимодальна на Х и х1 < x2. Тогда, если f(x1) f(x2), то х* х2, если же f(x1) f(x2), то х* х1, а если f(x1) = f(x2), то х* [х1, х2].

Работа любого алгоритма минимизации состоит из двух этапов. На первом этапе вычисляются предусмотренные алгоритмом характеристики задачи. На втором этапе по полученной информации строится приближение к решению. Обычно для задания алгоритма достаточно указать способ выбора точек приближения xk = (х1k, …, хnk), k =1, 2, … Выбор точек приближения называется поиском точек.

Если все точки выбираются одновременно до начала вычислений, то алгоритм минимизации называется пассивным. Однако для решения большинства задач точки приближения выбираются поочередно, т.е. точка х(k+1) выбирается тогда, когда уже выбраны точки предыдущих вычислений х(1), х(2), …, х(k) и в каждой из них произведены предусмотренные алгоритмом вычисления. Такие алгоритмы называются последовательными.

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

Пусть количество допустимых вычислений функции N = 2k. Приa +b a +b < (a + b)/2k. Вычислим f(x1) и f(x2) и определим новый отрезок локализации минимума. Согласно теореме 2, если f(x1) < f(x2), то х* [а, х2]; если f(x1) > f(x2), то х* [x1, b]; если f(x1) = f(x2), то х* [x1, x2]. В превом случае искомым отрезком будет [a, x2], во втором [x1, b], в третьем [x1, x2].

Для единообразия в случае f(x1) = f(x2) будем рассматривать в качестве нового отрезка локализации минимума, например, [a, x2]. Так что длина отba резка локализации после первой пары вычислений функции равна Вторая пара значений f вычисляется в точках х3, х4, отстоящих на расстоянии по обе стороны от середины нового отрезка локализации. Если, например, этим отрезком оказался [a, x2], то

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Сравнительный анализ указанных выше методов и обзор других методов одномерной минимизации можно найти в учебном пособии [1].

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

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

Говорят, что вектор h = (h1, h2,..., hn) задает направление убывания функции f в точке x, если существует такое число 0 > 0, что при всех 0 < < 0. Сам вектор h также называют направлением убывания.

Заменив неравенство, фигурирующее в (2.5), на противоположное, получим определение направления возрастания.

Общая идея методов спуска состоит в следующем. Для определения точки x* локального минимума функции f(x) строится последовательность

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Для различных методов спуска сначала выбирают начальную точку последовательности х(0). Дальнейшие приближения x(k) определяются соотношениями где h(k) – вектор направления убывания; k – положительная скалярная величина, называемая длиной шага.

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

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

Решение задачи (2.4) методом покоординатного спуска осуществляется по следующей общей схеме.

Выбирают произвольно начальную точку х(0) из области определения функции f(х). Приближения х(k) определяются соотношениями (2.6), где вектор направления убывания h(k) – это единичный вектор, коллинеарный какому-либо из координатных направлений; величина k является решением задачи одномерной минимизации Решение этой задачи может быть найдено, в частности, каким-либо из методов одномерной минимизации.

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

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

Далее везде будем считать, что f(x) и f(x) существуют и непрерывны, а компоненты градиента могут быть записаны в аналитическом виде или с достаточно высокой точностью найдены с помощью численных методов.

Все градиентные методы основаны на итерационной процедуре, реализуемой в соответствии с формулой (2.6), где вектор h(k) строится с помощью антиградиента функции f в точке x(k), т.е. вектора f(x(k)), задающего направление наискорейшего убывания целевой функции f. Способ определения h(k) и k на каждой итерации характеризует особенности применяемого метода. Например, поиск методом наискорейшего спуска (методом Коши) сводится к построению последовательности приближений {xk} по формуле (2.6), где ||f(x(k))|| – длина вектора градиента f(х(k)). Длина шага k вычисляется путем решения задачи одномерной минимизации с помощью какого-нибудь из методов одномерной минимизации. Условием окончания вычислительной процедуры является выполнение неравенства (2.7).

Метод наискорейшего спуска сходится быстрее, чем методы прямого поиска. Однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку cкорость изменения переменных непосредственно зависит от длины вектора градиента ||f(x(k))||, которая стремится к нулю, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из главных преимуществ этого метода связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага k на всех итерациях выполняется неравенство f (x(k+1)) f(x(k)).

Благодаря этому свойству метод наискорейшего спуска, как правило, позволяет существенно уменьшить значение целевой функции при движении из

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

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

Различают ненаправленный случайный поиск, направленный случайный поиск без самообучения и с самообучением.

Ненаправленный случайный поиск (или метод статистических испытаний, метод Монте-Карло) заключается в многократном моделировании независимых случайных вариантов решений из области допустимых, вычислении в каждом их них критерия оптимизации и запоминания наиближайшего к экстремуму. Метод Монтe-Карло относится к числу универсальных, поскольку позволяет решать многоэкстремальные задачи общего вида с отысканием глобальною экстремума. Основной недостаток метода – необходимость проведения большого числа испытаний для получения решения, достаточно близкого к оптимальному, т. е. наличие медленной сходимости к экстремуму.

Обзор других методов безусловной оптимизации можно найти в литературе [1, 2, 3, 4, 5].

1. Изучить основные понятия теории оптимизации, классификацию и основные численные методы для решения задач оптимизации.

2. В соответствии с индивидуальным заданием исследовать заданную целевую функцию на экстремумы.

3. Учитывая проведенное исследование, выполнить вычислительный эксперимент в пакете прикладных программ MATHCAD.

4. Сравнить полученные результаты.

5. Оформить отчет, в который включить: титульный лист; формулировку цели лабораторной работы; теоретическое описание используемого численного метода и его сравнение с другими методами; геометрическую интерпретацию метода; индивидуальное задание на работу; анализ полученных результатов.

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

2. Запустить пакет MATHCAD.

3. Ввести функцию в соответствии с вариантом задания.

4. Построить график и линии уровня функции, используя компонент Graph. Изменяя диапазоны значений переменных x, y, найти область, в которой линии уровня функции представляют собой замкнутые кривые, концентрически вложенные друг в друга (рис. 2.1).

6. Решить задачу безусловной оптимизации. Для этого задать начальные значения переменных в пределах найденной области и вычислить решение задачи с помощью встроенных функций Maximize или Minimize.

7. Проверить, удовлетворяет ли решение необходимым условиям оптимальности.

8. Распечатать результаты.

В пакете MATHCAD для решения задачи можно воспользоваться помощью: Help Solving and optimization Maximizing or minimizing a function.

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

ЛАБОРАТОРНАЯ РАБОТА 2. МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

2. Что такое глобальный, локальный оптимум ?

3. В чем заключается необходимое условие оптимальности в задаче безусловной оптимизации?

4. Сформулируйте достаточное условие оптимальности.

5. Какие численные методы используются для оптимизации унимодальных функций?

6. Опишите основную идею методов исключения интервалов.

7. В чем состоит суть метода Гаусса-Зейделя?

8. Как задается направление убывания в градиентных методах?

9. В чем заключается суть метода наискорейшего спуска?

10. Чем определяется выбор метода оптимизации?

ЛАБОРАТОРНАЯ РАБОТА

ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ ДЛЯ МОДЕЛИРОВАНИЯ

И РЕШЕНИЯ ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Методы линейного программирования (ЛП) оказались весьма эффективными для решения задач из различных областей человеческой деятельности. Слово «программирование» понимается как планирование, и это определяет характер рассматриваемых приложений. Основные идеи линейного программирования возникли во время Второй мировой войны в связи с поиском оптимальных стратегий при ведении военных операций. С тех пор они нашли широкое применение в промышленности, торговле и в управлении как в местных, так и в государственных масштабах. Этими методами можно решить многие задачи, связанные с эффективным использованием ограниченных ресурсов.

Пример двумерной задачи линейного программирования Фирма производит две модели (А и В) сборных книжных полок. Их производство ограничено наличием сырья (высококачественных досок) и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В – 4 м2. Фирма может получить от своих поставщиков до 1 700 м2 досок в неделю. Для каждого изделия модели А требуется 12 мин машинного времени, а для изделия модели В – 30 мин. В неделю можно использовать 160 ч машинного времени.

Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А приносит 2 дол. прибыли, а каждое изделие модели В – 4 дол. прибыли?

Чтобы сформулировать эту задачу математически, обозначим через x1 количество выпущенных за неделю полок модели A, а через x2 – количество выпущенных полок модели В. Задача состоит в том, чтобы найти наилучшие значения x1 и x2. Очевидно, наилучшими для данной задачи являются

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Поскольку x и x2 выражают еженедельный объем выпускаемых изделий, то они не могут быть отрицательны, т.е.

Теперь ограничения на наличие досок и машинное время могут быть записаны следующим образом:

для машинного времени – Следовательно, задача состоит в том, чтобы найти значения x1 и x2, удовлетворяющие условиям неотрицательности (3.1) и ограничениям типа неравенства (3.2), (3.3) и максимизирующие функцию Р.

Это типичная двумерная задача линейного программирования. Целевая функция, которая должна быть максимизирована, является линейной функцией своих переменных. Ограничения на эти переменные тоже линейны (рис. 3.1).

Условия неотрицательности позволяют ограничиться рассмотрением положительного квадранта. Границы определяются прямыми

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Штриховыми линиями изображены две линии уровня функции Р со значениями, соответственно, 0 и 800, обозначенные a и b. Ясно, что значение функции Р возрастает по мере того, как линии уровня удаляются от начала координат в положительном квадранте. Действительно, вектор градиента grad P =,, т.е. вектор с компонентами (2, 4), указывающий направx1 x ление возрастания функции Р, перпендикулярен линиям уровня и направлен в сторону, противоположную началу координат.

Линией уровня с наибольшим значением функции Р, имеющей хотя бы одну точку с допустимой областью, является прямая c, проходящая через вершину В; на ней Р принимает значение 1 400. Точка В, в которой x1 = 300, x2 = 200, соответствует оптимальному решению задачи. На данном примере показано, как возникают задачи линейного программирования на практике и как их можно решить, используя графический метод.

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

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

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

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

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

где A матрица ранга m, m < n; b вектор правых частей; x вектор переменных;

При приведении задачи к канонической форме используют следующие правила.

1. Максимизация целевой функции z равносильна минимизации целевой функции z.

2. Ограничение в виде неравенства преобразуется в равенство добавлением новой неотрицательной переменной к левой части неравенства. Новая переменная x5 неотрицательна.

3. Если переменная xk может принимать значения любого знака, то она заменяется разностью двух неотрицательных переменных: xk = x 'k x "k, Таким образом, приведение задачи к канонической форме может потребовать увеличения размерности задачи (количества переменных).

Основные свойства задач линейного программирования Допустимое множество Х общей ЗЛП образует так называемое многогранное множество. Каждое из равенств (3.4), (3.5) задает гиперплоскость в Rn, а каждое из неравенств определяет полупространство в Rn, ограниченное соответствующей гиперплоскостью. Если множество X непусто, то оно выпукло т.е. оно содержит отрезок прямой, соединяющей две его любые точки.

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Ограниченное многогранное множество называют многогранником.

Точка х0 выпуклого многогранного множества М называется его угловой точкой (базисным допустимым решением), если она не лежит ни на каком отрезке, соединяющем какие-либо две точки множества М, отличные от нее.

Угловые точки многогранника называются его вершинами.

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

Обозначая через A1, …, An столбцы матрицы А, т.е.

систему (3.7) можно записать в виде В дальнейшем без ограничения общности можно полагать, что число уравнений задающих множество Х меньше или равно числу переменных задачи (m n). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, значит, множество Х пусто), либо содержит избыточные (линейно зависимые) уравнения. Соотношение (3.9) является разложением вектора b по векторам Ai, i = 1, 2, …, n, а xi – коэффициентами этого разложения. Такое разложение получило название второй геометрической интерпретации ЗЛП.

Точка x(0) = (x1(0), …, xn(0)) называется опорной точкой допустимого множества Х (базисным решением), если существуют номера j1, …, jm, 1 jk n, такие, что система векторов A j1, …, A jm линейно независима и Система векторов { A j1, …, A jm} называется базисом опорной точки (х(0)), а переменные xj1, …, xjm – базисными переменными. Переменные, которые не входят в список базисных переменных, называются небазисными или свобод- ными.

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

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

У т в е р ж д е н и е 3.1. Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Геометрически это утверждение означает, что если допустимое множество X непусто, то у него существует хотя бы одна угловая точка.

Следующее утверждение называют основным свойством задач линейного программирования или основной теоремой линейного программирования.

У т в е р ж д е н и е 3.2. Если целевая функция достигает конечного минимума, то, по крайней мере, одно оптимальное решение является базисным. Другими словами, множество решений задачи линейного программирования содержит хотя бы одну угловую точку допустимого множества X.

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

Полный перебор базисных допустимых решений для реальных многомерных задач крайне не эффективен даже при условии использования мощной вычислительной техники, ибо при больших n и m он требует огромной вычислительной работы. Но он естественным образом подводит к основной идее симплекс-метода: полный перебор заменяется упорядоченным, при котором осуществляется переход от текущей опорной точки (базисного допустимого решения) только к тем опорным точкам, в которых значение целевой функции меньше, чем в текущей. Несмотря на то, что при таком переборе возврат к однажды просмотренным опорным точкам уже невозможен, теоретически не исключается (и такие примеры существуют), что в процессе решения будут пройдены все опорные точки допустимого множества Х. Однако большой практический опыт показал, что для подавляющего числа канонических ЗЛП количество итераций находится в пределах от m до 2m.

Пусть задача (3.6), (3.7), (3.8) невырожденна и столбцы A1, A2, …, Am матрицы А образуют базис некоторой угловой точки x(0), а переменные x1, x2, …, xm являются базисными переменными. Решая систему уравнений (3.7) относительно переменных x1, x2, …, xm и исключая базисные переменные из целевой функции, приходим к следующей ЗЛП, эквивалентной первоначальной задаче: минимизировать функцию

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Дальнейшая стратегия определяется основной теоремой симплексметода.

Т е о р е м а. Если после выполнения очередной итерации в опорной точке x(0):

1) все оценки окажутся неотрицательными, т. е. ek 0 для всех k = m + 1, …, n, то x(0) – решение задачи (3.6), (3.7), (3.8);

d ij r 0, i = 1, 2, …, m, то целевая функция z(x) неограниченно убывает на допустимом множестве (3.7), (3.8), т.е. задача (3.6), (3.7), (3.8) не имеет решения;

3) найдется номер jr, m + 1 r n, такой, что e jr < 0, но среди коесть положительные числа di1 jr, …, dis jr, то можно пеэффициентов d i jr рейти к другой опорной точке x(1), в которой f(x(1)) f(x(0)).

Третий случай означает, что решение ещё не достигнуто и необходимо выполнить следующую итерацию, которая включает в себя переход от х(0) к новой опорной точке х(1) и проверку последней на оптимальность. Для такого перехода мы вводим в список базисных переменных в точке х(0) новую базисную переменную x jr, m + 1 r n, выбирая ее из тех свободных переменных, которые входят в приведенное выражение z1(x) с отрицательным коэффициентом, и выводим из списка переменную x jl, определяя номер jl с помощью положительных коэффициентов di1 jr, …, dis jr при x jr в системе (3.10). А именно, выбираем номер jl из условия

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Вообще говоря, индекс jr в третьей части теоремы определяется неоднозначно, приведённое выражение (3.9) для функции f(x) может содержать несколько отрицательных оценок ejk. На практике обычно выбирают наименьшую из них.

В условии (3.11) возможны два случая: = 0 или > 0. При = имеем х(0) = х(1), т.е. происходит лишь замена одного базиса точки х(0) другим.

При > 0 заведомо х(0) х(1) и f(х(1)) < f(х(0)). Если точка х(0) невырожденная, то обязательно > 0.

Разработка моделей линейного программирования Термин «разработка» означает построение моделей ЛП практических задач. Она включает следующие основные этапы: 1) определение переменных задачи, представление ее ограничений в виде линейных уравнений или неравенств; 2) задание линейной целевой функции, подлежащей минимизации или максимизации. В качестве примера, иллюстрирующего основные этапы разработки модели ЛП, рассмотрим простейшую задачу производственного планирования.

Пусть имеется некоторый экономический объект (предприятие, цех, артель и т.п.), который может производить некоторую продукцию п видов.

В процессе производства допустимо использование т видов ресурсов (сырья, рабочего времени и пр.). Применяемые технологии характеризуются нормами затрат единиц сырья на единицу производимого продукта. Обозначим через ai,j количество i-го ресурса (i = 1, …, m), которое тратится на производство единицы j-го продукта (j = 1, …, n).

Если j-й продукт производится в количестве xj, то в рамках описанных выше технологий мы должны потратить a1,j xj первого ресурса, a2,j xj – второго, и так далее, am,j xj – m-го. Сводный план производства по всем продуктам может быть представлен в виде п-мерного вектора-строки х = (x1, x2, …, xj, …, xn). Тогда общие затраты i-го ресурса на производство всех продуктов можно выразить в виде суммы Очевидно, что всякая реальная производственная система имеет ограничения на ресурсы, которые она тратит в процессе производства. В рам-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Следует иметь в виду, что к ресурсам относятся также производственные мощности. В этом случае соответствующие ограничения в системе (3.12) могут иметь вид, например, К системе (3.12) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства:

Обозначив через cj цену единицы j-го продукта, получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором х:

Формулы (3.12), (3.13), (3.14) являются не чем иным, как простейшей математической моделью, описывающей отдельные стороны функционирования некоторого экономического объекта, поведением которого мы хотим управлять. В рамках данной модели можно поставить различные задачи, но, скорее всего, самой естественной будет задача поиска такого плана производства х, который дает наибольшее значение суммарного дохода, т. е. функции (3.14), и одновременно удовлетворяет системе ограничений (3.12), (3.13).

Кратко такую задачу можно записать в следующем виде:

где допустимое множество Х определяется ограничениями (3.12), (3.13), (3.14).

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Например, если сj означает общие расходы на производство единицы j-го продукта, то суммарные затраты на выполнение всего плана х выражаются также функцией (3.14). Однако в этом случае наиболее естественной задачей для модели (3.12), (3.13), (3.14) будет задача поиска такого плана производства х, удовлетворяющего ограничениям (3.12), (3.13), при котором значение суммарных затрат, т.е. функции z(x), будет наименьшим:

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

Любые изменения коэффициентов в исходной модели могут привести к изменению статически найденного оптимального решения задачи. Анализ модели связан с исследованием возможных изменений статически оптимального решения в результате изменений в исходной модели: коэффициентов целевой функции, матрицы коэффициентов, правых частей уравнений – ограничений. Причиной недопустимости решения может стать изменение ресурсов (правых частей ограничений) или добавление новых ограничений. К неоптимальности решения приводит изменение коэффициентов целевой функции или некоторых коэффициентов левых частей ограничений.

Послеоптимизационный анализ включает анализ внутренней структуры и параметрирование исходных данных модели.

Для анализа внутренней структуры используются данные из симплекс-таблицы, соответствующей оптимальному решению, а также двойственные оценки, получаемые в результате двойственной задачи ЛП.

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

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

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

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

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Нулевое значение дополнительной переменной в оптимальном плане означает неполное использование соответствующего ресурса.

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

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

Двойственная задача ЛП симметрична прямой (исходной) задаче:

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

Двойственную задачу получаем путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:

1. Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

2. Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

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

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

4. Направление оптимизации меняется на обратное, а знак ограничения определяется по правилу: прямая задача на максимум – ограничения в двойственной задаче вида «» и наоборот.

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

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

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

2. В соответствии с вариантами заданий построить модель, привести ее к канонической форме, составить двойственную задачу ЛП (в канонической форме).

3. Изучить порядок эксплуатации программных средств решения задачи ЛП с помощью ЭВМ.

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

5. Ввести данные в ЭВМ и получить решение задачи.

6. По заданию преподавателя получить с помощью ЭВМ двойственные оценки задачи.

7. Оформить отчет, в который включить: краткую формулировку цели и содержания работы; математическую модель планирования, прямую и двойственную задачи ЛП в канонической форме; алгоритм симплекс-метода;

исходные данные; результаты расчета на ЭВМ; анализ результатов и технико-экономическую оценку оптимального плана.

Решить задачу линейного программирования графическим методом.

Проверить результаты с помощью пакета прикладных программ. Исходные данные принять по табл. 3.1.

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

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

2) сформулировать в экономических терминах двойственную задачу и составить ее математическую модель;

3) используя решение исходной задачи и соответствие между двойственными переменными, найти компоненты оптимального плана двойственной задачи – двойственные оценки yi* (i = 1, 3).

Все необходимые числовые данные приведены в табл. 3.2, табл. 3.3.

Параметр

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

2. Чем отличается общая задача линейного программирования от канонической?

3. Всегда ли общую задачу линейного программирования можно привести к канонической форме? Опишите метод приведения общей задачи к каноническому виду.

4. Чем отличается выпуклый многогранник от выпуклого многогранного множества?

5. Дайте определение угловой точки выпуклого многогранного множества?

6. Перечислите свойства задач линейного программирования.

7. Сформулируйте основную теорему линейного программирования.

8. В чем заключается первая геометрическая интерпретация задачи линейного программирования?

9. В чем состоит идея геометрического метода решения задачи линейного программирования? Для каких задач он применяется?

10. В чем заключается вторая геометрическая интерпретация задачи линейного программирования?

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

12. Какая опорная точка называется вырожденной (невырожденной)?

13. Какая задача ЛП называется вырожденной (невырожденной)?

14. В чем состоит различие между симплекс-методом и методом полного перебора опорных точек допустимого множества?

15. Как с помощью симплекс-метода определить, что задача ЛП не имеет решения?

16. Что такое разрешающий элемент и разрешающее уравнение? Для чего они используются?

ЛАБОРАТОРНАЯ РАБОТА

ТРАНСПОРТНАЯ ЗАДАЧА

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

Пусть в пунктах А1, А2, …, Аm изготавливается некоторый однородный продукт, причем объем производства этого продукта в пункте Ai составляет ai ед., i = 1, …, m. Произведенный продукт должен быть доставлен в пункты потребления В1, В2, …, Вn, причем объем потребления в пункте Bj составляет bj ед. продукта. Предполагается, что транспортировка готовой продукции возможна из любого пункта производства в любой пункт потребления и транспортные издержки, приходящиеся на перевозку единицы продукта из пункта Аi в пункт Вj, составляют cij ден. ед. Задача состоит в организации такого плана перевозок, при котором суммарные транспортные издержки были бы минимальными.

Обозначим через xij количество продукта, перевозимого c i-го предприятия к j-му потребителю. План перевозки груза в данной транспортной сети представляет собой массив элементов размерности m n:

Если реальная перевозка между пунктами i и j отсутствует, то полагают xi,j = 0.

Ограничения на возможные значения x Rmn включают в себя:

ограничения на удовлетворение потребностей во всех пунктах потребления:

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

условия неотрицательности компонент плана:

Математически транспортная задача ставится следующим образом:

определить точку минимума функции суммарных транспортных издержек при ограничениях (4.1), (4.2), (4.3).

Полученная задача является задачей линейного программирования.

Существенная характеристика описываемой задачи – соотношение параметров ai и bj. Если суммарный объем производства равен суммарному объему потребления, а именно выполняется условие баланса то система называется сбалансированной. При выполнении условия баланса разумно накладывать такие ограничения на суммарный ввоз и вывоз груза, при которых полностью вывозится весь груз и не остается неудовлетворенных потребностей, т.е. условия (4.1), (4.2) приобретают форму равенства.

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

1. Изучить постановку и методы решения транспортных задач.

2. Изучить порядок эксплуатации программных средств решения задачи ЛП с помощью ЭВМ.

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

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

5. Оформить отчет, в который включить: титульный лист, краткую формулировку цели и содержания работы, математическую модель транспортной задачи, краткое описание методов решения, задание, результаты расчета на ЭВМ, анализ результатов.

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

ЛАБОРАТОРНАЯ РАБОТА 4. ТРАНСПОРТНАЯ ЗАДАЧА

2. Какие ограничения задают допустимое множетво транспортной задачи?

3. Каков экономический смысл решения транспортной задачи?

4. Можно ли решать транспортную задачу методами линейного программирования?

5. Сформулируйте условие баланса. Какова его роль в транспортных задачах?

6. Когда транспортна задача называется сбалансированной?

ЛАБОРАТОРНАЯ РАБОТА

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Динамическое программирование представляет собой математический метод для нахождения оптимальных решений многошаговых (многоэтапных) задач оптимизации.

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

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

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

Эта задача является многошаговой. Шагом управления здесь будет хозяйственный год. Управление процессом состоит в перераспределении средств в начале каждого хозяйственного года.

Обычно методами динамического программирования оптимизируют работу управляемых систем, эффект которой оценивается аддитивной целевой функцией. Аддитивной называется функция многих переменных f(x1, x2, …, xn) вида

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Принцип оптимальности и рекуррентное соотношение Динамическое программирование как научное направление возникло и сформировалось в 1951–1953 гг. благодаря работам Р. Беллмана и его сотрудников. Метод динамического программирования позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Процесс решения задачи разбивается на шаги. При этом если задано начальное состояние управляемой системы, то нумерация шагов осуществляется от конца к началу, а если конечное, то – от начала к концу.

Основным принципом, на котором базируется оптимизация многошагового процесса и особенности вычислительного метода динамического программирования, является принцип оптимальности Р. Беллмана [2, 3].

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

Этот принцип можно сформулировать и по-другому: оптимальное поведение в многошаговом процессе обладает тем свойством, что какими бы ни были решение, принятое на последнем шаге, и состояние процесса перед последним шагом, предыдущие решения должны составлять оптимальное относительно этого состояния поведение.

Принцип оптимальности имеет конструктивный характер и непосредственно указывает процедуру нахождения оптимального решения. Математически он записывается выражением вида l = 0, 1, …, n – 1, где Ul = ( ul(1); …; ul(m)) – решение (управление), выбранное на l-м шаге; Sl = (sl(1); …; sl(m)) – состояние системы на l-м шаге; Rl – непосредственный эффект, достигаемый на l-м шаге; fn-l – оптимальное значение эффекта, достигаемого за n – l шагов; n - количество шагов (этапов).

«Optimum» в выражении (5.1) означает максимум или минимум в зависимости от условия задачи. Формула (5.1) носит название уравнения Беллмана или рекуррентного соотношения. Процесс вычислени fn-l, l = 0, …, n – 1, осуществляется при естественном начальном условии f0(Sn) = 0, которое означает, что за пределами конечного состояния системы эффект равен нулю.

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

Пусть требуется перевезти груз из города А в город В. Сеть дорог, связывающих эти города, изображена в виде графа на рис. 5.1. Вершинам графа поставлены в соответствие города, а дугам – транспортные магистрали.

Стоимость перевозки груза из города s (s = 1, …, 6) в город j (j = 2, …, 7) проставлена над соответствующими дугами графа. Необходимо найти маршрут, связывающий города А и В, для которого суммарные затраты на перевозку груза были бы наименьшими.

Для решения задачи разобьем все множество вершин (городов) на подмножества. В первое подмножество включим исходную вершину 1. Во второе – вершины, в которые входят дуги, выходящие из вершины 1. В третье – вершины, в которые входят дуги, выходящие из вершин второго подмножества. Таким образом, продолжая разбиение дальше, получим четыре подмножества: {1}, {2, 3, 4}, {5, 6}, {7}. Очевидно, что любой маршрут из города 1 в город 7 содержит ровно три дуги, каждая из которых связывает вершины, принадлежащие соответствующим подмножествам. Следовательно, процесс решения задачи (нахождения оптимального маршрута) разбивается на три этапа. На первом этапе принимается решение о том, через какой город, принадлежащий второму подмножеству, везти груз из города 1. На втором этапе необходимо определить, через какой город третьего подмножества везти груз из некоторого города, принадлежащего второму подмножеству. На последнем (третьем) этапе формируется оптимальный маршрут.

Перенумеруем этапы от конечной вершины графа к начальной и введем обозначения: n – номер шага (n = 1, 2, 3); fn(s) – минимальные затраты на

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Здесь все обозначения несут важную смысловую нагрузку: f – это целевая функция, s – состояние системы (номер города), индекс n – динамическая информация о том, что из города s до конечного города осталось n шагов.

Предположим, что груз доставлен в город 7, следовательно, число оставшихся шагов равно нулю (n = 0) и fn(s) = f0(7) = 0, так как из города 7 груз вести не надо.

Рассмотрим последний шаг (n = 1) и вычислим для него значение функции. Очевидно, что в город 7 груз может быть доставлен из города 5 или из города 6. Вычислим затраты на перевозку для этих состояний:

Чтобы произвести расчет для n = 2, выдвинем гипотезы о месте нахождения груза: 1-я гипотеза – груз находится в городе 2; 2-я гипотеза – груз находится в городе 3; 3-я гипотеза – груз находится в городе 4.

Из города 2 в город 7 можно перевезти груз или через город 5, или через город 6. Поэтому оптимальный маршрут из города 2 найдем по выражению Здесь s = 2 и j2(2) = 6, т. е. условно-оптимальный маршрут проходит через город 6. Аналогично для s = 3 и s = 4:

Вычисления для третьего шага (n = 3) показывают, что j3(1) = 2, т.е. минимальные затраты на перевозку груза f3(1) = 11 и оптимальный маршрут проходит через город 2. Далее из вычислений f2(2) следует, что оптимальный маршрут проходит через город 6, так как j2(2) = 6. Наконец, из

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Следует отметить, что метод динамического программирования применим только для нахождения кратчайшего пути на связных графах, где любой маршрут состоит из одного и того же числа дуг, как, например, на рассмотренном графе. Для графов более общей структуры используются соответствующие алгоритмы теории графов [6].

1. Изучить основные принципы динамического программирования.

2. Изучить порядок эксплуатации программных средств.

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

4. Ввести данные в ЭВМ и получить решение задачи.

5. Оформить отчет, в который включить: краткую формулировку цели и содержания работы, основные положения теории динамического программирования, вариант задания, результаты расчета на ЭВМ, анализ результатов и выводы.

Найти кротчайший путь из первой вершины в последнюю по счету в заданном графе:

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

ЛАБОРАТОРНАЯ РАБОТА 5. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

2. В чем заключается суть метода динамического программирования?

3. Сформулируйте принцип оптимальности Беллмана.

4. Что является целевой функцией в задаче о кратчайшем маршруте?

5. Какой параметр определяет состояние системы на каждом шаге?

ЛАБОРАТОРНАЯ РАБОТА

ИДЕНТИФИКАЦИЯ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

Под идентификацией объектов понимается построение оптимальных в некотором смысле математических моделей по реализации их входных и выходных параметров.

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