Курсовая
Информатика
Математика
Живопись
Физика
Сопромат
Интеграл
Практика

Аварии

Энергетика
Типовик
Черчение
Реактор
БРЕСТ-2400
Электротехника
Дифуры

Решение алгебраических и трансцендентных уравнений

Пример 3 (распределение ресурсов)

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

 

Сырье 1

Сырье 2

Доход

1-я продукция

15

20

70

2-я продукция

15

10

50

Запасы сырья

90

80

 

Требуется получить максимальную прибыль.

Математическая постановка задачи:

Обозначим через х1 и х2 планируемый выпуск первой и второй продукции. Тогда система ограничений будет иметь вид:

Среди решений данной системы требуется найти такое, на котором достигается максимум целевой функции f=70x1+50x2.

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

Задача линейного программирования в общем виде:

Дана система ограничений: АХ £ В, X ³ 0, где А - матрица, Х и В - столбцы (возможно, разной длины). Дана линейная целевая функция: f = (с, х). Требуется определить компоненты вектора X, удовлетворяющие системе ограничений, при которых данная целевая функция принимает минимальное значение.

Определения. Решение называется допустимым в задаче линейного программирования, если оно удовлетворяет условиям: АХ £ В, Х ³ 0.

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

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

Если существует оптимальное решение, то говорят, что задача поставлена корректно.

Если в примере 2 умножить систему ограничений на -1, то вместо системы ограничений АХ ³ В получим АХ £ В, т.е. получим задачу в общем виде.

В примере 1 вместо АХ £ В имеем АХ = В. Это частный случай.

В примере 3 вместо f = 70х1 + 50х2 -> max ищем f1 = -70х1 - 50х2 -> min.

(но не надо забывать в ответе поменять знак!)

Любую задачу линейного программирования можно свести к КАНОНИЧЕСКОМУ ВИДУ:

АХ = В, Х³ 0, f = (с, х) -> min.

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

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

Например, задачу 3 можно так свести к канонической форме:

 

f = 70х1 + 50х2 -> max f1 = -70х1 - 50х2 -> min

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

 и f = 7х1 + 6х2 -> min


Ядерная физика

Машиностроительное черчение
Инженерная графика
Лабораторное занятие 
Электротехника