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

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

Описание алгоритма Эратосфена

1. Цель работы
Изучить алгоритм для поиска простых чисел на примере алгоритма «Решето Эратосфена»
2. Теоретический материал

Постановка задачи. Графический метод

Рассмотрим сначала несколько задач, которые привели к развитию целой отрасли математики – линейного программирования. Разумеется, в реальных задачах количество неизвестных и ограничений гораздо больше, но для понимания сути задачи и методов ее решения нам будет достаточно рассмотреть модельные ситуации с небольшим количеством неизвестных.
Пример 1 (транспортная задача)
На две товарные станции привезли по 30 комплектов мебели. Мебель необходимо развести по трем магазинам (по 20 комплектов в каждый). Известна стоимость перевозок с каждой станции в каждый магазин:

	Магазин 1	Магазин 2	Магазин 3
Станция 1	7	5	8
Станция 2	3	9	6

Требуется составить оптимальный (с наименьшими затратами) план перевозок.
Математическая постановка задачи:
Пусть х1, х2,...,х6- количество комплектов, которые надо перевезти со станций в магазины. Учитывая ограничения, получим для x_i0 систему:

Получили систему из четырех уравнений с шестью неизвестными, у которой бесконечно много решений. Среди них надо выбрать такое, на котором целевая функция: f=7х1 + 3х2 + 5х3 + 9х4 + 8х5 + 6х6 достигает минимума.

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

	Жиры	Белки	Углеводы	Цена
1-я смесь	22	15	7	7
2-я смесь	16	11	9	6

Каждая корова должна получать не меньше 200 единиц жиров, 130 единиц белков и 75 единиц углеводов. Требуется подешевле накормить коров с учетом этих данных.