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

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

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

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

рассмотрим неявную разностную схему

Здесь Ai = Ci = 1, Bi = 1 + /?. 2 /(2ат), Д = li 2 {-u" - г/")/(2ат). В нашем случае A j, Д и С* не зависят от индекса i , однако если шаг сетки будет переменным, то все коэффициенты будут зависеть от номера узла. Важно отметить, что А{, Bj, Ci, g n+l , / n+1 - известные величины. Соотношение (7.2) представляет собой систему линейных уравнений для неизвестных Uq + , Мдг + .

Распшренная матрица этой системы имеет вид

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

Наличие левого граничного условия (mq +1 = n+1) позволяет искать решение в виде (для простоты обозначений верхний индекс у неизвестной опущен) соотношения

Оно называется прогоночным соотношением , а входящие в него входящие в него коэффициенты A"*_i и Li- - прогоночными коэффициентами. Для i = 1 (7.1) выполняется, если принять

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

Исключим с помощью прогоиочного соотношения (7.3) неизвестную щ -1 из (7.2):

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

в форме, совпадающей с прогоночным соотношением. Сравнение (7.5) и (7.3) дает рекуррентные соотношения для прогоночных коэффициентов:

Пользуясь начальными значениями Ко = 0, Lq = , можно последовательно вычислить К, L ], К 2 , ^2, ..., Ln- - компоненты векторов прогоночных коэффициентов. Этот вычислительный процесс называют прямой прогонкой. Нетрудно убедиться, что прямая прогонка с помощью элементарных преобразований переводит трехдиагональную матрицу исходной линейной системы в верхнюю двухдиагональную, причем число арифметических операций (из-за особого вида исходной матрицы) пропорционально числу неизвестных 1 .

Двухдиагональный вид полученной матрицы позволяет легко построить процесс вычисления неизвестных. Прогоночное соотношение для последнего узла wjv-i = Kn-Un + L^~ 1, совместно с правым краевым условием = I, позволяет вычислить идг_ 1, а затем по рекуррентной формуле (7.3) последовательно определить все неизвестные un-2, un-3, ..., щ разностной задачи. Последовательное вычисление неизвестных с помощью прогоночного соотношения (7.3) называют обратной прогонкой. По своей сути, метод прогонки представляет собой вариант гауссового исключения, который учитывает особенности структуры трехдиагональной матрицы и устраняет операции над ее нулевыми элементами.

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

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

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

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

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

Запишем систему уравнений в виде

На главной диагонали матрицы этой системы стоят элементы b 1, b 2, …, bn ,над ней – элементы с 1, с2,... , с n -1 под ней – элементы а 2, а 3,... , ап (при этом обычно все коэффициенты bi не равны нулю). Остальные элементы матрицы равны нулю.

Метод прогонки состоит из двух этапов – прямой прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в вычислении прогоночных коэффициентов Ai ,Bi ,с помощью которых каждое неизвестное xi выражается через zi +1 :

Из первого уравнения системы (2.13) найдем

С другой стороны, по формуле (2.14) Приравнивая коэффициенты в обоих выражениях для х 1, получаем

(2.15)

Подставим во второе уравнение системы (2.13) вместо х 1его выражение через х 2по формуле (2.14):

Выразим отсюда х 2 через х 3:

Аналогично вычисляют прогоночные коэффициенты для любого номера i :

(2.16)

Обратная прогонка состоит в последовательном вычислении неизвестных xi . Сначала нужно найти хп. Для этого воспользуемся выражением (2.14) при i = п –1 и последним уравнением системы (2.13). Запишем их:

Отсюда, исключая х n-1 , находим

Далее, используя формулы (2.14) и вычисленные ранее по формулам (2.15), (2.16) прогоночные коэффициенты, последовательно вычисляем все неизвестные х n - 1, xn -2 ,....,х 1. Алгоритм решения системы линейных уравнений вида (2.13) методом прогонки приведен на рис. 2.4.

Рис. 2.4. Алгоритм метода прогонки

При анализе алгоритма метода прогонки надо учитывать возможность деления на нуль в формулах (2.15), (2.16). Можно показать, что при выполнении условия преобладания диагональных элементов, т.е. если , причем хотя бы для одного значения i имеет место строгое неравенство, деления на нуль не возникает, и система (2.13) имеет единственное решение.

Приведенное условие преобладания диагональных элементов обеспечивает также устойчивость метода прогонки относительно погрешностей округлений. Последнее обстоятельство позволяет использовать метод прогонки для решения больших систем уравнений. Заметим, что данное условие устойчивости прогонки является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (2.13) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных элементов.

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

Базисным столбцам соответствуют единичные столбцы.

Расчет остальных значений таблицы:

«БП – Базисный План»:

; ;

«х1»: ; ;

«х5»: ; .

Значения индексной строки неотрицательны, следовательно получаем оптимальное решение: , ; .

Ответ: максимальную прибыль от реализации изготовленной продукции, равную 160/3 ед., обеспечивает выпуск только продукции второго типа в количестве 80/9 единиц.

Задание № 2

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

Т.к. последняя цифра шифра равна 8, то А=2; В=5.

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

Решение:

1) Начертим область, которую задает система неравенств.

Эта область – треугольник АВС с координатами вершин: А(0; 2); В(4; 6) и С(16/3; 14/3).

Уровни целевой функции представляют собой окружности с центром в точке (2; 5). Квадраты радиусов будут являться значениями целевой функции. Тогда по рисунку видно, что минимальное значение целевой функции достигается в точке Н, максимальное – либо в точке А, либо в точке С.

Значение целевой функции в точке А: ;

Значение целевой функции в точке С: ;

Значит, наибольшее значение функции достигается в точке А(0; 2) и равно 13.

Найдем координаты точки Н.

Для этого рассмотрим систему:

ó

ó

Прямая является касательной к окружности, если уравнение имеет единственное решение. Квадратное уравнение имеет единственное решение, если дискриминант равен 0.

Тогда ; ; - минимальное значение функции.

2) Составим функцию Лагранжа для нахождение минимального решения:

При x 1 =2.5; x 2 =4.5 получим:

ó

Система имеет решение при , т.е. достаточные условия экстремума выполняются.

Составим функцию Лагранжа для нахождение максимального решения:

Достаточные условия экстремума:

При x 1 =0; x 2 =2 получим:

ó ó

Система также имеет решение, т.е. достаточные условия экстремума выполняются.

Ответ: минимум целевой функции достигается при ; ; максимум целевой функции достигается при ; .

Задание № 3

Двум предприятиям выделяются средства в количестве d единиц. При выделении первому предприятию на год x единиц средств оно обеспечивает доход k 1 x единиц, а при выделении второму предприятию y единиц средств, оно обеспечивает доход k 1 y единиц. Остаток средств к концу года для первого предприятия равен nx , а для второго my . Как распределить все средства в течение 4-х лет, чтобы общий доход был наибольшим? Задачу решить методом динамического программирования.

i=8, k=1.

A=2200; k 1 =6; k 2 =1; n=0.2; m=0.5.

Решение:

Весь период длительностью 4 года разбиваем на 4 этапа, каждый из которых равен одному году. Пронумеруем этапы начиная с первого года. Пусть Х k и Y k – средства, выделенные соответственно предприятиям А и В на k – том этапе. Тогда сумма Х k + Y k =а k является общим количеством средств, используемых на k – том этапе и оставшиеся от предыдущего этапа k – 1. на первом этапе используются все выделенные средства и а 1 =2200 ед. доход, который будет получен на k – том этапе, при выделении Х k и Y k единиц составит 6Х k + 1Y k . пусть максимальный доход, полученный на последних этапах начиная с k – того этапа составляет f k (а k) ед. запишем функциональное уравнение Беллмана, выражающее принцип оптимальности: каково бы не было начальное состояние и начальное решение последующее решение должно быть оптимальным по отношению к состоянию, получаемому в результате начального состояния:

Для каждого этапа нужно выбрать значение Х k , а значение Y k =а k – х k . С учетом этого найдем доход на k – том этапе:

Функциональное уравнение Беллмана будет иметь вид:

Рассмотрим все этапы, начиная с последнего.

(т.к. максимум линейной функции достигается в конце отрезка при х 4 = а 4);

Государственное бюджетное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА

по дисциплине « ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ »

на тему « МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ »

вариант 7

Выполнил:

студент заочного отделения

4-го курса группы ЗА-419

ФИО: Кужелев С. А.

Проверила:

Девятерикова М. В.

Омск – 2012 г.
^

Задание 1. Графический метод решения задач линейного программирования.

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

Первое ограничение модели имеет вид . Заменив в нем знак ≤ на знак =, получаем уравнение. На рис. 1.1 оно определяет прямую (1), которая разбивает плоскость на две полуплоскости, в данном случае выше линии и ниже нее. Чтобы выбрать, какая из них удовлетворяет неравенству , подставим в него координаты любой точки, не лежащей на данной прямой (например, начало координат х 1 = 0, х 2 = 0). Так как получаем верное выражение (20 0 + 6 0 = 0 ≤15), то неравенству удовлетворяет полуплоскость, содержащая начало координат (помечена стрелкой). В противном случае другая полуплоскость.

Аналогично поступаем с остальными ограничениями задачи. Пересечение всех построенных полуплоскостей с первым квадрантом образует ABCD (см. рис. 1). Это и есть допустимая область задачи.

Шаг 2. Построение линии уровня Линия уровня целевой функции - это множество точек плоскости, в которых целевая функция принимает постоянное значение. Такое множество задается уравнением f ( x ) = const . Положим, например, const = 0 и построим линию у ровня f ( x ) = 0 , т.е. в нашем случае прямую 7x 1 + 6x 2 = 0.

Данная прямая проходит через начало координат и перпендикулярна вектору . Этот вектор является градиентом целевой функции в точке (0,0). Градиент функции - это вектор значений частных производных данной функции в рассматриваемой точке. В случае задачи ЛП частные производные целевой функции равны коэффициентам C i, j = 1 , ..., n .

Градиент показывает направление наискорейшего роста функции. Перемещая линию уровня целевой функции f ( x ) = const . перпендикулярно направлению градиента, найдем последнюю точку, в которой она пересекается с областью. В нашем случае это точка D, которая и будет точкой максимума целевой функции (см. рис. 2)

Она лежит на пересечении прямых (2 ) и (3 ) (см. рис. 1 ) и задает оптимальное решение.

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

^ Шаг 3. Определение координат точки максимума (минимума) и оптимального значения целевой функции

Чтобы найти координаты точки C, необходимо решить систему, состоящую из соответствующих прямым уравнений (в данном случае из уравнений 2 и 3 ):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Получим оптимальное решение = 1,33.

^ Оптимальное значение целевой функции f * = f (х*) = 7 * 0 + 6 * 1,33 = 7,8

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

Строим в системе координат х 1 ох 2 прямые

Находим полуплоскости, определяемые системой. Так как неравенства системы выполняется для любой точки из соответствующей полуплоскости, то их достаточно проверить для какой-либо одной точки. Используем точку (0;0). Подставим её координаты в первое неравенство системы. Т.к. , то неравенство определяет полуплоскость, не содержащую точку (0;0). Аналогично определяем остальные полуплоскости. Находим множество допустимых решений как общую часть полученных полуплоскостей - это заштрихованная область.

Строим вектор и перпендикулярно к нему прямую нулевого уровня.

Перемещая прямую (5) в направлении вектора и видим, что у области максимальная точка будет в точке А пересечения прямой (3) и прямой (2). Находим решение системы уравнений:

Значит, получили точку (13;11) и.

Перемещая прямую (5) в направлении вектора и видим, что у области минимальная точка будет в точке В пересечения прямой (1) и прямой (4). Находим решение системы уравнений:

Значит, получили точку (6;6) и.

2. Мебельная фирма производит комбинированные шкафы и компьютерные столики. Их производство ограничено наличием сырья (высококачественных досок, фурнитуры) и временем работы обрабатывающих их станков. Для каждого шкафа требуется 5 м2 досок, для стола - 2 м2. На один шкаф расходуется фурнитуры на 10$, на один столик также на 8$. Фирма может получать от своих поставщиков до 600 м2 досок в месяц и фурнитуры на 2000$. Для каждого шкафа требуется 7 часов работы станков, для стола - 3 часа. В месяц возможно использовать всего 840 часов работы станков.

Сколько комбинированных шкафов и компьютерных столиков фирме следует выпускать в месяц для получения максимальной прибыли, если один шкаф приносит 100$ прибыли, а каждый стол - 50$?

• 1. Составить математическую модель задачи и решить её симплексным методом.
• 2. Составить математическую модель двойственной задачи, записать её решение исходя из решения исходной.
• 3. Установить степень дефицитности используемых ресурсов и обосновать рентабельность оптимального плана.
• 4. Исследовать возможности дальнейшего увеличения выпуска продукции в зависимости от использования каждого вида ресурсов.
• 5. Оценить целесообразность введения нового вида продукции - книжных полок, если на изготовление одной полки расходуется 1 м 2 досок и фурнитуры на 5$,и требуется затратить 0,25 часа работы станков и прибыль от реализации одной полки составляет 20$.
• 1. Построим математическую модель для данной задачи:

Обозначим через x 1 - объём производства шкафов, а х 2 - объём производства столиков. Составим систему ограничений и функцию цели:

Задачу решаем симплекс-методом. Запишем её в каноническом виде:

Запишем данные задачи в виде таблицы:

Таблица 1

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