Графический способ решения ЗЛП

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

(2.11)
(2.12)
(2.13)

Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений (2.12), (2.13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (2.11) — (2.13) есть выпуклое множество.
Перейдем к геометрической интерпретации целевой функции. Пусть область допустимых решений ЗЛП — непустое множество, например многоугольник .

Выберем произвольное значение целевой функции . Получим . Это уравнение прямой линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (2.11) F параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).
Найдём частные производные целевой функции по и :

(2.14)
. (2.15)

Частная производная (2.14) (так же как и (2.15)) функции показывает скорость ее возрастания вдоль данной оси.Следовательно, и — скорости возрастания F соответственно вдоль осей и .Вектор =( называется градиентом функции.Он показывает направление наискорейшего возрастания целевой функции:

(2.16)

Вектор указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор =( перпендикулярен к прямым семейства .
Из геометрической интерпретации элементов ЗЛП вытекает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область допустимых решений .

2. Строим вектор =( наискорейшего возрастания целевой функции — вектор градиентного направления.

3. Проводим произвольную линию уровня .

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

5. Определяем оптимальный план и экстремальное значение целевой функции .

2.3. Симплексный метод решение ЗЛП

Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит:

1) умение находить начальный опорный план;

2) наличие признака оптимальности опорного плана;

Пусть ЗЛП представлена системой ограничений в каноническом виде:
, .
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательной правой части левая часть ограничений содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения равенства - с коэффициентом, равным нулю.
Пусть система ограничений имеет вид
,
Сведем задачу к каноническому виду. Для этого прибавим к левым частям неравенств дополнительные переменные (. Получим систему, эквивалентную исходной:

,

Которая имеет предпочтительный вид

).

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

Сведём её к эквивалентной вычитанием дополнительных переменных ( из левых частей неравенств системы. Получим систему

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

) , (2.17)
(2.18)
, (2.19)

причём ни одно из ограничений не имеет предпочтительной переменной. М-задача запишется так:

) (2.20)
( (2.21)
, (2.22)

Задача (2.20) - (2.22) имеет предпочтительный план. Её начальный опорный план имеет вид:

).

Если некоторые из уравнений (2.18) имеют предпочтительный вид, то в них не следует вводить искусственные переменные.

Теорема. Если в оптимальном плане

) (2.23)

М-задачи (2.20) - (2.22) все искусственные переменные , то план является оптимальным планом исходной задачи(2.17)-(2.19).
Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М - задачу, которая имеет начальный опорный план
).
Решение исходной задачи симплексным методом путем введения искусственных переменных называется симплексным методом с искусственным базисом.
Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в котором все искусственные переменные , то его первые n-компоненты дают оптимальный план исходной задачи.

 

Задача о смесях(о диете)

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

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

2. Задан набор продуктов, из которых требуется составить пищевой рацион;

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

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

Формализуем описанную ситуацию:

Будем считать, что в рацион должно входить m биологически необходимых питательных веществ (индекс i). Таким образом, i=1,2,..,m.

Известно, что i -го питательного вещества в рационе должно быть не меньше, чем b_i единиц. Предположим, что мы располагаем n различными продуктами, из которых составляется пищевой рацион (индекс j, j=1,2,…,n). Норму содержания i -го питательного вещества в j -ом продукте обозначим через a_ij. Нам известна таблица-матрица, состоящая из m×n чисел a_{ij .}

Таблица 2.1

Пищевые продукты
		…	…	…	n
Питательные вещества				…
			…
…	…	…	…	…
…	…	…	…	…
m			…

 

Цены, которые установлены на продукты питания, обозначим c_j за единицу j -го продукта. Количество j -го продукта, входящего в пищевой рацион, обозначим через x_j.

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

Найти вектор X = (x₁, x_2, …, x_n), удовлетворяющий системе ограничений:

( (2.24)
(2.25)

и доставляющий целевой функции минимальное значение.

Ограничение для каждого i означает, что в выбираемом рационе i -го питательного вещества должно содержать не менее, чем b_i единиц. Второе ограничение формализует тот факт, что j -ый продукт может либо входить в рацион, и тогда x_i >0, либо не входить, и тогда x_i =0.