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

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

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

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

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

7.1. Элементы модели динамического программирования. Задача распределения капиталовложений

Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме пред­приятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 5 млн. долл. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами (в миллионах долларов) суммарных затрат (с) и доходов (R), связан­ных с реализацией каждого из проектов. Соответствующие данные приведены в табл. 7.1, в которую включены также проекты с нуле­выми затратами. Это позволяет учесть возможность отказа от рас­ширения какого-либо предприятия. Цель фирмы состоит в получе­нии максимального дохода от инвестиций в объеме 5 млн. долл.

Таблица 7.1

Проект	Предприятие 1		Предприятие 2		Предприятие 3
	c1	R1	c2	R2	c3	R3
1	0	0	0	0	0	0
2	1	5	2	8	1	3
3	2	6	3	9	-	-
4	-	-	4	12	-	-

Прямой и, по-видимому, чрезмерно упрощенный способ решения сформулированной задачи заключается в использовании процедуры полного перебора. Задача имеет 3*4*2=24 возможных решения, причем некоторые из них не являются допустимыми, так как пред­полагают ассигнование свыше 5 млн. долл. В процессе полного перебора вычисляются суммарные затраты, ассоциированные с каж­дым из 24 возможных решений. Если величина затрат не превышает объема авансированных средств, следует вычислить соответствую­щий суммарный доход. Оптимальным будет допустимое решение, обеспечивающее максимум суммарного дохода. Например, затраты на реализацию проектов 2, 3 и 1 для предприятий 1, 2 и 3 составля­ют 4 млн. долл. (<5), а суммарный доход равен 14 млн. долл. С другой стороны, набор проектов 3, 4 и 2 не является допустимым, так как объем затрат в этом случае равен 7 млн. долл.

Отметим следующие недостатки процедуры полного перебора.

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

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

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

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

7.1.1. Сетевая модель

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

x₁ = объем капиталовложений, распределенных на этапе 1;

х₂ = объем капиталовложений, распределенных на этапах 1 и 2;

x₃ = объем капиталовложений, распределенных на этапах 1, 2 и 3.

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

Заметим, что конкретные значения х₁ и х₂ заранее не известны, однако мы знаем, что эти значения лежат в интервале между 0 и 5. Так как затраты на реализацию каждого из проектов выражаются целыми числами, значения х₁ и х₂ могут быть равны 0, 1, 2, 3, 4 и 5. С другой стороны, значение переменной х₃, которая выражает объем капиталовложений, распределенных на всех трех этапах, равно 5.

Рис. 7.1 служит иллюстрацией сетевой модели для рассматри­ваемой задачи. Каждому возможному значению x₁, х₂ и х₃ поставлен в соответствие узел, ассоциированный с одним из этапов j=1, j=2 и j=3. Начальный этап j=0 введен в рассмотрение для удобства вы­числений. Длины дуг, соединяющих узлы на некотором этапе с уз­лами на последующем этапе, численно равны доходам от реализации наилучшего допустимого проекта. Рассмотрим дуги, соединяющие узел 0 на этапе j=0 с узлами х₁=(0, 1, 2, 3, 4, 5) на этапе j=1. Дуга (0,0) (соединяющая узлы 0 на этапе j=0 и 0 на этапе j= 1) соответст­вует случаю, когда средства на этапе 1 не выделяются. Допустимым здесь является проект 1 с R₁=0, и дуге (0, 0) приписывается длина R₁(0, 0)=0. С другой стороны, для дуги (0, 1) допустимыми оказы­ваются проекты 1 и 2, что предопределяет выбор проекта 2 с более высоким уровнем дохода R₁=5; дуге (0, 1) приписывается длина 5. По тем же самым причинам дуге (0, 2) приписывается длина 6, по­скольку здесь все три проекта являются допустимыми, а проекту 3 соответствует самый высокий уровень дохода R₁=6. Значения x₁=3, 4 и 5 соответствуют «избыточным» вариантам, для которых в лучшем случае R₁=6.

Дуги, соединяющие узлы на этапе 1 с узлами на этапе 2, задают­ся узлами х₁ и х₂. Величина х₂ – x₁ по определению равна объему капиталовложений, распределенных только на этапе 2. Таким об­разом, дуга (х₁, х₂) является допустимой лишь для проектов, за­траты на реализацию которых не превышают х₂ – x₁. Длина этой дуги равна наибольшему значению R₂ для всех таких проектов. Пусть, например, x₁=1 и х₂=5. Объем распределенных на этапе 2 капита­ловложений равен х₂ – x₁=4, и все четыре проекта оказываются допустимыми. Так как проекту 4 соответствует самый высокий уро­вень дохода

Рис. 7.1.

(R₂=12), дуге (1, 5) приписывается длина 12. С другой стороны, для дуги (1, 3)

х₂ – x₁=2,откуда вытекает допустимость только проектов 1 и 2. Следовательно, длина дуги (1,3) равна 8. Заметим, наконец, что в случае x₁ > x₂ соответствующая дуга не су­ществует, поскольку значение х₂ должно быть по меньшей мере рав­но значению х₁. (Чтобы проверить степень понимания материала, рекомендуется построить рассмотренную сеть на отдельном листе бумаги, не пользуясь рис. 7.1.)

Исследуем свойства сетевой модели. Легко видеть, что каждая дуга единственным образом связана с некоторым проектом. Наша цель состоит в отыскании связной последовательности дуг, соеди­няющей узел 0 на этапе j=0 с узлом 5 на этапе j=3 и обладающей максимальной длиной (соответствующей наибольшему доходу). Из определения величин х₁, х₂ и х₃ следует, что любой связный путь из узла 0 на этапе j=0 в узел 5 на этапе j=3 соответствует допустимой комбинации проектов (сравните с процедурой полного перебора). Если внимательно изучить построенную сеть, то нетрудно заметить, что некоторые дуги можно отбросить как заведомо неоптимальные. Например, можно исключить дугу (0, 1) между этапами j=1 и j=2, так как ассигнование х₂ – x₁= 1 млн. долл. на этапе 2 не приносит ни­какого дохода, поскольку эта сумма не является достаточной для реализации проекта 2. Исключение неоптимальных дуг значительно уменьшает объем необходимых вычислений. Однако, чтобы сделать изложение материала более доходчивым, мы не будем рассматривать процедуры такого рода. Тем не менее, если у вас появился интерес к проблеме идентификации неоптимальных дуг, рекомендуем обратиться к следующему упражнению.

После того как сеть построена, найдем самый длинный путь от узла 0 на этапе j=0 до узла 5 на этапе j=3. Метод решения этой задачи аналогичен методу нахождения кратчайшего маршрута. Представляется целесообразным описать метод поиска самого длинного пути подробно, так как он тесно связан с вычислительной схемой динамического программирования.

Обозначим через f_j (x_j) величину самого длинного пути, ведущего в узел x_j на этапе j. Поскольку j=0 — исходный этап, f₀(0)=0. Далее вычисления производятся поэтапно.

Этап 1. Так как узел 0 на этапе j=0 с каждым из шести узлов x₁=0, 1, 2, 3, 4 и 5 на этапе j= 1 соединяет единственная дуга, самый длинный путь до узла x₁ определяется формулой

f₁(x₁) = f₀ (0) + R₁ (0, x₁),

где R₁(0, x₁) — длина (доход) дуги (0, x₁). Имеем

f₁ (0) = 0 + 0 = 0, f₁ (3) = 0 + 6 = 6,

f₁ (1) = 0 + 5 = 5, f₁ (4) = 0 + 6 = 6,

f₁ (2) = 0 + 6 = 6, f₁ (5) = 0 + 6 = 6,

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

Этап 2. На данном этапе вычисляются величины самых длин­ных путей до всех узлов x₂ =0, 1, 2, 3, 4 и 5. В отличие от этапа 1 количество дуг, входящих в один из узлов на этапе 2, может превы­шать единицу. В результате имеем

(Величина самого длинного пути до узла x₂)

= max

^{по допустимым дугам (x1, x2)}

{(Величина самого длинного пути до узла x₁)+(Длина дуги(x₁, x₂))}.

Запишем это равенство в математической форме:

f₂(x₂) = max {f₁(x₁) + R₂(x₁, x₂)}.

^{по допустимым дугам (x1, x2)}

Ниже приводятся результаты вычислений по данной формуле. (Со­ветуем обратиться к рис. 7.1 и проследить за ходом вычислений.)

f₂ (0) =0+0=0,

f₂ (1) = mах {0+0; 5+0} =5,

f₂ (2) = mах {0+8; 5+0; 6+0} = 8,

f₂ (3) = mах {0+9; 5+8; 6+0; 6+0} = 13,

f₂ (4) = mах {0+12; 5+9; 6+8; 6+0; 6+0} = 14,

f₂ (5) = mах {0+12; 5+12; 6+9; 6+8; 6+0; 6+0} = 17.

Полученные результаты представлены на рис. 7.2, б, на котором показаны дуги, соответствующие вычисленным значениям f₂. Как и ранее, числа в круглых скобках обозначают номера проектов, ассоциированных с конкретными дугами.

Рис. 7.2.

Этап 3. По аналогии с этапом 2 соотношение, определяющее самый длинный путь f₃(x₃) до узла х₃, запишем в следующем виде:

f₃(x₃) = max {f₂(x₂) + R₃(x₂, x₃)}

^{по допустимым дугам (x2, x3)}

В результате вычислений находим (см. рис. 9.1)

f₃ (5) = mах {0+3; 5+3; 8+3; 13+3; 14+3; 17+0} = 17.

На рис. 7.2, в изображены оптимальные дуги, соответствующие вычисленному значению f₃(5).

Из рис. 7.2 нетрудно заметить, что любой связный путь от узла 0 на этапе j=0 до узла 5 на этапе j=3 определяет оптимальное решение исходной задачи. Всего имеется три различных решения, кото­рые приводятся в следующей таблице:

Оптимальный путь	Оптимальный набор проектов
(0, 1), (1, 4), (4, 5) (0, 1), (1, 5), (5, 5) (0, 2), (2, 4), (4, 5)	(2, 3, 2) (2, 4, 1) (3, 2, 2)

Отметим, что всем трем решениям соответствует один и тот же уро­вень дохода, а именно f₃ = 17 млн. долл.

7.1.2. Модель динамического программирования

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

Необходимо внести ясность в вопрос о структуре рекуррентных вычислений в ДП. Расчеты на некотором этапе осуществляются на базе сводной информации о максимальном суммарном доходе (самом длинном пути), полученной в результате вычислений на всех пред­шествующих этапах. При этом отдельные решения, найденные на предшествующих этапах, не представляют существенного интереса. Действительно, все последующие решения строятся некоторым оптимальным образом независимо от решений, полученных на предшествующих этапах. Это отражает сущность принципа опти­мальности, составляющего основу вычислительной схемы ДП.

Наиболее важным при построении сетевой модели, по-видимому, является способ определения величин х_j, который позволяет авто­матически выводить из рассмотрения недопустимые проекты (дуги). В ДП используется аналогичный прием, приводящий к понятию со­стояния системы. Этот термин не представляется бесспорно удачным, поскольку он описывает «состояние» системы лишь с позиций нали­чия ограниченного количества некоторого ресурса, что обеспечивает взаимную увязку всех этапов.

Если воспользоваться обозначениями, введенными при рассмот­рении сетевой модели, можно записать рекуррентное соотношение ДП в следующем виде:

f_j (x_j) = max {R_j (k_j) + f_j-1(x_j-1)}, j=1, 2, 3,

^{по допустимым проектам k}_j

где f₀(x₀)=0 по определению. Приведенное равенство действительно является рекуррентным, так как величина f_j (x_j) на этапе j вычис­ляется по известному значению f_j-1 (x_j-1) на этапе j-1 при f₀(x₀)=0.

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

Во-первых, заметим, что f_j(x_j) является функцией единственного аргумента x_j. Отсюда следует, что правая часть рекуррентного со­отношения должна быть выражена через x_j, а не через x_j-1. Вернем­ся к сетевой модели и вспомним, что разность между x_j и x_j-1 равна величине затрат (с_j) на реализацию проекта k_j на этапе j, т. е.

c_j (k_j) = x_j - x_j-1

Теперь можно выразить х_j-1 через x_j с помощью равенства x_j-1 = x_j – c_j(k_j). Такая замена обеспечивает более корректную мате­матическую запись рекуррентного соотношения.

Во-вторых, необходимо представить в математической форме условие, предписывающее рассмотрение только допустимых проек­тов. Как и в случае сетевой модели, можно воспользоваться равенст­вом c_j (k_j) = x_j – x_j-1. Однако это ограничение уже введено выше пу­тем замены x_j-1 = x_j – c_j (k_j) в функции f_j-1(x_j-1). Чтобы обеспечить полную корректность, следует в явном виде учесть не требующее пояснений неравенство x_j-1 ≥ 0, откуда x_j – c_j (k_j) ≥ 0 или c_j (k_j) ≤ x_j.

Таким образом, рекуррентное соотношение и ДП имеет следую­щий вид:

f₀(x₀) = 0,

f_j(x_j) = max {R_j (k_j) + f_j-1(x_j - c_j (k_j))}, j=1, 2, 3.

c_j (k_j) ≤ x_j

Ниже приводятся результаты поэтапных расчетов на основе рекуррентного соотношения для рассматриваемой задачи. Они представлены в виде таблиц, так как в ДП обычно используется таб­личная форма записи числовых результатов. Разумеется, весьма заманчивой выглядит перспектива проводить вычисления с исполь­зованием таблиц механически без четкого понимания, для чего вы­полняется та или иная операция. Однако такой путь приводит к це­лому ряду негативных последствий, и его ни в коем случае не следует выбирать тому, кто знакомится с основами динамического программирования. Следует придерживаться двух рекомендаций: (1) сравнивать результаты вычислений с использованием таблиц и расчетов с помощью сетевой модели и (2) всегда связывать исход­ные данные вычислений с использованием таблиц с соответствую­щими математическими символами в рекуррентном соотношении.

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

Этап 1

f₁(x₁) = max {R₁ (k₁)}.

c₁ (k₁) ≤ x₁, k₁ = 1, 2, 3

x1	R1(k1)			Оптимальное решение
	k1 = 1	k1 = 2	k1 = 3	f1(x1)	k1*
0 1 2 3 4 5	0 0 0 0 0 0	- 5 5 5 5 5	- - 6 6 6 6	0 5 6 6 6 6	1 2 3 3 3 3

Этап 2

f₂(x₂) = max {R₂ (k₂) + f₁ (x₂ - c₂ (k₂))}.

c₂ (k₂ ) ≤ x₂, k₂ = 1, 2, 3, 4

x2	R2 (k2) + f1 (x2 - c2(k2))				Оптимальное решение
	k2 = 1	k2 = 2	k2 = 3	k2 = 4	f2(x2)	k2*
0 1 2 3 4 5	0+0=0 0+5=5 0+6=6 0+6=6 0+6=6 0+6=6	- - 8+0=8 8+5=13 8+6=14 8+6=14	- - - 9+0=9 9+5=14 9+6=15	- - - - 12+0=12 12+5=17	0 5 8 13 14 17	1 1 2 2 2 или 3 4

Этап 3

f₃(x₃) = max {R₃ (k₃) + f₂ (x₃ – c₃ (k₃))}.

c₃ (k₃ ) ≤ x₃, k₃ = 1, 2

x3	R3 (k3) + f2 (x3 – c3 (k3))		Оптимальное решение
	k3 = 1	k3 = 2	f3(x3)	k3*
5	0+17=17	3+14=17	17	1 или 2

Оптимальное решение можно найти непосредственно из приве­денных выше таблиц. Сначала рассматривается таблица, построен­ная на этапе 3. При х₃=5 оптимальный проект имеет либо k₃^*=1, либо k₃^*=2. Пусть сначала k₃^*=1. Так как с₃(1)=0, на этапах 2 и 1 х₂=х₃ – с₃(1)=5. Легко видеть, что на этапе 2 из

Рис. 7.3.

x₂ =5 следует k₂^* =4. Далее с₂(4)=4, откуда х₅ =5-4= 1. На этапе 1 из x₁= 1 вытекает k₁^* =2. Таким образом, (2, 4, 1) есть оптимальный набор проектов для этапов 1, 2 и 3. На рис. 7.3 изображена схема определения всех различных оптимальных наборов проектов.

7.1.3 Рекуррентное соотношение для процедуры обратной прогонки

В разд. 7.1.1 и 7.1.2 вычисления проводились в соответствии с последовательностью

f₁  f₂  f₃

Такой метод вычислений известен как алгоритм прямой прогонки, поскольку расчеты осуществляются в естественном порядке следо­вания этапов. Однако в специальной литературе, посвященной динамическому программированию, рассматриваются рекуррентные соотношения, которые предписывают начинать вычисления с по­следнего этапа и затем «двигаться» назад до этапа 1. Такой метод вычислений известен как алгоритм обратной прогонки.

Основное различие между процедурами прямой и обратной про­гонки заключается в способе определения состояния системы. С це­лью пояснения опять обратимся к задаче распределения капитало­вложений. Для процедуры обратной прогонки определим состояния y_j следующим образом:

y₁ = объем капиталовложений, распределенных на этапах 1, 2 и 3;

y₂ = объем капиталовложений, распределенных на этапах 2 и 3;

y₃ = объем капиталовложений, распределенных на этапе 3.

Рис. 7.4.

Рис. 7.4 помогает лучше уяснить различие между определениями состояний x_j и y_j в процедурах прямой и обратной прогонки.

Положим

f₃(x₃) = максимальный доход на этапе 3 при заданном у₃;

f₂(x₂) = максимальный доход на этапах 2 и 3 при заданном у₂;

f₁(x₁) = максимальный доход на этапах 1, 2 и 3 при заданном у₁.

Рекуррентное соотношение для процедуры обратной прогонки за­писывается в следующем виде:

f₄(x₄) = 0,

f_j(y_j) = max {R_j (k_j) + f_j+1(y_j - c_j (k_j))}, j=1, 2, 3.

k_j

c_j (k_j) ≤ y_j

Порядок поэтапных вычислений определяется последовательностью f₃  f₂  f₁. Ниже приводятся результаты расчетов.

Этап 3

f₃ (y₃) = max {R₃ (k₃)}.

c₃ (k₃) ≤ y₃, k₃ = 1, 2

y3	R3 (k3)		Оптимальное решение
	k3 = 1	k3 = 2	f3(y3)	k3*
0 1 2 3 4 5	0 0 0 0 0 0	- 3 3 3 3 3	0 3 3 3 3 3	1 2 2 2 2 2

Этап 2

f₂ (y₂) = max {R₂ (k₂) + f₃ (y₂ - c₂ (k₂))}.

c₂ (k₂ ) ≤ y₂, k₂ = 1, 2, 3, 4

y2	R2 (k2) + f3 (y2 - c2 (k2))				Оптимальное решение
	k2 = 1	k2 = 2	k2 = 3	k2 = 4	f2(y2)	k2*
0 1 2 3 4 5	0+0=0 0+3=3 0+3=3 0+3=3 0+3=3 0+3=3	- - 8+0=8 8+3=11 8+3=11 8+3=11	- - - 9+0=9 9+3=12 9+3=12	- - - - 12+0=12 12+3=15	0 3 8 11 12 15	1 1 2 2 3 или 4 4

Этап 1

f₁ (y₁) = max {R₁ (k₁) + f₂ (y₁ – c₁ (k₁))}.

c₁ (k₁ ) ≤ y₁, k₁ = 1, 2, 3

y1	R1 (k1) + f2 (y1 – c1 (k1))			Оптимальное решение
	k1 = 1	k1 = 2	k1 = 3	f1(y1)	k1*
5	0+15=15	5+12=17	6+11=17	17	2 или 3

Оптимальное решение можно определить, начиная с у₁ на этапе 1 и двигаясь далее до у₃ на этапе 3. Разумеется, это решение совпадает с решением, полученным с помощью алгоритма прямой прогонки. (Проверьте!)

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

ЛАБОРАТОРНАЯ РАБОТА №1

ИЗУЧЕНИЕ ГРАФИЧЕСКОГО МЕТОДА ЛИНЕЙНОГО ПРОГРАММИРОВАМ (ЛП)

1. Цель работы

1.1. Научиться отроить математические модели ЛП.

1.2. Изучить принцип графического представления задачи линейного программирования.

1.3. Изучить графический метод ЛП.

2. Краткие теоретические сведения

Рассмотрим конкретный пример. Пусть предприятие производит два вида кабеля: С и К. Для производства каждого кабеля необходимы два исходных вида сырья: А и В. Максимально возможные суточные запасы сырья составляют 6 и 8 тонн соответственно. Для производства одного километре кабеля С необходима одна тонна сырья А и две тонны сырья 8. Для производства кабеля К необходимы две тонны сырья А и одна тонна сырья В.

Известно, что суточный спрос на кабель К никогда не превышает спроса на кабель С более чем на один километр. Кроме того, спрос на кабель К не превышает 2 км в сутки. За реализацию кабеля предприятие получает прибыль: за I км кабеля К - 2000 руб., кабеля С - 3000 рублей.

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

Построение математической модели

Процесс построения математической модели для решения поставленной задачи можно начать с ответов на три вопроса :

1. Для определения каких величин должна быть построена модель? Другими словами, как идентифицировать переменные (искомые величины) данной задачи?

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

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

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

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

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

Переменные. Так как нужно определить объемы производства каждого вида кабеля, переменными в модели являются:

Хк - суточный объем производства кабеля К (в км),

Хс . суточный объем производства кабеля С (в км).

Целевая функция. Так как прибыль от 1 км кабеля С равна 3 тыс.руб., суточная прибыль составит 3Хк тыс. руб. Аналогично прибыль от реализации Хс км кабеля С составит 2Хс тыс.руб. в сутки. При допущении независимости объемов сбыта каждого из кабелей общая прибыль равна сумме двух слагаемых прибыли от продажи кабеля 0 и от продажи кабеля К.

Обозначив общую прибыль (в тыс.руб.) через Z, можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения Хк и Хс , максимизирующие величину общей прибыли Z=3Хк+2Хс

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

Расход исходного продукта \ / Максимально возможный для производства обоих | = | запас данного исходного видов кабеля / \ продукта

Это приводит к следующим ограничениям (см.условия задачи):

Х+2Хс ≤ 6 (для А)

2Х+Хс ≤ 8 (для В)

Ограничения на величину опроса на продукцию имеют вид

/ Превышение спроса на \

| кабель К относительно | ≤ 1 км/сут. ,

\ спроса на кабель G /

(Спрос на кабель К ) ≤ 2 км/сут.

Математически эти ограничения записываются следующим образом:

Хс - Хк ≤ 1 (соотношение величин опроса на кабель К и С),

Хс ≤ 2 (максимальная величина опроса на кабель К).

Неявное, т.е. "подразумеваемое") ограничение заключается в том, что объемы производства продукции не могут принимать отрицательных значений (т.е. быть меньше нуля). Чтобы предотвратить получение таких недопустимых решений, потребуем выполнения условия неотрицательности переменных, т.е. введем ограничения на их знак:

Хс ≥ 0 (объем производства кабеля К),

Хк ≥ 0 (объем производства кабеля С).

Итак, математическую модель можно записать следующим образом. Определить суточные объемы производства (Хс и Хк) кабеля К и С (в км), при которых достигается

maxZ=3Хк+2Хс (целевая функция)

при

Хк+2Хс ≤ 6

2Хк+Хс ≤ 8

- Хк+Хс ≤ 1 (ограничения)

Хс ≤ 2

Хк ≥ 0, Хс ≥ 0

Что определяет линейный характер построенной модели? С формальных позиций данная модель является линейной потому, что все входящие в нее функции (ограничения и целевая функция) линейны. Линейность предполагает наличие двух свойств - пропорциональности и аддитивности.

1. Пропорциональность означает, что вклад каждой переменной (т.е. Хк и Хс) в целевую функцию и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной. Если, например, фирма будет предоставлять покупателям скидку, продавая кабель С по цене 2,5 тыс.руб. за км при объеме закупок свыше 2 км, то в такой си­туации не будет выполняться исходное условие задачи, заключающееся в том, что производство одного км кабеля С обеспечивает прибыль от реализации, равную 3 тыс.руб. В новых условиях эта прибыль будет равна 3 тыс.руб. при Хк≤2 км и 2,5 тыс.руб. при Хк > 2 км, т.е. прямая пропорциональность между прибылью и величиной Хк не имеет места.

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

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

Первый шаг при использовании графического метода заключается в геометрическом представлении допустимых решений, т.е. построении области (допустимых) решений, в которой одновременно удовлетворяются все ограничения модели. Искомая область (пространство) решений показана на рис.1. Условия неотрицательности переменных Хк≥0 и Хс≥О ограничивают область их допустимых значений первым квадрантом (представляющим собой по определению часть плоскости, расположенную над осью Хк и правее оси Хс), Другие границы пространства решений изображены на плоскости Хк, Хс прямыми линиями, построенными по уравнениям, которые получаются при замене знака "≤" на знак "-" в остальных ограничениях. Области, в которых выполняются соответствующие ограничения в вида неравенств, указываются стрелками, направленными в сторону допустимых значений переменных. Полученное таким

Рис. 1

образом пространство решений - многоугольник ABCDEF -показан на рис.1.

В каждой точке принадлежащей внутренней области или границам многоугольника решений ABCDEF, все ограничения выполняются, поэтому решения, соответствующие этим тачкам, являются допустимыми. Пространство решений содержит бесконечное число таких точек, но, несмотря на это, можно найти оптимальное ре­шение, если выяснить, в каком направлении возрастает целевая функция модели Z=3Хк+2Хс. Для этого на график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях Z, что позволяет определить наклон целевой функции и направление, в котором происходит ее увеличение (т.е. возрастание общего дохода).

Чтобы найти оптимальное решение, следует перемещать прямую, характеризующую прибыль, в направлении возрастания целевой функции до тех пор, пока она не сместится в область недопустимых решений. На рис.1 видно, что оптимальному решению соответству­ет точка С. Так как точка С является точкой пересечения прямых (I) и (2), значения Хк и Хс в этой точке определяются решением следующей системы двух уравнений:

Хк+2Хс = 6;

2Хк+Хс = 8.

Решение указанной системы уравнений дает следующий результат: Хк=3 1/3; Хс=1 1/3, Полученное решение означает, что суточный объем производства кабеля С должен быть равен 3 1/3 км, а кабеля К – 1 1/3 км. Прибыль, получаемая в этом случае, со­ставит

Z=3*3 1/3+2*1 1/3=12 2/3 тыс.руб.

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

На практике представляет интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение спроса и (или) изменения запасов исходных продуктов. Возможно, также потребуется определить влияние на оптимальное решение изменения рыночных цен.

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

Первая задача анализа на чувствительность. На сколько сократить или увеличить запасы ресурсов?

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

I. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции Z ?

2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции?

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

Прежде чем ответить на поставленные вопросы, классифицируем ограничения линейной модели как связывающие (активные) и несвязывавщие (неактивные) ограничения. Прямая, представляющая связывающее ограничение, должна проходить через оптимальную точку. В противном случае соответствующее ограничение будет не-связывающим. На рис.1 связывающими ограничениями являются только ограничения (I) и (2), т.е. те, которые лимитируют запасы исходных продуктов (ресурсов) А и В.

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

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

Вторая задача анализа на чувствительность. Увеличение объема какого из ресурсов наиболее выгодно?

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

Третья задача анализа на чувствительность. В каких пределах допустимо изменение коэффициентов целевой функции?

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

1. Каков диапазон изменения (увеличения или уменьшения) того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным и, наоборот, дефицитный ресурс сделать недефицитным?

3. Порядок выполнения работы

3.1. Получить у преподавателя исходные данные для работы.

3.2. Используя ЭВМ, построить систему координат и пространство допустимых решений для заданных исходных данных,

3.3. Задавшись произвольным значением целевой функции

(например, Z = 1), построить на экране дисплея график целевой функции.

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

3.5. Определить из системы уравнений оптимальный план производства.

3.6. Изменить коэффициенты целевой функции для двух слу­аев (цена на кабель К в два раза падает или возрастает).

3.7. Найти оптимальное решение для двух цен п.3.6. 3.8. Увеличить на единицу поочередно объемы ресурсов

А и В.

3.9. Построить пространства допустимых решений для п.3.8.

3.10. Найти оптимальное решение для п,3,8. 3.II. Проанализировать дефицитные и недефицитные ресурсы и влияние динамики цен на прибыль предприятия.

4. Содержание отчета

4.1. Цель работы.

4.2. Исходные данные.

4.3. Графики о экрана дисплея для всех вариантов п.3.3-3.10.

4.4. Анализ задачи на чувствительность к исходным данным.

4.5. Рекомендации по динамике исходных данных и цен, их влияние на оптимальное решение.

5. Контрольные вопросы

5.1. Можно ли улучшить значение целевой функции, заменяя неравенства в ограничениях на равенства?

5.2. Может ли достигаться оптимальное решение более чем в одной экстремальной точке?

5.3. Может ли целевая функция принимать одинаковые значения в двух экстремальных точках?

5.4. Всегда ли изменение коэффициентов целевой функции влияет на оптимальное решение?

5.5. Может ли дефицитный ресурс стать недефицитным при изменении коэффициентов целевой функции?

6. Литература

Таха X. Введение в исследование операций. - М.: Мир, 1996.

ЛАБОРАТОРНАЯ РАБОТА №2

РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ СИМПЛЕКС-МЕТОДОМ

1. Цель работы

1.1. Изучение вычислительной процедуры симплекс-метода.

1.2. Решение задач оптимизации на ЭВМ симплекс-методом.

2. Краткие теоретические сведения

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

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

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

1) все ограничения записываются в виде равенств с неотрицательной правой частью;

2) значения всех переменных модели должны быть неотрицательны;

3) целевая функция максимизируется или минимизируется.

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

2Х₁+5Х₂+3Х₃≤6

вводится переменная Х4>0, в результате чего исходное неравенство обращается в равенство

2Х₁+5Х₂+3Х₃+Х₄=6

Если правая часть равенства отрицательна, то, умножая обе части на -1, ее можно сделать неотрицательной.

Общую идею симплекс-метода можно проиллюстрировать на примере.

Пусть требуется максимизировать функцию

F=3Х₁+2Х₂

при ограничениях Х₁+2Х₂ ≤ 6

2Х₁+Х₂ ≤ 8

-Х₁+Х₂ ≤ 1

Х₂≤2, Х₁,Х₂≥0

Приведенная линейная модель может быть сведена к стандартной форме:

maxF=3Х₁+2Х₂+0Х₃+0Х₄+0Х₅+0Х₆

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

Х₁+2Х₂+Х₃=0

4Х₁+2Х₂+Х₄=8

-Х₁+Х₂+Х₅=1

Х₂+Х₆=2

На рис. I представлено пространство решений данной задачи. Каждую точку этого пространства можно определить с помощью переменных, входящих в модель стандартной формы. Например, при первое ограничение принимает вид равенства 2Х₁+4Х₂=12 , кото­рое можно представить прямой 3- 4.

Поскольку стандартная модель содержит четыре уравнения и шесть неизвестных, в каждой из экстремальных точек две переменные (6-4) должны иметь нулевые значения. Например, в точке 1 Х₁ и Х₂ равны нулю, в точке 2 – Х₄ и Х₅ , в точке 3 – Х₃ .

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

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

Алгоритм симплекс-метода состоит из следующих шагов.

Шаг 1. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение.

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

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

Шаг 4. Находится новое базисное решение, соответствующее новым

составам базисных и небазисных переменных.

В нашем примере точку 1 можно использовать как начальное

допустимое решение. В этой точке Х₁=Х₂=0 и Х₃=6; Х₄=8; Х₅=1; Х₆=2, а функция F=0.

Преобразовав уравнение целевой функции так, чтобы ее пра­вая часть стала равной нулю

F-3Х₁-2Х₂=0

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

Полученные результаты удобно представить в виде табл.1.

Таблица I

Базисные переменные		Х1	Х2	Х3	Х4	Х5	Х6	Решение
Х3	0	1	2	1	0	0	0	6
Х4	0	2	1	0	1	0	0	8
Х5	0	-1	1	0	0	1	0	1
Х6	0	0	1	0	0	0	1	2
F	1	-3	-2	0	0	0	0	0

Первый столбец этой таблицы содержит переменные пробного базиса X₃, X₄, X₅, X₆, значения которых приведены в последнем столбце.

Является ли полученное решение оптимальным? Нет. Об этом свидетельствует наличие в строке целевой функции отрицательных чисел. Это эквивалентно наличию положительных коэффициентов при этих переменных в исходной целевой функции. Поскольку речь идет о максимизации, значение F может быть увеличено при увеличе­нии как X₁, так и X₂. Если бы в cтроке целевой функции не было отрицательных чисел, это означало бы, что функция цели уже не пересекает оси в области положительных решений.

В качестве переменной, включаемой в базис, выберем Xj, так как коэффициент при ней больше и функция цели изменяется сильнее. Исключаемая переменная выбирается из совокупности базисных переменных X₃, X₄, X₅, X₆, Этой переменной является та, которая первой обращается в нуль при увеличении включаемой переменной X₁ вплоть до значения, соответствующего смежной экстремальной точке. В нашем случае переменная X₁ достигает максимально допустимого значения, равного 4, в точке 2, при этом исключаемой из базиса переменной становится Х₄.

Отношение, фиксирующее искомую точку пересечения и идентифицирующее исключаемую переменную, можно определить прямо из сим­плекс-таблицы. Для этого в столбце, соответствующем вводимой переменной Х₁, вычеркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных, фигурирующих в правых частях этих ограничений, к оставшимся элементам столбца, соответствующего вводимой переменной X₁. Исключаемой переменной будет та переменная базиса, для которой указанное выше отношение минимально.

Указанная процедура иллюстрируется табл. 2.

Таблица 2

Базисные переменные		Ведущий Х1	Х2	Х3	Х4	Х5	Х6	Решение
Х3 Ведущая	0	1	2	1	0	0	0	6 (6/1=6)
Х4 Ведущая	0	2	1	0	1	0	0	8 (8/2=4)
Х5	0	-1	1	0	0	1	0	1
Х6	0	0	1	0	0	0	1	2
F	1	-3	-2	0	0	0	0	0

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

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

Операция I.

Вое элементы ведущей строки. делятся на ведущий элемент и получают новую ведущую отроку.

Операция 2.

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

Х₁ | 0 | 1 ½ 0 ½ 0 0 | 4 ,

а строка, соответствующая Х₃:

Х₃ | 0 | 0 3/2 1 -1/2 0 0 | 2 .

Новая симплекс-таблица, полученная с помощью рассмотренных опе­раций, имеет следующий вид (табл.3).

Таблица 3

Базисные переменные	F	Х1	Х2	Х3	Х4	Х5	Х6	Решение
Х3	0	0	3/2	1	-1/2	0	0	2(2/(3/2)=4/3)
Х1	0	1	1/2	0	1/2	0	0	4(4/(1/2)=8)
Х5	0	0	3/2	0	1/2	1	0	5 10/3
Х6	0	0	1	0	0	0	1	2(2/1=2)
F	1	0	-1/2	0	3/2	0	0	12

В новом решении значение F возросло с 0 до 12.

Из табл. 3 следует, что на очередной итерации в качестве вводимой переменной следует выбрать X₂, так как коэффициент при этой переменной в F -уравнении равен -1/2. Исключаемой перемен­ной будет Х₃, а включаемой – Х₂. Новая симплекс-таблица будет иметь вид (табл. 4).

Таблица 4

Базисные переменные		Х1	Х2	Х3	Х4	Х5	Х6	Решение
Х2	0	0	1	2/3	-1/3	0	0	4/3
Х1	0	1	0	-1/3	2/3	0	0	10/3
Х5	0	0	0	-1	1	1	0	3
Х6	0	0	0	-2/3	1/3	0	1	2/3
F	1	0	0	1/3	4/3	0	0	12 2/3

В новом базисном решении Х₁ =3¹/₃и X₂=1¹/₃. Значение F увеличилось с 12 (предыдущая таблица) до 12²/₃. Этот прирост целевой функции обусловлен увеличением X₂ от 0 до ⁴/₃, так как из F- отроки предыдущей симплекс-таблицы следует, что возрастанию дан­ной переменной на единицу соответствует увеличение функции на ¹/₂.

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

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

ИСХОДНЫЕ УСЛОВИЯ

Кабельный завод производит кабели четырех типов: I, 2, 3, 4. Для их производства используются металлы трех типов: М, С, Б. Данные о месячных поставках металлов приведены в табл.5. Расход металла на каждый вид кабеля приведен в табл.б. Оптовые цены на кабели дани в табл.?. Сколько и какого вида кабелей необходимо производить чтобы завод получил максимальную прибыль?

Таблица 5

Вариант металл	1	2	3	4	5	6
М	15	25	20	12	16	14
С	19	9	12	18	10	10
Б	30	35	30	32	30	28

Таблица 7

Вариант	1	2	3	4	5	6
кабель	М, С, Б	М, С, Б	М, С, Б	М, С, Б	М, С, Б	М, С, Б
К1	3, 4, 5	2, 3, 6	3, 5, 4	4, 5, 6	5, 6, 7	2, 4, 5
К2	5, 3, 6	4, 3, 5	5, 4, 6	3, 4, 5	5, 6, 4	3, 4, 3
К3	2, 3, 4	3, 2, 4	3, 4, 2	4, 5, 3	4, 5, 2	3, 5, 4
К4	7, 5, 8	6, 4, 8	5, 6, 8	4, 5, 3	4, 6, 7	7, 4, 8

Таблица 6

Вариант металл	1	2	3	4	5	6
К1	42	50	45	35	40	35
К2	50	55	40	50	50	40
К3	34	20	46	22	30	32
К4	35	35	25	28	29	18

СОДЕРЖАНИЕ ОТЧЕТА

Отчет должен содержать:

1. Исходные данные задачи.

2. Математическую формулировку задачи,

3. Алгоритм расчета.

4. Симплекс-таблицу с выделенными ключевой строкой и ключевым столбцом.

5. Результаты расчета.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Любую ли задачу линейного программирования можно решить симплекс-методом?

2. Дать определение ключевой отроке, ключевому столбцу.

3. Дать графическую интерпретацию симплекс-методу.

4. Зависит ля объем вычислений при реализации симплекс-метода от количества ограничений?

5. Может ли ведущий элемент иметь нулевое значение?

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

ЛИТЕРАТУРА

1. Таха X. Введение в исследование операций. -М.: Мир, 1996.

2. Балашевич В.А. Ооновы математического программирования. -Мн.: Вышэйшая школа, 1985.

ЛАБОРАТОРНАЯ РАБОТА №3

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1. Цель работы

1.1. Научиться строить математические модели транспортной задачи.

1.2. Изучить принцип построения опорных планов.

1.3. Изучить метод оптимизации ТЗ.

2. Краткие теоретические сведения

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

Частный случай распределительной задачи – транспортная задача.

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

Задача – транспортная. Такого рода задача записывается в виде матрицы.

а и b посление цифры в номере зачетной книжки

	1	2	3	4	5	номерная емкость АТС
A	1+b	2+2b	1+a+b	1+2b	a+b	80+10a+b
B	1+b	а+b	3b	2b	6	60+4b
C	3b+a	b+a+4	2b+1	3b-1	4b-a	100+a+b
D	5	2b+a	3b-a	4+a	6	40+4b+a
номерная емкость района	30+b	40+a+b	60+4b	80+a+2b	110+6b

Предположим, что а =1, а b=3:

	1	2	3	4	5	номерная емкость АТС
A	4	8	5	7	4	93
B	4	4	9	6	6	72
C	10	8	7	8	11	104
D	5	7	8	5	6	53
номерная емкость района	33	44	72	87	128

Подсчитаем суммы номерных емкостей:

Заявки - номерная емкость района: 33+44+72+87+128 = 364

номерная емкость АТС: 93+72+104+53 = 322

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

Решение начинается с составления опорного плана.

2. Составление опорного плана методом наименьших стоимостей.

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи. По той причине, что число заявок и запасов не совпадает, то вводится фактическая строка.

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

На основании вышеизложенного строим опорный план.

Району №1 необходимо 33 номера, расстояния от АТС минимальны в случае A и B. Запросы района №1 удовлетворяются станцией A. Району №2 необходимо 44 номера, а ближе всех расположена АТС B. Удовлетворим запросы района №2 через станцию B. Району №3 необходимо 72 номера и хоть расстояние минимально от станции A, но минимум расстояния приходится на район №5, так что от станции A запитывается район №5 на чем его номерная емкость исчерпана. Необходимость в номерах района №3 удовлетворит станция С и на этом необходимость этого района в свободных номерах будет удовлетворена. Для района №4 минимум расстояния приходится на станцию D, но по той причине, что на станции B остаются невостребованные номера, район №4 забирает на себя все вакантные номера станции В, далее станции D располагает только 53 номерами, их забирает район №4 и еще району нужно 6 номеров, которыми его снабдит станция С. На станции С остаются свободными еще 26 номеров, которые придутся кстати району №5. На этом этапе все вакантные емкости станций были исчерпаны, а 42 номера в которых так нуждались потребители остались неподключенными

	1		2		3		4		5		номерная емкость АТС
A	33	4	0	8	0	5	0	7	60	4	93
B	0	4	44	4	0	9	28	6	0	6	72
C	0	10	0	8	72	7	6	8	26	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		0		42		42
номерная емкость района	33		44		72		87		128

Последние 42 номера попав в финишную строку означает: пятый район недополучит 42 номера

Стоимость плана

S = 33*4+44*4+72*7+6*8+28*6+53*5+60*5+26*11= 1819 у.е

3 Составление опорного плана методом северо-западного угла.

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

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

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

На основании вышеизложенного строим опорный план.

Району №1 необходимо 33 номера, расстояния от АТС минимальны в случае A и B. Запросы района №1 удовлетворяются станцией A. Району №2 необходимо 44 номера, а ближе всех расположена АТС B. Удовлетворим запросы района №2 через станцию B. Району №3 необходимо 72 номера, поэтому станция А удовлетворяет запросы района №3 до тех пор, пока позволяет номерная емкость. Значит, от станции А район получает 60 номеров, а остальные 12 предоставляет станция С. Район №4 ждет 87 номеров. Станция В даст весь свой остаток, составляющий 28 номеров, станция D даст весь свой запас номеров, составляющий 53 номера, а недостающие 6 номеров предоставляет станция С. Получается, что району №5 необходимо 128 номеров, но номера может предоставить только станция С и то не полностью. Поэтому все 86 номера из зарезервированных 104 пойдет на нужды района №5

	1		2		3		4		5		Номерная емкость АТС
A	33	4	0	8	60	5	0	7	0	4	93
B	0	4	44	4	0	9	28	6	0	6	72
C	0	10	0	8	12	7	6	8	86	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		0		42		42
номерная емкость района	33		44		72		87		128

Район №5 недополучит 42 номера

S = 33*4+44*4+60*5+12*7+28*6+6*8+53*5+86*11 = 2119 у.е

4. Оптимизация транспортной задачи методом потенциалов.

Для оптимизации транспортной задачи в качестве опорного возьмем план по методу северо-западного угла.

Начинаем оптимизацию.

	1		2		3		4		5		номерная емкость АТС
A	33	4	0	8	60	5	0	7	0	4	93
B	0	4	44	4	0	9	28	6	0	6	72
C	0	10	0	8	12	7	6	8	86	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		0		42		42
номерная емкость района	33		44		72		87		128

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

Этот метод проверки на оптимальность плана называется «Методом потенциалов»

Итак, вначале построим наглядную схему для нахождения потенциалов. Для этого присвоим всем АТС потенциал Va, Vb, Vc, Vd, Ve, а районам U₁, U₂, U₃, U₄, U₅

Зададимся начальным потенциалом U_{1 ,} выберем его равным соразмерным расстояниям, скажем, равным 4. Переход от АТС к району определяется расстоянием, то есть стрелкой, которая будет обозначаться буквой С

Итак, U₁=4

Vа Vb Vc Vd Vе

U₁ U₂ U₃ U₄ U₅

Проверим по методу потенциалов план на соответствие

U₁ = 4 Va = Ca₁ + U₁ = 4 + 4 = 8

U₂ = Vb - Cb₂ = 8 – 4 = 4 Vb = U₄ + Cb₄ = 2 + 6 = 8

U₃ = Vа - Ca₃ = 8 – 5 = 3 Vc = U₃ + C c₃ = 3 + 7 = 10

U₄ = Vc - Cc₄ = 10 – 8 = 2 Vd = U₄ + Cd₄ = 2 + 5 = 7

U₅ = Vc - Cc₅ = 10 – 11 = -1 Ve = U₅ + Ce₅ = -1 + 0 = -1

Тогда найдем потенциалы в незаполненных клетках по формуле, имеем

Vb - U₁ – Cb₁ = 8 – 4 – 4 = 0 истина

Vс - U₁ – Cс₁ = 10 – 4 – 10 = -4 норма

Vd - U₁ – Cd₁ = 7 – 4 – 5 = -2 норма

Ve - U₁ – Ce₁ = -1 – 4 – 0 = -5 норма

Va - U₂ – Ca₂ = 8 – 4 – 8 = -4 норма

Vc - U₂ – Cc₂ = 10 – 4 – 8 = -2 норма

Vd - U₂ – Cd₂ = 7 – 4 – 7 = -4 норма

Ve - U₂ – Ce₂ = -1 – 4 – 0 = -5 норма

Vb - U₃ – Cb₃ = 8 – 3 – 9 = -4 норма

Vd - U₃ – Cd₃ = 7 – 3 – 8 = -4 норма

Ve - U₃ – Ce₃ = -1 – 3 – 0 = -4 норма

Va - U₄ – Ca₄ = 8 – 2 – 7 = -1 норма

Ve - U₄ – Ce₄ = -1 – 2 – 0 = -3 норма

Va - U₅ – Ca₅ = 8 + 1 – 4 = 5

Vb - U₅ – Cb₅ = 8 + 1 – 6 = 3

Vd - U₅ – Cd₅ = 7 + 1 – 6 = 2

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

	1		2		3		4		5			номерная емкость АТС
A	33	4	0	8	6 0-x	5	0	7		x	4	93
B	0	4	44	4	0	9	28	6		0	6	72
C	0	10	0	8	1 2+x	7	6	8		86 –x	11	104
D	0	5	0	7	0	8	53	5		0	6	53
E	0		0		0		0		42			42
номерная емкость района	33		44		72		87		128

Неизвестная величина X всегда равна наименьшему числу от которого производится вычитание. Значит, здесь X = 60. И получаем новую таблицу, для которой повторяется расчет на оптимальность методом потенциалов. Имеем

	1		2		3		4		5			номерная емкость АТС
A	33	4	0	8	0	5	0	7		60	4	93
B	0	4	44	4	0	9	28	6		0	6	72
C	0	10	0	8	72	7	6	8		26	11	104
D	0	5	0	7	0	8	53	5		0	6	53
E	0		0		0		0		42			42
номерная емкость района	33		44		72		87		128

S = 33*4+44*4+72*7+28*6+6*8+53*5+60*4+26*11 = 1819 у.е

Vа Vb Vc Vd Vе

U₁ U₂ U₃ U₄ U₅

Проверим по методу потенциалов план на соответствие

U₁ = 4 Va = Ca₁ + U₁ = 4 + 4 = 8

U₂ = Vb - Cb₂ = 13 – 4 = 9 Vb = U₄ + Cb₄ = 7 + 6 = 13

U₃ = Vc - Cc₃ = 15 – 7 = 8 Vc = U₅ + Cc₅ = 4 + 11 = 15

U₄ = Vc - Cc₄ = 15 – 8 = 7 Vd = U₄ + Cd₄ = 7 + 5 = 12

U₅ = Va - Ca₅ = 8 – 4 = 4 Ve = U₅ + Ce₅ = 4 + 0 = 4

Тогда найдем потенциалы в незаполненных клетках по формуле, имеем

Vb - U₁ – Cb₁ = 13 – 4 – 4 = 5

Vс - U₁ – Cс₁ = 15 – 4 – 10 = 1

Vd - U₁ – Cd₁ =12 – 4 – 5 = 3

Ve - U₁ – Ce₁ = 4 – 4 – 0 = 0 норма

Va - U₂ – Ca₂ = 8 – 9 – 8 = -9 норма

Vc - U₂ – Cc₂ = 15 – 9 – 8 = -2 норма

Vd - U₂ – Cd₂ = 12 – 9 – 7 = -4 норма

Ve - U₂ – Ce₂ = 4 – 9 – 0 = -5 норма

Va - U₃ – Ca₃ = 8 – 8 – 5 = -5 норма

Vb - U₃ – Cb₃ = 13 – 8 – 9 = -4 норма

Vd - U₃ – Cd₃ = 12 – 8 – 8 = -4 норма

Ve - U₃ – Ce₃ = 4 – 8 – 0 = -4 норма

Va - U₄ – Ca₄ = 8 – 7 – 7 = -6 норма

Ve - U₄ – Ce₄ = 4 – 7 – 0 = -3 норма

Vb - U₅ – Cb₅ = 13 - 4 – 6 = 3

Vd - U₅ – Cd₅ = 12 - 4 – 6 = 2

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

	1		2		3		4		5		номерная емкость АТС
A	33-x	4	0	8	0	5	x	7	60	4	93
B	x	4	44	4	0	9	28-x	6	0	6	72
C	0	10	0	8	72	7	6	8	26	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		0		42		42
номерная емкость района	33		44		72		87		128

Здесь X = 28 Имеем новую таблицу и производим перерасчет на оптимальность.

	1		2		3		4		5		номерная емкость АТС
A	5	4	0	8	0	5	28	7	60	4	93
B	28	4	44	4	0	9	0	6	0	6	72
C	0	10	0	8	72	7	6	8	26	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		0		42		42
номерная емкость района	33		44		72		87		128

S = 5*4+28*4+44*4+72*7+28*7+6*8+53*5+60*4+26*11 = 1847 у.е

Vа Vb Vc Vd Vе

U₁ U₂ U₃ U₄ U₅

Проверим по методу потенциалов план на соответствие

U₁ = 4 Va = Ca₁ + U₁ = 4 + 4 = 8

U₂ = Vb - Cb₂ = 8 – 4 = 4 Vb = U₁ + Cb₁ = 4 + 4 = 8

U₃ = Vc - Cc₃ = 9 – 7 = 2 Vc = U₄ + Cc₄ = 1 + 8 = 9

U₄ = Va - Ca₄ = 8 – 7 = 1 Vd = U₄ + Cd₄ = 1 + 5 = 6

U₅ = Va - Ca₅ = 8 – 4 = 4 Ve = U₅ + Ce₅ = 4 + 0 = 4

Тогда найдем потенциалы в незаполненных клетках по формуле, имеем

Vс - U₁ – Cс₁ = 9 – 4 – 10 = -5 норма

Vd - U₁ – Cd₁ = 6 – 4 – 5 = -3 норма

Ve - U₁ – Ce₁ = 4 – 4 – 0 = 0 норма

Va - U₂ – Ca₂ = 8 – 4 – 8 = -4 норма

Vc - U₂ – Cc₂ = 9 – 4 – 8 = -3 норма

Vd - U₂ – Cd₂ = 6 – 4 – 7 = -4 норма

Ve - U₂ – Ce₂ = 4 – 4 – 0 = 0 норма

Va - U₃ – Ca₃ = 8 – 2 – 5 = 1 ложь

Vb - U₃ – Cb₃ = 8 – 2 – 9 = -3 норма

Vd - U₃ – Cd₃ = 6 – 2 – 8 = -4 норма

Ve - U₃ – Ce₃ = 4 – 2 – 0 = 2 ложь

Vb - U₄ – Cb₄ = 8 – 1 – 6 = 1 ложь

Ve - U₄ – Ce₄ = 4 – 1 – 0 = 3 ложь

Vb - U₅ – Cb₅ = 8 - 4 – 6 = -2 норма

Vd - U₅ – Cd₅ = 6 - 4 – 6 = -4 норма

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

	1		2		3		4		5		номерная емкость АТС
A	5	4	0	8	0	5	2 8-x	7	60+x	4	93
B	28	4	44	4	0	9	0	6	0	6	72
C	0	10	0	8	72	7	6	8	26	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		x		42-x		42
номерная емкость района	33		44		72		87		128

Здесь X = 28. И получаем новую таблицу, для которой повторяется расчет на оптимальность методом потенциалов. Имеем

	1		2		3		4		5		номерная емкость АТС
A	5	4	0	8	0	5	0	7	88	4	93
B	28	4	44	4	0	9	0	6	0	6	72
C	0	10	0	8	72	7	6	8	26	11	104
D	0	5	0	7	0	8	53	5	0	6	53
E	0		0		0		28		14		42
номерная емкость района	33		44		72		87		128

S = 5*4+28*4+44*4+72*7+6*8+53*5+28*0+88*4+26*11+14*0 = 1763 у.е

Vа Vb Vc Vd Vе

U₁ U₂ U₃ U₄ U₅

Проверяем план на оптимальность и повторяем процедуру до получения оптимальности-

3. Порядок выполнения работы

3.1. Получить у преподавателя исходные данные для работы.

3.2. Построить опорные темя способами

3.3. Провести оптимизацию методом потенциалов

3.4. Используя ЭВМ прверить полученный результат

4. Содержание отчета

4.1. Цель работы.

4.2. Исходные данные.

4.3. Результаты расчета.

ЛИТЕРАТУРА

1. Таха X. Введение в исследование операций. -М.: Мир, 1996.

2. Балашевич В.А. Ооновы математического программирования. -Мн.: Вышэйшая школа, 1985.