Разработка модели и решение задачи линейного программирования

• 0 этап

        Составляем симплексную таблицу,  соответствующую исходной задаче :

Таблица 2

Симплекс-таблица

	x1	x2	...	xn-1	xn	b
F	-a0,1	-a0,2	...	-a0,n-1	-a0,n	-b0
xn+1	a1,1	a1,2	...	a1,n-1	a1,n	b1
xn+2	a2,1	a2,2	…	a2,n-1	a2,n	b2
…	…	…	…	…	…	…
xn+m	am,1	am,2	…	am,n-1	am,n	bm

 

• Шаг 1. Проверка на оптимальность

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

 Если в столбце  свободных членов имеются отрицательные  элементы, то выбираем среди них максимальный по модулю − он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент a_k,l − он задает ведущий столбец − l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс−таблицу согласно правилам (1).

Если среди свободных  членов есть отрицательные элементы , а в соответствующей строке нет, то условия задачи несовместны и решений у нее нет.

Если после перерасчета в столбце свободных членов остались отрицательные элементы, то переходим к первому шагу, если таких нет, то ко второму.

• Шаг 2. Проверка на неразрешимость

На предыдущем этапе  найдено допустимое решение. Проверим его на оптимальность. Если среди элементов симплексной таблицы, находившихся в строке F (не беря в расчет элемент b₀ - текущее значение целевой функции) нет отрицательных, то найдено оптимальное решение.

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

l − столбец, в котором находится этот элемент, будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответствующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.

k − строка, для которой  это отношение минимально − ведущая. Элемент a_k,l − ведущий (разрешающий). Переменная, соответствующая ведущей строке (x_k) исключается из базиса, переменная соответствующая ведущему столбцу (x_l) включается в базис. Пересчитываем симплекс − таблицу по формулам . Если в новой таблице после перерасчета в строке F остались отрицательные элементы, то переходим к шагу 2.

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

Если в строке F и  в столбце свободных членов все  элементы положи-тельные, то найдено  оптимальное решение.³

Правила преобразования симплекс-таблицы:

При составлении новой  симплекс-таблицы в ней происходят следующие изменения (1): 

• вместо базисной переменной x_k записываем x_l; вместо небазисной пе-ременной x_l записываем x_k; 

• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l ;

• все элементы ведущего столбца (кроме a_k,l) умножаются на −1/a_k,l ;

• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l ;  
• оставшиеся элементы симплекс-таблицы преобразуются по формуле (2) 

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого

базисного решения задачи;                 

2)  правило перехода  к лучшему (точнее, не худшему)  решению;

3)  критерий проверки  оптимальности найденного решения.

Геометрический (графический) метод

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

Рис. 1. Система ограничений  на плоскости

Рассмотрим задачу линейного  программирования в стандартной  форме с двумя переменными (n = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т. е. n – m = 2.

Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F=c₁x₁+c₂x₂ принимает максимальное (или минимальное) значение.

Рассмотрим так называемую линию уровня линейной функции F, т. е. линию вдоль которой эта функция принимает одно и тоже значение a, т.е. F = a, или

c₁x₁+c₂x₂ = а                                                     (3)

линии уровня широко используются, например, на картах прогноза погоды, где извилистые линии – так называемые изотермы есть ничто иное, как линии уровня температуры Т = с. Ещё более простым примером линий уровня являются параллели на географической карте. Это линии уровня широты.

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

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

Уравнение линии функции (1) есть уравнение  прямой линии. При различных уровнях а.

Линии уровня параллельны, так как  их угловые коэффициенты определяются только соотношением между коэффициентами c₁ и c₂ и следовательно, равны. Таким образом, линии уровня функции F – это своеобразные “параллели”, расположенные обычно под углом к осям координат.

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

Пусть имеются три линии уровня :

F=c₁x₁ + c₂x₂ = а₁ (I)

F=c₁x₁ + c₂x₂ = а₂ (II)

F=c₁x₁ + c₂x₂ = а₃ (III)

Причём линия II заключена между линиями I и III. Тогда а₁ < а₂ < а_{3 и} а₁ > а₂ > а_3.

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

Для определения направления  возрастания рекомендуется изобразить две линии уровня и определить, на какой них уровень больше. Например, одну из линий взять проходящей через  начало координат (если линия функция имеет вид F=c₁x₁ + c₂x₂, т. е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее найдём точку, в которой функция принимает максимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 – это точка С или А).

2. РАСЧЕТ ЗАДАЧИ  О ВЫБОРЕ ОПТИМАЛЬНЫХ ПРОЕКТОВ  ДЛЯ ФИНАНСИРОВАНИЯ

2.1. Вербальная постановка конкретной решаемой задачи

 

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

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

Таблица 3

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

Проект	Период 1	Период 2	Период 3	Период 4	Прибыль
А	8	8	10	10	21
В	7	9	9	11	18
С	5	7	9	11	16
D	9	8	7	6	17,5
Ресурс банка	22	25	38	30

 

Какие проекты следует  финансировать и какое количество наличности необходимо в течении каждого периода, если цель состоит в том, чтобы максимизировать прибыль?

2.2. Разработка экономико-математической модели задачи о выборе оптимальных проектов для финансирования

 

Построим экономико-математическую модель задачи, для этого введем необходимые обозначения:

Пусть x_i – логические переменные, равные 1, если проект принимается и равные 0, если проект не принимается. Тогда суммарная потребность в наличности в данные период будет равна сумме произведений X_i на столбец финансовых затрат по каждому проекту в данный период.

В принятых обозначениях ограничения по ресурсам примут вид:

8x₁ + 7x₂ + 5x₃ + 9x₄ ≤ 22,

8x₁ + 9x₂ + 7x₃ + 8x₄ ≤ 25,

10x₁ + 9x₂ + 9x₃ + 7x₄ ≤ 38,

10x₁ + 11x₂ + 11x₃ + 6x₄ ≤ 30,

x₁,x₂,x₃,x₄ ≥ 1,

где X(x₁,x₂,x₃,x₄) – координаты точки X в R₄ (4-мерном пространстве).

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

В этой модели целевая  функция - это математическая запись критерия оптимальности «максимум прибыли от финансирования проекта» Целевая функция равна

F(x₁,x₂,x₃,x₄) = 21x₁+18x₂+16x₃+17,5x₄ → max.

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

Тогда целевая функция – это функция ограниченности ресурсов

X(x₁,x₂,x₃,x₄) = 22x₁+25x₂+38x₃+30x₄→min,

а ограничения примут вид:

8x₁ + 8x₂ + 10x₃ + 10x₄ ≥ 21,

7x₁ + 9x₂ + 9x₃ + 11x₄ ≥ 18,

5x₁ + 7x₂ + 9x₃ + 11x₄ ≥ 16,

9x₁ + 8x₂ + 7x₃ + 6x₄ ≥ 17,5.

Какие периоды спонсор станет финансировать и в каких пределах, чтобы его вложения были минимальны?

2.3. Решение поставленной задачи симплекс-методом

 

Решим прямую задачу линейного  программирования  строчечным симплекс-методом. Определим максимальное значение целевой функции

F(X) = 21x₁+18x₂+16x₃+17,5x₄

при следующих условиях ограничений:

8x₁+7x₂+5x₃+9x₄≤22

8x₁+9x₂+7x₃+8x₄≤25

 10x₁+9x₂+9x₃+7x₄≤38