Лабораторная работа № Задачи линейного программирования. Математическая модель задачи, экономический анализ. Описание алгоритма Эратосфена

Математическая постановка задачи:
Пусть надо дать корове 1-ой смеси х1 единиц, 2-ой смеси- х2 единиц. Тогда

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

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

	Сырье 1	Сырье 2	Доход
1-я продукция	15	20	70
2-я продукция	15	10	50
Запасы сырья	90	80

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

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

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

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

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

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