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

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

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

Скачать заметку в формате , рисунки в формате

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

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

Рассмотрим пример построения математической модели линейного программирования

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

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд (рис. 1). На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

Рис. 1. Использование и предоставление ресурсов

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

Линейная модель может быть построена в четыре этапа.

Этап 1. Определение переменных

Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:

Z = суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

Существует ряд неизвестных искомых переменных (обозначим их х 1 , х 2 , х 3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

х 1 = количество единиц продукта А, произведенных в следующем месяце.

х 2 = количество единиц продукта В, произведенных в следующем месяце.

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

Этап. 2. Построение целевой функции

Целевая функция – это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х 1 , х 2 … в виде линейного уравнения.

В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х 1 единиц продукта А, маржинальная прибыль составит 2500 * х 1 . Аналогично маржинальная прибыль от изготовления х 2 единиц продукта В составит 3500 * х 2 . Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х 1 единиц продукта А и х 2 единиц продукта В, то есть, целевая переменная Z составит:

Z = 2500 * х 1 + 3500 *х 2

Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:

Максимизировать Z = 2500 * х 1 + 3500 *х 2

Этап. 3. Определение ограничений

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

В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х 1 их 2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х 1 , единиц, то будет потрачено З * х 1 , часов этого ресурса. Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х 2 продуктов, то потребуется 10 * х 2 часов. Таким образом, общий объем машинного времени, необходимого для производства х 1 единиц продукта А и х 2 единиц продукта В, составляет 3 * х 1 + 10 * х 2 . Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:

3 * х 1 + 10 * х 2 ≤ 330

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

16 * х 1 + 4 * х 2 ≤ 400

6 * х 1 + 6 * х 2 ≤ 240

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап 4. Запись условий неотрицательности

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х 1 ≥ 0 и х 2 ≥ 0. В нашем примере второе условия является избыточным, так как выше было определено, что х 2 не может быть меньше 12.

Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:

Максимизировать: Z = 2500 * х 1 + 3500 *х 2

При условии, что: 3 * х 1 + 10 * х 2 ≤ 330

16 * х 1 + 4 * х 2 ≤ 400

6 * х 1 + 6 * х 2 ≤ 240

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

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

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

Рис. 2. Оси графика линейного программирования

Рассмотрим, например, первое ограничение: 3 * х 1 + 10 * х 2 ≤ 330. Это неравенство описывает область, лежащую ниже прямой: 3 * х 1 + 10 * х 2 = 330. Эта прямая пересекает ось х 1 при значении х 2 = 0, то есть уравнение выглядит так: 3 * х 1 + 10 * 0 = 330, а его решение: х 1 = 330 / 3 = 110

Аналогично вычисляем точки пересечения с осями х 1 и х 2 для всех условий-ограничений:

Графически первое ограничение отражено на рис. 3.

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

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

Аналогично отражаем на графике остальные ограничения (рис. 4). Значения х 1 и х 2 на или внутри заштрихованной области ABCDE будут соответствовать всем ограничениям модели. Такая область называется областью допустимых решений.

Рис. 4. Область допустимых решений для модели в целом

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

Z = 2500 * х 1 + 3500 *х 2

разделим (или умножим) коэффициенты перед х 1 и х 2 на одно и тоже число, так чтобы получившиеся значения попали в диапазон, отражаемый на графике; в нашем случае такой диапазон – от 0 до 120; поэтому коэффициенты можно разделить на 100 (или 50):

Z = 25х 1 + 35х 2

затем присвоим Z значение равное произведению коэффициентов перед х 1 и х 2 (25 * 35 = 875):

875 = 25х 1 + 35х 2

и, наконец, найдем точки пересечения прямой с осями х 1 и х 2:

Нанесем это целевое уравнение на график аналогично ограничениям (рис. 5):

Рис. 5. Нанесение целевой функции (черная пунктирная линия) на область допустимых решений

Значение Z постоянно на всем протяжении линии целевой функции. Чтобы найти значения х 1 и х 2 , которые максимизируют Z, нужно параллельно переносить линию целевой функции к такой точке в границах области допустимых решений, которая расположена на максимальном удалении от исходной линии целевой функции вверх и вправо, то есть к точке С (рис. 6).

Рис. 6. Линия целевой функции достигла максимума в пределах области допустимых решений (в точке С)

Можно сделать вывод, что оптимальное решение будет находиться в одной из крайних точек области принятия решения. В какой именно, будет зависеть от угла наклона целевой функции и от того, какую задачу мы решаем: максимизации или минимизации. Таким образом, не обязательно чертить целевую функцию – все, что необходимо, это определить значения х 1 и х 2 в каждой из крайних точек путем считывания с диаграммы или путем решения соответствующей пары уравнений. Найденные значения х 1 и х 2 затем подставляются в целевую функцию для расчета соответствующей величины Z. Оптимальным решением является то, при котором получена максимальная величина Z при решении задачи максимизации, и минимальная – при решении задачи минимизации.

Определим, например значения х 1 и х 2 в точке С. Заметим, что точка С находится на пересечении линий: 3х 1 + 10х 2 = 330 и 6х 1 + 6х 2 = 240. Решение этой системы уравнений дает: х 1 = 10, х 2 = 30. Результаты расчета для всех вершин области допустимых решений приведены в таблице:

Таким образом, Николай Кузнецом должен запланировать на следующий месяц производство 10 изделий А и 30 изделий В, что позволит ему получить маржинальную прибыль в размере 130 тыс. руб.

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

1. Начертите на графике две оси, представляющие собою два параметра решения; нарисуйте только I-й квадрант.
2. Определите координаты точек пересечения всех граничных условий с осями, подставляя в уравнения граничных условий поочередно значения х 1 = 0 и х 2 = 0.
3. Нанести линии ограничений модели на график.
4. Определите на графике область (называемую допустимой областью принятия решения), которая соответствует всем ограничениям. Если такая область отсутствует, значит, модель не имеет решения.
5. Определите значения искомых переменных в крайних точках области принятия решения, и в каждом случае рассчитайте соответствующее значение целевой переменной Z.
6. Для задач максимизации решение – точка, в которой Z максимально, для задач минимизации, решение – точка, в которой Z минимально.

Тесты для текущего контроля знаний

1. Любая экономико – математическая модель задачи линейного программирования состоит из:

A. целевой функции и системы ограничений

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

C. системы ограничений и условия неотрицательности переменных

D. целевой функции и условия неотрицательности переменных

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

B. система уравнений

C. система неравенств

D. условие неотрицательности переменных

3. Оптимальное решение задачи математического программирования – это

A. допустимое решение системы ограничений

B. любое решение системы ограничений

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

D. максимальное или минимальное решение системы ограничений

4. Система ограничений называется стандартной, если она содержит

A. все знаки

B. все знаки

C. все знаки

D. все знаки

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

A. одна переменная

B. две переменные

C. три переменные

D. четыре переменные

6. Неравенство вида описывает

B. окружность

C. полуплоскость

D. плоскость

7. Максимум или минимум целевой функции находится

A. в начале координат

B. на сторонах выпуклого многоугольника решений

C. внутри выпуклого многоугольника решений

D. в вершинах выпуклого многоугольника решений

8. Каноническим видом ЗЛП называется такой ее вид, в котором система ограничений содержит знаки

A. все знаки

B. все знаки

C. все знаки

D. все знаки

9. Если ограничение задано со знаком «>=», то дополнительная переменная вводится в это ограничение с коэффициентом

B. -1

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

C. 0

A. количество ресурса с номером i, необходимого для изготовления 1 единицы продукции j – го вида

B. неиспользованные ресурсы i - го вида

C. прибыль от реализации 1 единицы продукции j – го вида

D. количество продукции j – го вида

12. Разрешающий столбец при решении ЗЛП на max целевой функции выбирается исходя из условия

A. наибольшее положительное значение коэффициента Cj целевой функции

B. наименьшее положительное значение коэффициента Cj целевой функции

C. наибольшее отрицательное значение коэффициента Cj целевой функции

D. любой столбец коэффициентов при неизвестных

13. Значение целевой функции в таблице с оптимальным планом находится

A. на пересечении строки коэффициентов целевой функции со столбцом коэффициентов при х1

B. на пересечении строки коэффициентов целевой функции со столбцом b

C. в столбце коэффициентов при хn

D. на пересечении строки коэффициентов целевой функции со столбцом первоначального базиса

14. Искусственные переменные в систему ограничений в каноническом виде вводятся с коэффициентом

A. 1

15. Оптимальность плана в симплексной таблице определяется

A. по столбцу b

B. по строке значений целевой функции

C. по разрешающей строке

D. по разрешающему столбцу

16. Дана задача линейного программирования

B. 1

17. Дана задача линейного программирования

Количество искусственных переменных для этой задачи равно

C. 2

18. Если исходная ЗЛП имеет вид

тогда ограничения двойственной задачи

A. имеют вид

B. имеют вид

C. имеют вид

D. имеют вид

19. Если исходная ЗЛП имеет вид

A. имеют вид

B. имеют вид

C. имеют вид

D. имеют вид

20. Коэффициентами при неизвестных целевой функции двойственной задачи являются

A. коэффициенты при неизвестных целевой функции исходной задачи

B. свободные члены системы ограничений исходной задачи

C. неизвестные исходной задачи

D. коэффициенты при неизвестных системы ограничений исходной задачи

21. Если исходная ЗЛП была на максимум целевой функции, то двойственная задача будет

A. тоже на максимум

B. либо на максимум, либо на минимум

C. и на максимум, и на минимум

D. на минимум

22. Связь исходной и двойственной задач заключается в том, что

A. надо решать обе задачи

B. решение одной из них получается из решения другой

C. из решения двойственной задачи нельзя получить решения исходной

D. обе имеют одинаковые решения

23. Если исходная ЗЛП имеет вид

тогда целевая функция двойственной задачи

A. имеют вид

B. имеют вид

C. имеют вид

D. имеют вид

24. Если исходная ЗЛП имеет вид

то количество переменных в двойственной задаче равно

B. 2

25. Модель транспортной задачи закрытая,

A. если

26. Цикл в транспортной задаче – это

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

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

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

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

27. Потенциалами транспортной задачи размерности (m*n) называются m+n чисел ui и vj, для которых выполняются условия

A. ui+vj=cij для занятых клеток

B. ui+vj=cij для свободных клеток

C. ui+vj=cij для первых двух столбцов распределительной таблицы

D. ui+vj=cij для первых двух строк распределительной таблицы

28. Оценками транспортной задачи размерности (m+n) называются числа

yij=cij-ui-vj, которые вычисляются

A. для занятых клеток

B. для свободных клеток

C. для первых двух строк распределительной таблицы

D. для первых двух столбцов распределительной таблицы

29. При решении транспортной задачи значение целевой функции должно от итерации к итерации

A. увеличиваться

B. увеличиваться или не меняться

C. увеличиваться на величину любой оценки

D. уменьшаться или не меняться

30. Число занятых клеток невырожденного плана транспортной задачи должно быть равно

C. m+n-1

31. Экономический смысл целевой функции транспортной задачи

A. суммарный объем перевозок

B. суммарная стоимость перевозок

C. суммарные поставки

D. суммарные потребности

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

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

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

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

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

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

вариант 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

Определение 9.3. Вектор х называется собственным вектором матрицы А , если найдется такое число λ, что выполняется равенство: Ах = λх , то есть результатом применения к х линейного преобразования, задаваемого матрицей А , является умножение этого вектора на число λ . Само число λ называетсясобственным числом матрицы А .

Подставив в формулы (9.3) x` j = λx j , получим систему уравнений для определения координат собственного вектора:

. (9.5)

Эта линейная однородная система будет иметь нетривиальное решение только в случае, если ее главный определитель равен 0 (правило Крамера). Записав это условие в виде:

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

| A - λE | = 0, (9.6)

поскольку в его левой части стоит определитель матрицы А-λЕ . Многочлен относительно λ | A - λE | называется характеристическим многочленом матрицы А.

Свойства характеристического многочлена:

1) Характеристический многочлен линейного преобразования не зависит от выбора базиса. Доказательство. (см. (9.4)), но следовательно, . Таким образом, не зависит от выбора базиса. Значит, и |A-λE | не изменяется при переходе к новому базису.

2) Если матрица А линейного преобразования является симметрической (т.е. а ij =a ji ), то все корни характеристического уравнения (9.6) – действительные числа.

Свойства собственных чисел и собственных векторов:

1) Если выбрать базис из собственных векторов х 1 , х 2 , х 3 , соответствующих собственным значениям λ 1 , λ 2 , λ 3 матрицы А , то в этом базисе линейное преобразование А имеет матрицу диагонального вида:

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

2) Если собственные значения преобразования А различны, то соответствующие им собственные векторы линейно независимы.

3) Если характеристический многочлен матрицы А имеет три различных корня, то в некотором базисе матрица А имеет диагональный вид.

Найдем собственные числа и собственные векторы матрицы Составим характеристическое уравнение: (1- λ )(5 - λ )(1 - λ ) + 6 - 9(5 - λ ) - (1 - λ ) - (1 - λ ) = 0, λ ³ - 7λ ² + 36 = 0, λ 1 = -2, λ 2 = 3, λ 3 = 6.

Найдем координаты собственных векторов, соответствующих каждому найденному значению λ. Из (9.5) следует, что если х (1) ={x 1 ,x 2 ,x 3 } – собственный вектор, соответствующий λ 1 =-2, то

- совместная, но неопределенная система. Ее решение можно записать в виде х (1) ={a ,0,-a }, где а – любое число. В частности, если потребовать, чтобы |x (1) |=1, х (1) =

Подставив в систему (9.5) λ 2 =3, получим систему для определения координат второго собственного вектора - x (2) ={y 1 ,y 2 ,y 3 }:

, откуда х (2) ={b,-b,b } или, при условии |x (2) |=1, x (2) =

Для λ 3 = 6 найдем собственный вектор x (3) ={z 1 , z 2 , z 3 }:

, x (3) ={c ,2c,c } или в нормированном варианте

х (3) = Можно заметить, что х (1) х (2) = ab – ab = 0, x (1) x (3) = ac – ac = 0, x (2) x (3) = bc - 2bc + bc = 0. Таким образом, собственные векторы этой матрицы попарно ортогональны.

Лекция 10.

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

Определение 10.1. Квадратичной формой действительных переменных х 1 , х 2 ,…,х n называется многочлен второй степени относительно этих переменных, не содержащий свободного члена и членов первой степени.

Примеры квадратичных форм:

(n = 2),

(n = 3). (10.1)

Напомним данное в прошлой лекции определение симметрической матрицы:

Определение 10.2. Квадратная матрица называется симметрической , если , то есть если равны элементы матрицы, симметричные относительно главной диагонали.

Свойства собственных чисел и собственных векторов симметрической матрицы:

1) Все собственные числа симметрической матрицы действительные.

Доказательство (для n = 2).

Пусть матрица А имеет вид: . Составим характеристическое уравнение:

(10.2) Найдем дискриминант:

Следовательно, уравнение имеет только действительные корни.

2) Собственные векторы симметрической матрицы ортогональны.

Доказательство (для n = 2).

Координаты собственных векторов и должны удовлетворять уравнениям.