- •Введение
- •Глава 1. ОСновные понятия теории множеств, комплексных чисел и алгебры многочленов
- •1. Элементы теории множеств и комплексных чисел
- •1.1. Понятие множества. Операции над множествами
- •1.2. Числовые множества и их свойства.
- •2. Алгебра многочленов.
- •Глава 2. Матрицы. Определители
- •1. Алгебра матриц.
- •Виды матриц.
- •2. Определитель n-го порядка.
- •2.1. Определение. Вычисление определителей 2 и 3-го порядков.
- •2.2.Миноры и алгебраические дополнения.
- •2.3.Свойства определителя n-го порядка.
- •3. Действия над матрицами.
- •3.1. Линейные операции над матрицами.
- •3.2. Умножение матриц.
- •3.3. Многочлены от матриц.
- •3.4. Обратная матрица.
- •Вычисление обратной матрицы (через алгебраические дополнения).
- •3.5. Линейная зависимость строк и столбцов матрицы.
- •3.6. Ранг матрицы. Базисный минор.
- •3.7 Нахождение ранга матрицы
- •Вопросы для повторения.
- •Глава 3. Системы линейных уравнений и методы их решения.
- •1. Основные понятия и определения
- •2. Условия совместности системы линейных уравнений
- •3. Метод обратной матрицы
- •4. Правило Крамера
- •5. Метод Гаусса исключения неизвестных
- •7. Метод полного исключения
- •7.1. Решение систем линейных уравнений
- •7.2. Вычисление обратной матрицы методом полного исключения.
- •7.3. Вычисление ранга матрицы методом полного исключения
- •Линейное пространство.
- •8. Собственные значения и собственные векторы матриц
- •9. Квадратичные формы
- •10. Численные методы решения систем линейных уравнений
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Глава 4. Векторная алгебра
- •Векторное произведение двух векторов.
- •Вопросы для повторения.
- •Глава 5. Задачи линейного программирования
- •1. Постановка задачи линейного программирования (злп)
- •2. Графический метод решения злп
- •3. Симплекс – метод решения злп
- •4. Двойственные злп
- •Методы определения опорного плана тз.
- •Вопросы для повторения.
- •Глава 6. Балансовые модели
- •1. Экономико-математическая модель (эмм) межотраслевого стоимостного баланса (модель Леонтьева)
- •Модель международной торговли
- •Вопросы для повторения.
- •Задачи для самостоятельного решения.
- •Библиографический список
- •Глава 1. ОСновные понятия теории множеств, комплексных чисел и алгебры многочленов 4
- •Глава 2. Матрицы. Определители 17
- •Глава 3. Системы линейных уравнений и методы их решения. 52
- •Глава 4. Векторная алгебра 103
- •Глава 5. Задачи линейного программирования 118
- •Глава 6. Балансовые модели 153
- •394026 Воронеж, Московский просп., 14
2. Графический метод решения злп
Если число переменных в ЗЛП равно 2, а ограничениями является система неравенств, то задачу можно решать графическим методом. Он применим для решения ЗЛП следующего вида:
(3)
(4)
Алгоритм решения ЗЛП графическим методом.
Записывают уравнения прямых, соответствующих ограничениям (4) и строят их на плоскости X1OX2.
Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости X1OX2 и подставляют ее координаты в левую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; иначе искомая полуплоскость находится с противоположной стороны от прямой.
Эти действия выполняются последовательно для всех неравенств (4).
Определяют ОДР задачи (многоугольник решений) как область пересечения m полуплоскостей, соответствующих m ограничениям задачи.
Определяют направление возрастания (убывания) целевой функции F. Для этого строят вектор-нормаль градиента целевой функции: =grad F= =(c1;c2), его направление показывает направление возрастания функции F, в противоположном направлении функция убывает.
Определяют граничную точку (точки) ОДР, в которых целевая функция принимает максимальное или минимальное значение.
Для этого строят линию уровня целевой функции и передвигают ее в направлении вектора =(c1;c2) до тех пор, пока она не пройдет через последнюю её общую точку с многоугольником решений.
Вычисляют значения координат найденной точки, решая совместно уравнения, задающие прямые, на пересечении которых находится эта точка, или, выявляя уравнение граничной прямой ОДР, с которой совпадает линия уровня целевой функции.
Возможны следующие варианты ОДР: замкнутое множество, открытое множество, пустое множество (система ограничений несовместна), единственная точка. Пересечение линии уровня целевой функции может состоять из одной точки или целого отрезка. Максимальным (минимальным) значением целевой функции может быть как конечное число, так и бесконечность.
Пример. Фирма выпускает 2 вида мороженого: сливочное и шоколадное. Для изготовления мороженого используются 2 исходных продукта: молоко и наполнители, расходы которых на 1 кг мороженого и суточные запасы приведены в таблице.
Исходный продукт |
Расход исходных продуктов на 1 кг мороженого |
Запас, кг |
|
сливочное |
шоколадное |
||
Молоко
|
0,8 |
0,5 |
400 |
Наполнители |
0,4 |
0,8 |
365 |
Изучение рынка сбыта показало, что суточный спрос на сливочное мороженое превышает спрос на шоколадное не более, чем на 100 кг. Кроме того, установлено, что спрос на шоколадное мороженое не превышает 350 кг в сутки. Розничная цена 1 кг сливочного мороженого 16 д. е., шоколадного-14 д. е.
Какое количество мороженого каждого вида должна производить фирма, чтобы доход от реализации продукции был максимальным?
Решение. Обозначим: x – суточный объем выпуска сливочного мороженого, кг; x – суточный объем выпуска шоколадного мороженого, кг. Составим математическую модель задачи.
Целевая функция будет иметь вид:
F=16x +14x max. (5)
Система ограничений:
(6)
Построим в плоскости X1OX2 область допустимых решений, то есть решение системы ограничений (6) (см. рис.20). Для этого, заметим, что каждое неравенство системы ограничений определяет в плоскости X1OX2 полуплоскость, лежащую выше или ниже прямой, определяемой соответствующим уравнением.
Построим прямые: 0,8x +0,5x =400, 0,4x +0,8x =365, x -x =100, x =350, x =0, x =0. Точки пересечения этих прямых обозначим A, B, C, D, E.
Рис.20. Решение задачи линейного программирования
Рассмотрим первое неравенство системы ограничений (6). Чтобы построить его решение, возьмём, например, точку с координатами x =0, x =0. Подставив их в неравенство, получаем 0 400 – верно, следовательно, искомая полуплоскость (решение) лежит ниже прямой 0,8x +0,5x =400, остальные полуплоскости находятся аналогичным образом. В результате пересечения всех этих областей получаем область OABCDE - ОДР задачи. Для нахождения максимального значения целевой функции F проверим граничные точки из области решений.
Построим линию уровня F целевой функции F: . Переместим её в направлении вектора-нормали =(16;14) градиента целевой функции параллельно самой себе, пока хотя бы одна её точка будет принадлежать ОДР. По рисунку видно, что точкой выхода из ОДР является точка С. Её координаты определяются из системы:
Решая её, найдем координаты точки С: x =312,5 и x =300. В точке С и будет оптимальное решение X*=(312,5; 300). При этом F =16∙312,5+14∙300=9200(д. е.).
Таким образом, фирма должна выпускать в сутки 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого, при этом доход от реализации составит 9200 д.е.