Тема 1 . Задачи математического программирования

Цель работы:

• изучить основные понятия линейного программирования;

• освоить графический метод решения простейших задач линейного программирования;

• научиться использовать сим­плексный метод с искусственным базисомна примере задачи о диете.

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

1.1. Основные формулы и определения

В каноническом виде задача линейного программирования (ЛП) формулируется следующим образом.

Найти такой набор , который является решением системы

(1.1)

удовлетворяет соотношению

(1.2)

и обеспечивает максимум (минимум) линейной функции

(1.3)

Соотношения (1.1) принято называть фазовыми ограничениями, соотношения (1.2) –естественными ограничениями.

Функцию Fпринято называтьцелевойфункцией.

Система ограничений всегда может быть приведена к каноническому виду.

Если ограничения заданы неравенствами, то их можно преобразовать в равенства путем введения новых неотрицательных переменных, так называемых балансовых(выравнивающих)ресурсов.

Так, например, в неравенстве достаточно добавить к левой части некоторую величинуx_n+1³0и получится равенство:.

Чтобы балансовые переменные не влияли на искомый оптимум, их вводят в целевую функцию (1.1) с нулевыми коэффициентами.

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

Задачу ЛП, определяемую соотношениями (1.1)-(1.3), можно записать в матричном виде:

,

,

,

где , , ,

.

В дальнейшем при анализе задачи также используется расширенная матрица системы (1.1) , которая составляется из матрицыАи вектораВ.

Пример 1. Задача о диете.

Составить задачу ЛП, позволяющую оптимизировать расход кормов, и привести ее к каноническому виду.

Для откорма животных употребляют два вида кормов; стоимость 1 кг корма I вида - 5 у.е., а корма - II вида 2 у.е. В каждом килограмме корма I вида содержится 5 ед. питательного вещества  А, 2.5 ед. питательного веществаBи 1 ед. питательного веществаC. В каждом килограмме корма II вида содержится соответственно 3, 3 и 1.3 ед. Суточный рацион предусматривает питательных единицAне менее 225 ед., типаB- не менее 150 ед. и типаC- не менее 80 ед. Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы затраты были минимальны?

Решение

Построим математическую модель данной задачи. Обозначим через x₁иx₂количество кормов I и II вида соответственно. Тогда суммарная стоимость кормов будет равна 5x₁+2 x₂. Поэтому целевая функция будет иметь вид:

(1.4)

Ограничения по содержанию питательных веществ в рационе будут иметь вид:

	(1.5)
	(1.6)

Соотношения (1.4)-(1.6) корректно определяют задачу ЛП, но предложенная форма записи не является канонической. Для приведения задачи к этой форме домножим ЦФ (1.4) на –1, в результате получим новую ЦФ (1.7). Для преобразования фазовых ограничений (1.5) к канонической форме введем положительные балансовые переменные x₃,x₄иx₅. Тогда фазовые ограничения примут вид (1.8), а естественные - вид (1.9).

(1.7)

	(1.8)
	(1.9)

Соотношения (1.7) – (1.9) определяют задачу ЛП в канонической форме.