Примеры задач линейного программирования

Задача 1. Использование сырья. Предприятие может выпускать два вида продукции . На их изготовление расходуется три вида сырья . Запасы сырья, нормы их расхода на единицу изделия, себестоимость С и оптовые цены приведены в таблице:

Требуется составить план выпуска продукции, обеспечивающий получение максимальной прибыли.

Построим математическую модель: обозначим X₁ и X₂ - количество выпускаемой продукции Р₁ и Р₂. На изготовление изделий P₁, Р₂ будет израсходовано 10X₁ + 20X₂ единиц сырья S₁. По условию имеем: .

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

В результате реализации единицы изделия Р₁ предприятие получит прибыль (7-5)=2 усл. ед.; единицы изделия Р₂ - прибыль (13-10) = 3 усл. ед. Общая прибыль составит: .

Итак, задача свелась к нахождению неотрицательных чисел X₁ и X₂, удовлетворяющих линейным ограничениям и обращающих в максимум линейную целевую функцию .

Задача 2. Задача о диете. Пусть имеется два вида продуктов , в которые входят три вида питательных веществ, например белки, жиры и углеводы . Содержание количества единиц питательных веществ в 1 кг каждого вида продукта, норма содержания питательных веществ в дневном рационе и стоимость 1 кг продукта представлены в таблице:

Требуется составить такой рацион питания, при котором затраты на приобретение продуктов будут минимальными. Построим математическую модель: обозначим X₁ и X₂ - суточное потребление продуктов Р₁ и Р₂,тогда стоимость рациона определяется из следующих условий:

Задача свелась к нахождению неотрицательных чисел X₁, X₂, удовлетворяющих линейным ограничениям и доставляющих минимум линейной целевой функции .

Задача 3. Транспортная задача. В двух пунктах отправления сосредоточен однородный груз в количестве 5т и 15 т. Груз необходимо доставить трем потребителям, потребности которых одинаковы: 1-й потребитель - 6 т, 2-й потребитель - 10 т, 3- й потребитель - 4 т. Известны также затраты на перевозку единицы груза из i-гo пункта отправления в каждый j-й пункт потребления:

Требуется составить такой план перевозок груза, при котором общая стоимость перевозок была бы минимальной. Математическая модель: обозначим Xij - объем перевозок груза из i-гo пункта отправления в j-й пункт потребления (i = 1,2; j = 1,2,3). Тогда получим:

при ограничениях

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