§1.1Общая постановка задачи линейного программирования. Классические задачи.

Общая задача линейного программирования формулируется следующим образом.

Даны система m линейных уравнений и неравенств с n переменными

и линейная функция .

Необходимо найти такое решение системы , где (j=1,2,…,l, l), при котором линейная функция F принимает оптимальное значение (т.е. максимальное или минимальное).

Записанная выше система называется системой ограничений, а функция F – линейной функцией, линейной формой, целевой функций или функцией цели.

Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение системы ограничений, удовлетворяющее условию неотрицательности переменных, при котором линейная функция F принимает оптимальное значение.

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

, (j=1,2,…,l, l)

и линейная функция F .

Она отличается от других задач тем, что ее система ограничений является системой уравнений и все переменные неотрицательные.

При необходимости перехода от неравенства к уравнению вводятся дополнительные переменные. Неравенство заменяется уравнением и условием неотрицательности дополнительной переменной , а неравенство - уравнением  . Дополнительные переменные вводят в целевую функцию с коэффициентом, равным нулю.

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

Модельюбудем называть условный образ какого-либо объекта, приближенно воссоздающий этот объект с помощью некоторого языка. В экономико-математических моделях таким объектом является экономический процесс, а  языком – классические и специально разработанные математические методы.

Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта, которое выражает закономерности экономического процесса в абстрактном виде с помощью математических соотношений.

Для составления модели задачи линейного программирования, заданной в текстовой форме, необходимо:

1. ввести обозначение для неизвестных задачи
2. проанализировать ограничения для них (например, неотрицательность)
3. составить систему ограничений
4. составить целевую функцию и установить вид экстремума.

Этапы экономико-математического моделирования:

1. Постановка цели и задачи исследования.
   Качественное описание объекта в виде экономической модели.
2. Формирование математической модели, изучаемого объекта. Выбор или разработка методов исследования.
3. Анализ математической модели и полученных результатов.

Построение математических моделей простейших экономических задач.

1. Задача об использовании ресурсов (задача планирования производства)

Для изготовления двух видов продукции и используют четыре вида ресурсов, , и  . Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице.

Прибыль, получаемая от единицы продукции и – соответственно 2 и 3 руб.

Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.

Решение.

Составим экономико-математическую модель.

Пусть и – число единиц продукции соответственно изапланированных к производству. Для их изготовления потребуется единиц ресурса , 2 единиц ресурса , , единиц ресурса и единиц ресурса  .

Так как потребление ресурсов , и  не должно превышать их запасов, соответственно 18,16,5 и 21 ед., то связь между потреблением ресурсов и их запасами выразится системой неравенств

По смыслу задачи переменные , .

Суммарная прибыль F составит руб. от реализации продукции и – от реализации продукции , т.е. .

Экономико-математическая модель задачи: найти такой план выпуска продукции , удовлетворяющий записанной системе неравенств при котором функция F принимает максимальное значение.

2. Задача составления рациона (задача о диете, задача о смесях).

Имеется два вида корма I и II, содержащих питательные вещества (витамины) , . Содержание числа единиц питательных веществ в 1 кг каждого вида корма необходимы минимум питательных веществ приведены в таблице.

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб.

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных веществ было бы не менее установленного предела.

Решение.

Составим экономико-математическую модель.

Пусть и – количество кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать 3 единиц питательного вещества , единиц питательного вещества , , единиц питательного вещества . Так как содержание питательных веществ , в рационе должно быть не менее соответственно 9, 8, и 12 единиц, то получим систему неравенств:

При этом переменные , .

Общая стоимость рациона F .

Экономико-математическая модель: составить дневной рацион , удовлетворяющий записанной выше системе с условием , , при котором функция принимает минимальное значение.