Минимизировать общую стоимость всех перевозок

 

L = (8)

при условиях

и (9)

I. Первое допустимое базисное решение (допустимый план) построим по правилу «северо-западного» угла.

а) попытаемся удовлетворить потребности первого пункта назначения В₁ запасами первого пункта отправления, , примем . При этом запасы А₁ окажутся полностью исчерпанными, а потребности В₁ сокращенными до ; .

Исключим временно из рассмотрения строку А₁ и приходим к случаю, когда суммарное число пунктов назначения и отправления уменьшилось на единицу.

б) далее все повторим и заполняем таблицу 1.

Табл. 1

Произ вод ство	Потребление
	45 ¹	³	²	²	º	p1 = 0
	14 3	27 ²	14 4	³	º	p2 = 2
	4	²	26 ³	35 ¹	9 º	p3 = 1
	q1 = 1	q2 = 0	q3 = 2	q4 = 0	q 5 = -1

L = 45 · 1 + 14 · 3 + 27 · 2 + 14 · 4 + 26 · 3 + 35 ·1 + 9 · 0 = 310

II. Для решения транспортной задачи применяем метод «потенциалов».

Обозначим через = (p₁, p₂, p₃, q₁, q₂, q₃, q₄, q₅) – вектор симплексных множителей или потенциалов.

Составим систему для нахождения потенциалов, учитывая, что для базисных (занятых) клеток∆ _ij = 0,

где ∆ _ij = p_i + q_j – c_ij , i=1, m; j=1, n.

p₁ + q₁ = 1 p₃ + q₃ = 3

p₂ + q₁ = 3 p₃ + q₄ = 1

p₂ + q₂ = 2 p₃ + q₅ = 0

p₂ + q₃ = 4

Один из потенциалов (любой) можно выбрать произвольно, так как в системе (9) одно из уравнений линейно зависит от остальных.

Пусть p₁ = 0.

Имеем: q₁ = 1; p₂ = 3 – 1 = 2; q₂ = 2 – 2 = 0; q₃ = 4 – 2 = 2;

p₃ = 3 – 2 = 1; q₄ = 1 – 1 = 0; q₅ = 0 – 1 = - 1;

Значение потенциалов занесем в табл. 1.

Вычисляем оценки всех свободных клеток.

 

∆ 12 = p1 + q2 – c12 = 0 – 3 = - 3; ∆ 14 = p1 + q4 – c14 = 0 + 0 – 2 = - 2; ∆ 24 = p2 + q4 – c24 = - 1; ∆ 31 = p3 + q1 – c31 = 1 + 1 - 4 = -2;

∆ 13 = p1 + q3 – c13 = 0 + 2 – 2 = 0; ∆ 15 = p1 + q5 – c15 = - 1; ∆ 25 = p2 + q5 – c25 = 1; ∆ 32 = p3 + q2 – c32 = 1 – 2 = - 1;

max (∆ _ij > 0) = ∆ ₂₅ = 1.

Для найденной свободной клетки строим цикл пересчета, то есть замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин которой находится в данной свободной клетке, а остальные в занятых клетках. Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «-».

-14		+		14-(p=9)		(p=9)
+26		9-		26+(p=9)		9-(p=9)

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

Найдем новые потенциалы для второго допустимого базисного решения, записанного в таблице 2.

Табл. 2

	45 ¹	³	²	²	º	p1 = 0
	14 ³	27 ²	5 4	³	9 º	p2 = 2
70	4	²	35 ³	35 ¹	º	p3 = 1
	q1 = 1	q2 = 0	q3 = 2	q4 = 0	q5 = -2

p₁ + q₁ = 1 p₁ = 0

p₂ + q₂ = 2 q₁ = 1

p₂ + q₁ = 3 p₂ = 2

p₂ + q₃ = 4 q₂ = 0

 

p₂ + q₅ = 0 q₃ = 2

p₃ + q₃ = 3 p₃ = 1

p₃ + q₄ = 1 q₄ = 0 q₅ = -2

Найдем оценки свободных клеток.

∆ ₁₂ = p₁ + q₂ – c₁₂ = - 1; ∆ ₂₄ = p₂ + q₄ – c₂₄ = - 1;

∆ ₁₃ = p₁ + q₃ – c₁₃ = 0; ∆ ₃₁ = p₃ + q₁ – c₃₁ = - 2;

∆ ₁₄ = p₁ + q₄ – c₁₄ = - 2; ∆ ₃₂ = p₃ + q₂ – c₃₂ = - 2;

∆ ₁₅ = p₁ + q₅ – c₁₅ = - 2; ∆ ₃₅ = p₃ + q₅ – c₃₅ = - 1.

Нет неизвестных, для которых∆ _ij > 0, поэтому в таблице 2 записано оптимальное решение X = .

При этом суммарная стоимость перевозки

L = 45 · 1 + 14 · 3 + 27 · 2 + 5 · 4 + 9 · 0 + 35 ·3 + 35 · 1 = 301.

Контрольные вопросы по теме 4

1. Транспортная задача.

2. Сбалансированные и несбалансированные транспортные модели.

3. Определение начального плана.

4. Метод потенциалов нахождения оптимального плана транспортной задачи.

5. Примеры экономических задач, сводящихся к транспортным моделям.

6. Задачи назначения и распределения.

Задание по теме 4

4.1. Составить математическую модель транспортной задачи по исходным данным:

С = - матрица транспортных издержек, A = - вектор объемов производства, B = (34, 40, 38, 53) - вектор объемов потребления.

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

Найти оптимальное решение транспортной задачи методом потенциалов.

Литература: 1, 3, 4, 5, 6, 8, 10, 11, 12, 15.

Тема 5. МНОГОКРИТЕРИАЛЬНАЯ ОПТИМИЗАЦИЯ

Примеры решения типовых задач

 

5.1. Векторная оптимизация.

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

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

Найти вектор :

;

.

Для решения используем метод последовательных уступок. Алгоритм метода:

1. Критерии нумеруются в порядке убывания важности.

2. Определяется оптимальное значение критерия . Лицом, принимающим решение, устанавливается величина уступки по этому критерию.

3. Решается задача по критерию с дополнительным ограничением .

Далее пункты 2 и 3 повторяются для критериев , , … .

К недостаткам метода можно отнести то, что полученное решения не всегда принадлежит области компромиссов.

Методом последовательных уступок решим оптимизационную
задачу

В задаче критерии пронумерованы в порядке убывания важности. Считаем, что уступка по первому критерию составляет 15% от его оптимального значения.

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

; .

Оптимальное значение ; ;

б) В соответствии с условием задачи находим величину уступки

.

Дополнительное ограничение примет вид

в) Решаем задачу.

; .

Получим оптимальное решение при этом

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

1. Сущность глобального и локального критериев оптимальности.

2. Общая формулировка многокритериальной задачи.

3. Решение методом последовательных уступок.

 

Задание по теме 5

5.1. Решить задачу двухкритериальной оптимизации методом последовательных уступок. Для простоты рассмотреть задачи ли-нейного программирования (решать любым методом).

Исходные данные: F(Х) ={f₁ = 2x₁ + 5x₂, f₂ = 4: p₁: x₁ + 10x₂}®max.

На переменные наложены ограничения:

Уступка по первому критерию составляет 2·p₃ % от его оптимального значения. Критерии пронумерованы в порядке убывания важности.

Литература: 2, 20, 24.

Тема 6. МОДЕЛИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Примеры решения типовых задач

6.1. Распределение капитальных вложений.

Нелинейная задача распределения ресурсов: предположим, что задано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначим через ( ) прирост мощности или прибыли на j предприятии, если оно получит рублей капитальных вложений. Требуется найти такое распределение капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли при ограничениях по общей сумме капитальных вложений , причем считаем, что все переменные принимают только целые неотрицательные значения = 0, или 1, или 2, или 3, ….. Функции ( ) считаем заданными.

 

Метод динамического программирования:

Введем параметр состояния ξ - количество рублей, выделенных нескольким предприятиям. Функцию состояния F_k(ξ ) определяем как максимальную прибыль на первых k предприятиях, если они вместе получают ξ рублей.

Параметр ξ изменяется от 0 до b.

Если из ξ рублей k –ое предприятие получило x_k рублей, то остальные (ξ - x_k) рублей надо распределить между предприятиями от первого до (k – 1) так, чтобы была получена максимальная прибыль F_{k –1} (ξ - x_k).

Прибыль k предприятий тогда будет равна f_k(x_k) + F_{k –1} (ξ - x_k).

Надо выбрать такое значение x_k между 0 и ξ, чтобы эта сумма была максимальной. Приходим к рекуррентному соотношению

F_k (ξ ) { f_k(x_k) + F_{k –1} (ξ - x_k)} для k =2, 3, 4 …n,

Если k =1, то F₁(ξ ) = f₁(ξ ).

Исходные данные:

Табл. 1

( )
( )
( )
( )

Производственное объединение состоит из n = 4 предприятий. Общая сумма капитальных вложений b = 700 тыс. руб. Выделяемые предприятиям суммы кратны 100 тыс. рублей. Прирост прибыли ( ) заданы в таблице. Например, число 25 во второй строке означает, что если второе предприятие получит 200 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 25 тыс. руб.

Для заполнения Табл.2. находим сумму F₁(ξ – ) = (ξ – ) и ( ). На каждой северо-восточной диагонали находим наибольшее число, то есть F₂(ξ ) { ( ) + F₁(ξ – )}. Отметим его «*»

Табл. 2

ξ –
	F1(ξ - )
	( )
		13*
		25*
		37*	47*	57*
				67*	77*

Для чисел, указанных «*» находим соответствующее значение (ξ ). Заполняем Таблицу 3.

Табл. 3

ξ
F2(ξ )
(ξ )

Продолжим процесс вычислений: находим F₃(ξ ), (ξ ) и заполняем Табл. 4 и Табл. 5 так же, как Табл. 2 и Табл.3.

 

 

Табл. 4

ξ –
	F2(ξ - )
			13*	25*	37*	47*	57*	67*	77*

Табл. 5

Ξ
F3(ξ )
(ξ )

В Таблице 6 заполняем только одну диагональ для ξ = 700.

 

Табл. 6

ξ –
	F3 (ξ - )
							93*

Z max = 93 тыс. руб., причем четвертому предприятию должно быть выделено * = (700) = 200 тыс. руб.

На долю остальных предприятий остается 500 тыс. руб. Из Табл.5 видно, что третьему предприятию должно быть выделено * = (700- *) = *(500) = 0 руб.

Продолжая обратный процесс, находим * = (700- *- *) = (700 – 200 - 0) = (500) = 300 тыс. руб.

На долю первого предприятия остается * = 700- *- *- * = 700 – 200 – 0 - 300 = 200 тыс. руб.

Следовательно, наилучшим является следующее распределение капитальных вложений по предприятиям

* = 200 тыс. руб.; * = 300 тыс. руб.;

* = 0 руб.; * = 200 тыс. руб.

Оно обеспечивает производственному объединению наибольший возможный прирост прибыли равный 93 тыс. руб.

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

f₁( *) = f₁(200) = 20 тыс. руб.; f₂( *) = f₂(300) = 37 тыс. руб.;

f₃( *) = f₃(0) = 0 руб.; f₄( *) = f₄(200) = 36 тыс. руб.

Проверка показывает, что

f₁( *) + f₂( *) + f₃( *) + f₄ ( *)= 93 тыс. руб.

Контрольные вопросы по теме 6

1. Общая постановка задачи динамического программирования.

2. Принцип оптимальности и уравнения Беллмана.

3. Составление математической модели.

4. Общая схема применения метода динамического программирования.

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

 

 

Задание по теме 6

6.1. Методом динамического программирования решить задачу распределения капитальных вложений между 4 предприятиями производственного объединения. Максимизировать суммарный прирост прибыли (или мощности). Общая сумма капитальных вложений равна 700 денежных единиц. Суммы, выделяемые предприятиям кратны 100 ден.ед.

Значение функций f_i(x_i) приведены в таблице:

x
f1(x1)						р3
f2(x2)			p2
f3(x3)		р1
f4(x4)

Литература: 1, 3, 4, 5, 8, 15, 24.

Тема 7. МАТЕМАТИЧЕСКИЕ МЕТОДЫ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ. ОПТИМИЗАЦИЯ СЕТЕВЫХ МОДЕЛЕЙ

Примеры решения типовых задач

7.1. Сетевые методы решения экономических задач.

Сетевой график задан в виде следующей таблицы:

Шифр работ

i

j

Продолжительность работ

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

Решение

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

Определяем основные параметры сетевого графика.

I. Ранние сроки свершения событий находим методом динамического программирования.

.

Для нашего случая имеем:

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

.

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

Аналогично, находим, что работы (4, 5) и (1, 4) являются критическими.

На графике отмечены работы, принадлежащие критическому пути, это работы (1, 4), (4, 5), (5, 6), (6, 9).

Определим другие параметры сетевого графика.

II. Найдем поздние сроки свершения события i:

,

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

Например,

III. Найдем резерв времени события (i).

Резервы всех критических событий равны нулю.

IV. Определим временные параметры работ.

Ранний срок начала работы (i, j):

.

Например,

Ранний срок окончания работы (i, j):

или .

 

Например,

Поздний срок окончания работы совпадает с поздним сроком свершения ее конечного события

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

или

Полный резерв времени работы – максимально возможный запас времени, на который можно отсрочить начало работы или увеличить продолжительность ее выполнения при условии, что конечное для данной работы событие наступит не позднее его позднего срока

.

Например, .

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

Свободный резерв времени

Например,

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

Например,

Только отдельные работы проекта обладают свободным резервом времени.

Контрольные вопросы по теме 7

1. Основные понятия.

2. Правила построения сетевых графиков.

3. Расчет временных параметров сетевого графика.

Задание по теме 7

7.1. Сетевой график задан в виде следующей таблицы:

 

шифр работ

i

j

продолжительность работ

р1

p2

р3

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

Литература: 1, 2, 4, 6, 24.

 

РАЗДЕЛ 3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ С ЭЛЕМЕНТАМИ
НЕОПРЕДЕЛЁННОСТИ

⇐ Предыдущая123456Следующая ⇒

Поделиться:

Популярное:

1. Бесполезность всех остальных способов приближения к Аллаху
2. В обосновании какого конкретного решения исходным показателем предприятия является себестоимость единицы продукции?
3. Виды осуществляемых АТП перевозок грузов
4. Визуальное определение оптимальных режимов тиснения для всех испытываемых покровных материалов.
5. Вклад различных видов энергии в общую энергию притяжения молекул
6. Вопрос 8. Капитал — стоимость, авансируемая в производство с целью получения прибыли.
7. Вопрос №3. Таможенная стоимость товара.
8. Восстановительная стоимость дает возможность учитывать стоимость ОПФ с уровнем официальной инфляции, которая искажает действительную стоимость ОПФ.
9. Вот уже две тысячи лет евангелие проповедуется во всех краях. Кто-то послан с проповедью и к твоим современникам, к твоим землякам. Но кто, если не ты?
10. Выбор марок и сечений проводников на всех участках
11. Выкуп. Получая землю, крестьяне были обязаны оплатить ее стоимость. Рыночная цена
12. Г. Гегель: Последняя цель всемирной истории – это свобода всех