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

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

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

1. Цель, поставленную в задаче, выразить в виде зависимости от искомых величин. Полученное выражение называют функцией цели (целевой функцией).

2. Записать условия, которые накладываются на искомые величины. Чаще всего – это системы уравнений или неравенств. Их называют системой ограничений.

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

где c_j, d_j, b_j, a_ij – некоторые постоянные числа.

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

Как и в случае основной задачи линейного программирования, своё максимальное значение целевая функция задачи (1.1)-(1.3) принимает в одной из вершин многогранника решений, определяемого системой ограничений (1.2)-(1.3) (естественно при условии, что эта задача имеет оптимальный план). Это сходство с линейным программированием позволяет решать дробно-линейные задачи методом Штифеля.

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

Вычисления оформляются в виде жордановых таблиц. При этом для функционала отводятся две нижние строки: в первую из них записываем коэффициенты числителя, а во вторую – знаменателя. Исходной задаче соответствует таблица 1:

Табл. 1.

Через y_i обозначаются разности между правыми и левыми частями системы ограничений:

y_i = a_i – a_i1x₁ – a_i2x₂ – a_i3x₃ – … – a_inx_n ³ 0.

Свободными переменными мы будем называть переменные, расположенные в верхней заглавной строке жордановой таблицы. Приравнивая к нулю свободные переменные, мы получим исходное базисное решение: Данный вектор не может являться опорным планом, т.к. знаменатель целевого функционала на нем равен нулю ( ). Поэтому среди свободных членов системы ограничений a₁,…, a_m обязательно есть отрицательные числа (иначе базисное решение было бы опорным планом).

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

Табл. 2.

В таблице 2 все свободные члены b_i неотрицательны, что обеспечивает неотрицательность базисных переменных x₁, …, y_m. Кроме того (в силу положительности знаменателя целевой функции L₂ на множестве опорных планов). Первоначальным опорным планом является вектор с координатами Значение целевой функции на первоначальном опорном плане равно

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

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

Предположим, что исходная задача дробно-линейного программирования являлась задачей на максимум. Если все определители , вычисленные по таблице 2, неотрицательны, то оптимальным является опорный план X⁰ и .

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

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

Метод Штифеля позволяет находить не только максимум, но и асимптотический максимум задачи дробно-линейного программирования. Рассмотрим более подробно переход от плана X⁰ к плану X¹. Выбирая разрешающий элемент в j-м столбце, мы должны руководствоваться принципом минимального симплексного отношения. Т.е. разрешающий элемент в j-м столбце должен попасть в ту строку, для которой симплексное отношение положительно и минимально.

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

Однако, если на одном из шагов некоторая оценка меньше нуля, и при этом все элементы j-го столбца . Тогда в данном столбце, руководствуясь принципом минимального симплексного отношения, разрешающий элемент выбирать нельзя. Увеличивая значения свободной переменной x_j от 0 и до (см. Табл. 2), мы все время остаемся в области планов. Это связано с тем, что увеличение переменной x_j не вызывает изменения знака на минус ни у одной из базисных переменных.

Обозначим через М предел, к которому, монотонно возрастая, стремится целевая функция при : . Это число является асимптотическим максимумом.

Пример1.1. Найти максимум функционала:

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

 

Решение. Составим жорданову таблицу:

	-x1	-x2
y1	-4		-1
y2		-3
y3		-1	-2
y4	-1		-1
z1	-2	-5
z2	-3	-2

Табл. 1.5.

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

	-y4	-x2
y1	-4
y2		-3
y3		-1	-2
x1	-1
z1	-2	-5
z2	-3	-2

Табл. 1

Продолжаем искать опорный план. За разрешающий элемент берем -1.

	-y4	-y3
y1	-4
y2		-3
x2		-1
x1	-1
z1	-2	-5
z2	-3	-2
dj		-11	12/7

	-y4	-y1
y3	-4
y2	-10
x2	-4
x1	-1
z1	-22
z2	-11
dj	-11		17/9

Табл. 2

Табл. 3

Получили что один из определителей равен -11, а в столбце -y₄ все переменные отрицательные, т.е. получили асимптотический максимум.

Определим угловой коэффициент, обозначим y₄=M. Выпишем x₁,x₂:

Угловой коэффициент

Для того, чтобы определить, какой у нас максимум, конечный или бесконечный, определим к чему стремится z.

Получили конечный максимум.