2. Задача о диете

   1. Содержательное описание

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

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

2.1. Исходные параметры

– количество видов продукта

– количество контролируемых питательных веществ

– нормы потребления каждого питательного вещества (нижние границы)

– содержание i-го питательного вещества в единице j-го продукта

– цена каждого продукта

2.2. Управляемые параметры (варьируемые параметры)

– объем закупок каждого продукта

– вектор управляемых параметров (решение, план закупок или рацион)

2.3. Ограничения модели

Потребление каждого питательного вещества не должно быть ниже нормы. Пусть– содержание i-го питательного вещества в произвольном рационе .

Нужно выбрать наилучшее решение.

3. Формулировка цели принятия решений

Сформулируем критерий оптимальности. Пусть – стоимость произвольного рациона . Требуется найти рацион наименьшей стоимости

Таким образом, задача о диете ставится как задача определения такого набора управляемых параметров

,

на котором достигается наименьшее значение критерия

(4)

(5)

(6)

при условии

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

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

Найти набор управляемых параметров

,

на котором достигается наибольшее (наименьшее) значение показателя эффективности

(7)

при выполнении ограничений

(8)

(9)

(10)

и на некоторые переменные накладываются условия неотрицательности

(11)

Функция (7) называется целевой функцией или критерием оптимальности, или линейной формой.

Вектор управляемых параметров называется решением. Решение называется допустимым, если оно удовлетворяет ограничениям (8–11). Допустимое решение называется планом.

(12)

Решение называется оптимальным, если на нем достигается наибольшее значение критерия оптимальности :

– оптимальное решение, если

(13)

– оптимальное решение, если для любого

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

1.3. Различные формы задач линейного программирования

В зависимости от вида ограничений различают следующие формы задач:

• Каноническая

• Симметричная

• Общая.

Задача в канонической форме – задача ЛП, в которой все ограничения (8) – (10) есть равенства (p = q = 0) и все переменные неотрицательные (r = n).

Общий метод решения задачи ЛП разработан именно для задачи в каноническом виде.

Матричный вид задачи в канонической форме:

(14’)

(15’)

(16’)

() = (*) →

=

= – вектор коэффициентов критерия

=

= – матрица условий (технологических коэффициентов)

= ( )

= – вектор условий

= – вектор ограничений

Векторный вид задачи в канонической форме:

(14”)

(15”)

() = (*)

+ + …+ =

(16”)

,

Для неё разработан метод решения, который называется симплексным.

Задача в симметричной форме – задача ЛП, в которой все ограничения (8) - (10) есть неравенства (p = q = m) и все переменные неотрицательные (r = n).

(17)

(18)

(19)

Матричный вид задачи в симметричной форме:

С

(14’)

(15’)

(16’)

имметричная форма допускает графическое решение (иллюстрацию).

Задача в общей (смешанной) форме – задача ЛП, в которой присутствуют все виды ограничений и не все переменные неотрицательные.