Раздел II. Линейное программирование.

1. Математические модели задач линейного программирования.

Рассмотрим детерминированные линейные задачи, в которых показатель эффективности W=W(, x) линейно зависит от заданных условий  и элементов решения x=(x₁ , x₂ , …, x_n).

Такие задачи составляют группу задач линейного программирования.

Задача о пищевом рационе.

Каждому человеку для нормальной жизнедеятельности необходимо определенное количество белков (b₁), жиров (b₂), углеводов (b₃) и витаминов (b₄). Рассмотрим N видов продуктов.

	Продукт	Белки	Жиры	Углеводы	Витамины	Цена
1	П1	а11	а12	а13	а14	с1
2	П2	а21	а22	а23	а24	с2
N	ПN	аN1	аN2	аN3	аN4	сN

Математическая модель.

ДАНО: x_i – количество единиц i-продукта.

Суммарная стоимость продуктов – показатель эффективности.

НАЙТИ решение Х= (x₁ , x₂ ,… , x_N ), которое удовлетворяет следующей системе неравенств:

и обращает в минимум показатель эффективности

ПРИМЕР 2.1.

Имеется 5 видов продуктов питания заданной калорийности. Необходимо составить рацион на неделю с максимальным количеством калорий, уложившись в сумму 1000 руб. Количество каждого продукта не должно превышать заданной нормы.

Показатели	Номер вида продукта
	1	2	3	4	5
Относительная калорийность на 1 кг продукта	10	10	15	30	20
Цена 1 кг продукта, руб.	5	10	15	20	30
Норма потребления продукта, кг	10	15	20	10	15

Математическая модель.

x_i – количество продуктов i-ого вида

x₁ ≤ 10

x₂ ≤ 15

x₃ ≤ 20

x₄ ≤ 10

x₅ ≤ 15

5x₁ + 10x₂ + 15x₃ + 20x₄ + 30x₅≤1000

W = 10x₁ + 10x₂ + 15x₃ + 30x₄ + 20x₅ →max

Задача производственного планирования.

Пусть имеется некоторый экономический объект (предприятие, бригада, АОО), который может производить продукцию n видов. В процессе производства допустимо использование m видов ресурсов. На производство единицы продукции j-го вида ресурсов i-го вида требуется в количестве а_ij. Технологию предприятия можно представить как прямоугольную матрицу m на n. Если план производства представить в виде вектора х=(х₁, х₂, …, х_n), тогда общие затраты ресурса i-го вида будут равны . Всякая реальная система имеет ограничения на ресурсы. Представим их в виде вектора b=(b₁, b₂, …, b_m). В математической форме по правилам матричной алгебры система условий будет иметь вид: Ах≤b. По каждому виду изделия объем не должен превышать спрос v=(v₁, v₂, …, v_n): x≤.v Также необходимо добавить ограничения на неотрицательность элементов решения: х ≥ 0.

Обозначим за с_j цену единицы продукции j–го вида. Тогда в качестве целевой функции можно выбрать функцию f(x)= = cx. Ее необходимо максимизировать.

ПРИМЕР 2.2.

Ткацкая фабрика лилипутов выпускает 2 вида ткани. Изучение спроса показало, что ежедневно необходимо выпускать не меньше 8м ткани. Суточный расход сырья не должен превышать 10ед. Установить план выпуска ткани с максимальной прибылью, при условии полного удовлетворения спроса.

Показатели	Вид ткани
	1	2
Сырьё, ед/м	1	2
Доход, у.е./м	1	1

Математическая модель:

х _i – количество ткани i-го вида (м)

х_i 0

L= х₁+х₂max