1. Сутність задачі лінійного програмування (злп).Сформулюйте і складіть моделі задач "раціонального використання ресурсів" і "раціону" в загальному вигляді.

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

	I1	I2	Запас ресурса
Ресурс 1	C11	C12	R1
Ресурс 2	C21	C22	R2
Ресурс 3	C31	C32	R3
Прибыль	P1	P2

Задача рационального использования ресурсов. Пусть некоторое предприятие выпускает 2 вида продукции. При их производстве используются три вида ресурсов. Данные по их расходу на выпуск одного изделия, запасы ресурсов, а также прибыль от реализации единицы продукции приведены в таблице. Требуется спланировать количество выпускаемых изделий таким образом, чтобы при данных условиях производства полученная прибыль была максимальна. Выберем в качестве параметров, характеризующих процесс планирования производства продукции, число выпускаемых изделий первого вида (переменная х1) и выпускаемых изделий второго вида (переменная х2). Выразим через выбранные неизвестные суммарную прибыль от реализации всей продукции: f (х, х₂) = P1х₁ + P2х₂ → mах.

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

I1 составит C11х1 единиц, а на выпуск всех стульев C12х2 соответственно (см. первую строку таблицы). В сумме это даст полный расход ресурса первого вида и ограничение примет вид линейного неравенства C11х1 + C12х2 ≤ R1. Аналогично запишутся ограничения по второму и третьему видам ресурсов. Далее, исходя из смысла введенных переменных, (число производимых изделий не может быть отрицательным) на них необходимо наложить ограничения неотрицательности: х1, х2 ≥ 0. Окончательно выпишем математическую модель задачи в форме ЗЛП.

f (х, х₂) = P1х₁ + P2х₂ → mах

C11х1 + C12х2 ≤ R1

C21х1 + C22х2 ≤ R2

C31х1 + C32х2 ≤ R3

х1, х2 ≥ 0

После решения поставленной ЗЛП переменные х 1 и х 2 укажут плановое количество табуреток и стульев для получения максимальной прибыли, а разность между правой и левой частями каждого неравенства даст остаток ресурса каждого вида.

Задача о составлении оптимального рациона (ЗЛП на минимизацию)

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

	Корм 1	Корм 1	Пит. в-в в рац.
Пит. в-во 1	2	1	12
Пит. в-во 2	6	4	30
Цена корма	5	2

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

Пусть х1 и х2 - содержание в данном рационе единиц корма 1-го и 2-го вида соответственно. Общую стоимость дневного рациона запишем, используя цены на корма:

f (х1, х2) = 5х1 + 2х2 → min

Ограничения имеют следующую структуру:

содержание пит. веществ в рационе ≥ min кол-во пит. в-в.

Используя для записи левой части введенные неизвестные, получим

2x1 + x2 ≥ 12

6x1 + 4x2 ≥ 30

Добавив к полученным ограничениям условия неотрицательности (xі равно нулю, если корм i не используется в рационе), окончательно запишем ЗЛП.

f (х1, х2) = 5х1 + 2х2 → min

2x1 + x2 ≥ 12

6x1 + 4x2 ≥ 30

x1 ≥ 0, х2 ≥ 0

2. Означення канонічного вигляду ЗЛП. Теореми про заміну нерівностей рівняннями. Відповідно сформульованим теоремам, перетворіть задачі "раціонального використання ресурсів" і "раціону" і надайте економічний зміст додатковим змінним і коефіцієнтам цільової функції при них.

ЗЛП называется заданной в каноническом виде, если её система основних ограничений представлена уравнениями. Каноническая форма записи злп:

max f(x) = ΣCjXj (j = 1,n)

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

Σ AijXj = Bi, i=1,m j=1,n

Xj ≥0, Bi ≥ 0 i=1,m j=1,n.

Произвольно заданную злп нужно привести к каноническому виду. Каноническая форма систему функциональных ограничений (СФО) имеет в виде равенств. Покажем, как осуществляется эта процедура. Пусть исходное ФО имеет вид: A11X1+A12X2+…+A1nXn≤B1. Приведение к каноническому виду осуществляется введением в левую часть соответств.ограничения k-той дополнительной переменной: Ak1x1+Ak2X2+…+AknXn+Xn+k=Bk.

При этом, если СФО содержит изначально знак «≤», то все Xn+k берутся со знаком «+», и наоборот. Все введенные таким образом переменные называются балансовыми. Каноническая форма предполагает неотрицательность всех входящих в задачу переменных. Если исходная задача имеет знак экстремумов противоположный знаку целевой функции, то изменение экстремума достигается изменением знака в целевой функции. Если каноническая форма злп предполагает поиск максимума f(x), а исходная задача сформулирована на поиск минимума, то для изменения экстремума нужно искать max (-f(x)) или в обратном случае min (-f(x)). У задачі використання ресурсів додаткові змінні – залишки відповідних видів ресурсів. Оскільки в цільовій функції коеф-ти при змінних описують питомий прибуток від реалізації виробів, а залишки ресурсів прибутку не дають, до цільової функції додаткові змінні мають входити з нульовими коеф-ми. У разі "раціону" додаткові змінні відображують перевищення кількості відповідної поживної речовини над нормою. Оскільки вартість поживних речовин відображена у вартості кормів, до цільової функції додаткові змінні входять з нульовими коеф-ми.