Задачи динамического программирования

Нижегородский институт менеджмента и бизнеса. Богомолова Е. С.

Содержание

Задание 1

Постановка  задачи 

Предприятие выпускает  два вида продукции, используя три  вида ресурсов. Принятые обозначения: А – матрица норм затрат ресурсов, В – запасы ресурсов в планируемый  период, С – прибыль на единицу продукции.

А = ; В = ; С =

С помощью данных, приведенных  в таблице, требуется:

1) Составить экономико-математическую  модель задачи;

2) Определить план  выпуска изделий, обеспечивающий получение максимальной прибыли;

3) Составить двойственную  задачу, найти оптимальное решение  и оптимум двойственной задачи  с помощью теорем двойственности; указать дефицитные для предприятия  ресурсы;

4) провести решение  графическим методом и рассмотреть, к чему приведет изменение запасов ресурсов;

5) провести решение симплекс-методом и рассмотреть экономическую интерпретацию последней симплекс-таблицы.

Решение

Экономико-математическая модель задачи линейного программирования имеет следующий вид:

= 4x₁ + x₂ → max;

8x1 + 2x2 ≤ 80,  3x1 + 3x2 ≤ 60,  x1 + 4x2 ≤ 40;
x1 ≥ 0,   x2 ≥ 0.

где х₁ – план выпуска первого изделия, х₂ – план выпуска второго изделия.

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

Каждое неравенство определяет некоторую полуплоскость. Соответствующие области для каждого ограничения отмечены штрихами. Пересечение D данных полуплоскостей (т. е. множество точек, которые одновременно принадлежат каждой их них) является областью допустимых планов задачи. Поведение целевой функции f(x) = 4х₁+ х₂ в рамках двумерной иллюстрации может быть охарактеризовано с помощью линий уровня.

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

 

 

 

 

Если линия уровня определяется уравнением f (x) = c_lx_l+c₂x₂= const , то этот вектор имеет вид

                            

и указывает направление  возрастания функции. Таким образом, с геометрической точки зрения задача максимизации сводится к определению такой точки области D, через которую проходит линия уровня, соответствующая наибольшему из возможных значений. Последнее означает, что для нахождения точки экстремума в задаче линейного программирования мы должны сначала построить линию уровня для некоторого произвольного значения целевой функции. Затем необходимо осуществлять ее параллельное передвижение (так, чтобы она оставалась перпендикулярной вектору с) до тех пор, пока не достигнем такой точки области допустимых планов D, из которой смещение в направлении вектора с было бы невозможно. Такой точкой будет являться точка пересечения прямых 8x₁ + 2x₂ = 80 и х₂ = 0. Найдем координаты этой точки.

x₂ = 0

x₁ = 80/8 = 10

Таким образом, оптимальным планом выпуска изделий будет являться план: X^*(10;0), а максимальная прибыль будет равна = 40 = max

Решим задачу симплекс-методом.

С точки зрения обеспечения рациональности и наглядности вычислительного процесса выполнение алгоритма симплекс-метода удобно оформлять в виде последовательности таблиц.

Шаг 1. Приведем задачу к  канонической форме. Для реализации шага в ограничения задачи вводятся дополнительные переменные.

= 4x₁ + x₂ + 0·x₃ + 0·x₄ +  0·x₅ → max;

8x1 + 2x2 + x3 = 80,  3x1 + 3x2 + x4 = 60,  x1 + 4x2 + x5 = 40;
x1 ≥ 0,   x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0

Шаг 2. Исходная симплекс-таблица  соответствует первоначальному  допустимому базисному решению. В качестве такового проще всего взять базисное решение, в котором основными являются дополнительные переменные x₃, x₄, x_5.

В левом столбце записываются основные (базисные) переменные, в первой строке таблицы перечисляются все  переменные задачи. Крайний правый столбец содержит свободные члены системы ограничений b₁, b₂, ..., b_m. В последней строке таблицы (она называется оценочной) записываются коэффициенты целевой функции, а также значение целевой функции (с обратным знаком) при текущем базисном решении ( ). В рабочую область таблицы (начиная со второго столбца и второй строки) занесены коэффициенты a_ij при переменных системы ограничений.

Таблица 1 - Исходная симплекс-таблица

базис	переменные					bi
	x1	x2	x3	x4	x5
x3	8	2	1	0	0	80
x4	3	3	0	1	0	60
x5	1	4	0	0	1	40
cj	4	1	0	0	0	0

Таким образом, в данном базисном решении неосновные переменные x₁ и x₂ равны нулю. Базисные переменные отличны от нуля: x₃ = 80, x₄ = 60, x₅ = 40. Данное базисное решение является допустимым. Естественно, что значение целевой функции в этом случае равно нулю, так как в формировании целевой функции участвуют переменные, которые для данного базисного решения являются неосновными.

Шаг 3.  Проверка условия: все c_j ≤ 0. Если НЕТ - осуществляется переход к шагу 4, если ДА - задача решена. Таким образом, на данном шаге проверяется наличие положительных элементов в последней строке симплексной таблицы. Если такие элементы имеются, необходимо продолжать решение.

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

Шаг 4. Выбор разрешающего столбца (переменной, вводимой в базис). Разрешающий столбец выбирается в соответствии со следующим условием:

где r - номер разрешающего столбца.

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

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

Шаг 5. Проверка условия: все a_ir ≤ 0. Если ДА - целевая функция неограниченна и решения нет, если НЕТ - переход к шагу 6.

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

В нашем примере все  элементы разрешающего столбца положительны (8, 3 и 1), следовательно, необходимо перейти к шагу 6.

Шаг 6. Выбор разрешающей строки (переменной, выводимой из базиса) по условию:

для air > 0,

где s - номер разрешающей строки.

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

Для первой строки: D₁ = 80 / 8 = 10.

Для второй строки: D₂ = 60 / 3 = 20.

Для третьей строки: D₃ = 40 / 1 = 40.

Наименьший результат  деления - в первой строке, значит именно эту строку мы выбираем в качестве разрешающей, т.е. исключать из базисного решения будем переменную x₃. Элемент, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом. В нашем случае таковым является 8 (элемент, стоящий на пересечении первой строки и первого столбца).

Шаг 7. Пересчет элементов симплекс-таблицы (переход к новому базисному решению). Порядок пересчета различных элементов таблицы несколько отличается.

Для элементов  разрешающей строки используются следующие формулы:

где s - номер разрешающей  строки,

r - номер разрешающего столбца, 

, - новые значения пересчитываемых элементов,

a_sj, b_s - старые значения пересчитываемых элементов,

a_sr - старое значение разрешающего элемента.

Таким образом, при пересчете  элементов разрешающей строки каждый ее элемент делится на разрешающий  элемент.

Еще проще пересчитать элементы разрешающего столбца. Все они (кроме разрешающего элемента) становятся равными нулю:

.

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

где , , , - новые значения пересчитываемых элементов,

a_ij, b_i, c_j, L - старые значения пересчитываемых элементов.

Применение правила прямоугольника проиллюстрируем, используя таблицу 2. Пересчитаем элемент a₃₂ (в исходной симплекс-таблице его значение равно 4). В таблице 2 можно видеть прямоугольник (прочерчен пунктиром), соединяющий четыре элемента, участвующих в пересчете:

,   т.е.

Аналогичным образом  пересчитываются остальные элементы.

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

базис	переменные					bi
	x1	x2	x3	x4	x5
x3	1	1/4	1/8	0	0	10
x4	3	3	0	1	0	60
x5	1	4	0	0	1	40
cj	4	1	0	0	0	0

По окончании пересчета  осуществляется возврат к шагу 3.

Полностью результат  пересчета для нашего примера  можно видеть в таблице 3.

Таблица 3 - Симплекс-таблица (второе базисное решение)

базис	переменные					bi
	x1	x2	x3	x4	x5
х1	1	1/4	1/8	0	0	10
x4	0	9/4	-3/8	1	0	30
х5	0	15/4	-1/8	0	1	30
cj	0	0	-1/2	0	0	-40