Материал: 1823

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

ближайшему целому числу Ki0+1. Для нахождения этих чисел,

решаются симплекс-методом		следующие две задачи линейного
программирования:
F		n
F		c j x j max,
		j 1
n		j 1
n
aij x j bi (i			1, m		),
(I )
j 1
xi 0 Ki 0 ,

	0( j 1, n);
x j	0( j 1, n);
F		n
F		c j x j max,
		j 1
n		j 1
n
aij x j bi (i				1, m		),
(II )
j 1	Ki 0 1,
xi 0	Ki 0 1,

	0( j 1, n);
x j	0( j 1, n);

Здесь возможен один из следующих четырёх случаев:

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

2.Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматривается вторая задача и в её оптимальном плане выбирается одна из компонент, значение которой равно дробному числу, и строятся две задачи, аналогичные задачам (I) и (II).

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

взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные задачам (I) и (II).

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

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану X0 задачи (5.1)- (5.2), а каждая соединённая с ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. На каждом шаге выбирается та вершина, для которой значение целевой функции наибольшее. Если на некотором шаге будет получен план, имеющих целочисленные компоненты, и значение функции на нём будет больше или равно значений функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нём является оптимальным.

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

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

F 2x1 x2

при условиях:

6x1 4x2 x3		24,
	x4	9,
3x1 3x2
	x3	3,
x1 3x2

x j 0, x j 0( j 1,5)

Решение. В результате решения задачи симплекс-методом без учёта условия целочисленности переменных получен следующий оптимальный план X0=(18/5,3/5,0,0,24/5), при котором значение функции F=39/5. Далее выбирается одна из дробных переменных, например x1, которая в оптимальном плане исходной задачи будет принимать значение, либо x1 3 , либо x1 4.

F 2x x

max,

F 2x x

max,

6x1 4x2 x3

24,

6x1 4x2 x3 24,

x4 9,

(I ) 3x1 3x2

(II ) 3x1 3x2

x1 3x2 x3

x1 3x2

x3 3,

3, x

0( j

1,5);

4, x

0( j

1,5).

Задача (I) имеет оптимальный план X1(1) (3,3/ 2,0,9 / 2,3/ 2) , на котором значение целевой функции F=15/2. Задача (II) неразрешима. Далее исследуется задача (I). Так как среди компонент оптимального плана есть дробные числа, то для одного из них,

например x2, вводятся дополнительные ограничения - x2 1 ,

x2 2.

Затем решаются следующие две задачи:

F 2x1 x2

max,

F 2x1 x2

max,

24,

3x2

x4 9,

3x1

(III)

x1 3x2 x3 3,

(IV )

x1 3x2 x3 3,

3, x2

4, x2

0( j

1,5);

1,5).

Задача (IV) неразрешима, а задача (III) имеет оптимальный

план

X (1)

(3,1,2,3,3) ,

на

котором

значение

целевой функции

F( X

(1) 7

. Что и является решением задачи.

6. Сетевые модели

Сетевой моделью (другие названия: сетевой график, сеть)

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

Математический аппарат сетевых моделей базируется на теории графов. Графом называется совокупность двух конечных множеств: множества точек, которые называются вершинами (отображаются кружочками, точками и др.), и множества пар вершин, которые называются ребрами (дугами, соединяющими вершины графа). Если рассматриваемые пары вершин являются упорядоченными, т.е. на каждом ребре задаётся направление, то граф называется ориентированным; в противном случае – неориентированным. Последовательность неповторяющихся рёбер, ведущая от некоторой вершины к другой, образует путь. Граф называется связным, если для любых двух его вершин существует путь, их соединяющий, в противном случае граф называется несвязным. В экономике чаще всего используются два вида графов: дерево и сеть. Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. Сеть – это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида «сеть» [1].

С помощью сетевого планирования и управления (СПУ)

решаются различные оптимизационные экономические задачи,

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

			1
		3	7
	5			6
	5		8
			8
		3	4
	6	4		9
1	2	5	10	11
			9
	3	6		3
		4	9
		7		5

Рис. 6.1. Сетевая модель.

Основные понятия сетевой модели: событие, работа и путь. На рис. 6.1 графически представлена СМ, состоящая из 11 событий и 16 работ, продолжительность выполнения которых указана над работами.

Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом представлении изображается стрелкой, которая соединяет два события. Она обозначается парой заключённых в скобки чисел (i,j), где i –

Смотрите также:


«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
«ДОХОДЫ, РАСХОДЫ И ПРИБЫЛЬ КОММЕРЧЕСКОГО БАНКА.»
Значение, сущность и содержание социально — педагогической деятельности в организации для детей-сирот и детей, оставшихся без попечения родителей
Проактивные методы PR-деятельности российских авиационных компаний «Россия», «Азимут»
__RGR2
__RGR2
_11_А. Франс для эл версии
_3 тема - Диффузия
_индив анализ данных