Для чего применяется метод северо западного угла. Транспортная задача: метод Северо-Западного угла. Опорное решение транспортной задачи

Опорное решение транспортной задачи

Методы построения начального опорного решения

Метод северо-западного угла.

Транспортная задача: метод Северо-Западного угла

Формирование опорного плана методом Северо-Западного угла

ЗАКРЫТАЯ ТРАНСПОРТНАЯ ЗАДАЧА

Решение транспортной задачи методом северо-западного угла

Метод вычеркивания

Метод северо-западного угла

Метод минимальной стоимости

04.04.2019

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

Теорема 38.2 Свойство системы ограничений транспортной задачи

Ранг системы векторов-условий транспортной задачи равен N=m+n-1 (m — поставщики, n-потребители)

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

Ввиду того, что ранг системы векторов-условий транспортной задачи равен m+n — 1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невырожденного опорного решения равняется m+n-1, а для вырожденного опорного решения меньше m+n-1

Цикл

Циклом называется такая последовательность клеток таблицы транспортной задачи (i 1 , j 1),(i 1 , j 2),(i 2 , j 2),...,(i k , j 1), в которой две и только две соседние клетки распложены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

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

Теорема 38.3
Допустимое решение транспортной задачи X=(x ij) является опорным тогда и только тогда, когда из занятых клеток таблицы нельзя образовать ни одного цикла.

Метод вычеркивания позволяет проверить, является ли данное решение транспортной задачи опорным.

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

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

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

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

Примеры "вычеркнутого" (опорного) и "не вычеркнутого" (не опорного решений):

Логика вычеркивания :

Вычеркнуть все столбцы, в которых всего одна занятая клетка (5 0 0), (0 9 0)
Вычеркнуть все строки, в которых всего одна занятая клетка (0 15), (2 0)
Повторить цикл (7) (1)

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

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

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

Пример 38.1

Составить опорное решение, используя метод северо-западного угла.

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

Пример : так как его запасы a 1 =100 меньше запросов первого потребителя b 1 =100, то в клетку (1,1) записываем перевозку x 11 =100 и исключаем из рассмотрения поставщика.
Определяем оставшиеся неудовлетворенными запросы 1-го потребителя b 1 = 150-100=50.

2. Распределяем запасы 2-го поставщика.
Так как его запасы a 2 = 250 больше оставшихся неудовлетворенными запросов 1-го потребителя b 1 =50, то в клетку (2,1) записываем перевозку x 21 =50 и исключаем из рассмотрения 1-го потребителя.
Определяем оставшиеся запасы 2-го поставщика a 2 = a 2 — b 1 = 250-50=200. Так как оставшиеся запасы 2-го поставщика равны запросам 2-го потребителя, то в клетку (2,2) записываем x 22 =200 и исключаем по своему усмотрению либо 2-го поставщика, либо 2-го потребителя. В нашем примере мы исключили 2-го поставщика.
Вычисляем оставшиеся неудовлетворенными запросы второго потребителя b 2 =b 2 -a 2 =200-200=0.

	150	200	100	100
100	100
250	50	200			250-50=200 200-200=0
200
	150-100-50=0

3. Распределяем запасы 3-го поставщика.
Важно! В предыдущем шаге у нас был выбор исключать поставщика или потребителя. Так как мы исключили поставщика, то запросы 2-го потребителя все же остались (хоть и равны нулю).
Мы должны записать оставшиеся запросы равные нулю в клетку (3,2)
Это связано с тем, что если в очередную клетку таблицы (i,j) требуется поставить перевозку, а поставщик с номером i или потребитель с номером j имеет нулевые запасы или запросы, то ставится в клетку перевозка, равная нулю (базисный нуль), и после этого исключается из рассмотрения либо соответствующий поставщик, либо потребитель.
Таким образом, в таблицу заносятся только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми.

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

Так как в предыдущем шаге мы исключили из рассмотрения второго поставщика, то в клетку (3,2) записываем x 32 =0 и исключаем второго потребителя.

Запасы 3-го поставщика не изменились. В клекту (3,3) записываем x 33 =100 и исключаем третьего потребителя. В клетку (3,4) записываем x 34 =100. Ввиду того, что наша задача с правильным балансом, запасы всех поставащиков исчерпаны и запросы всех потребителей удовлетворены полностью и одновременно.

Опорное решение
	150	200	100	100
100	100
250	50	200
200		0	100	100

4. Проверяем правильность построения опорного решения.
Число занятых клеток должно быть равно N=m(поставщики)+m(потребители) — 1=3+4 — 1=6.
Применяя метод вычеркивания, убеждаемся, что найденное решение является "вычеркиваемым" (звездочкой отмечен базисный нуль).

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

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(c ij).

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

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

Пример 38.2

Используя метод минимальной стоимости построить начальное опорное решение транспортной задачи.

1. Запишем отдельно матрицу стоимостей для того, чтобы было удобнее выбирать минимальные стоимости.

2. Среди элементов матрицы стоимостей выбираем наименьшую стоимость C 11 =1, отмечаем ее кружочком. Данная стоимость имеет место при перевозке груза от 1-го поставщика 1-му потребителю. В соответствующую клетку записываем максимально возможный объем перевозки:
x 11 = min {a 1 ; b 1 } = min {60; 40} =40 т.е. минимум между запасами 1-го поставщика и запросами 1-го потребителя.

2.1. Запасы 1-го поставщика уменьшаем на 40.
2.2. Исключаем из рассмотрения 1-го потребителя, так как его запросы полностью удовлетворены. В матрице C вычеркиваем 1-ый столбец.

3. В оставшейся части матрицы C минимальной стоимостью является стоимость C 14 =2. Максимально возможная перевозка, которую можно осуществить от 1-го поставщика 4-му потребителю равна x 14 = min {a 1 "; b 4 } = min {20; 60} = 20 , где a 1 со штрихом это оставшиеся запасы первого поставщика.
3.1. Запасы 1-го поставщика исчерпаны, поэтому исключаем его из рассмотрения.
3.2. Запросы 4-го потребителя уменьшаем на 20.

4. В оставшейся части матрицы С минимальная стоимость C 24 =C 32 =3. Заполняем одну из двух клеток таблицы (2,4) или (3,2). Пусть в клетку запишем x 24 = min {a 2 ; b 4 } = min {80; 40} =40 .
4.1. Запросы 4-го потребителя удовлетворены. Исключаем его из рассмотрения вычеркивая 4-й столбец в матрице C.
4.2. Уменьшаем запасы 2-го поставщика 80-40=40.

5. В оставшейся части матрицы C минимальная стоимость C 32 =3. Запишем в клетку (3,2) таблицы перевозку x 32 = min {a 3 ; b 2 } = min {100; 60} =60 .
5.1. Исключим из рассмотрения 2-го потребителя. Из матрицы C исключаем 2-ой столбец.
5.2. Уменьшим запасы 3-го поставщика 100-60=40

6. В оставшейся части матрицы C минимальная стоимость C 33 =6. Запишем в клетку (3,3) таблицы перевозку x 33 = min {a 3 "; b 3 } = min {40; 80} =40
6.1. Исключим из рассмотрения 3-го поставщика, а из матрицы C 3-ю строку.
6.2. Определяем оставшиеся запросы 3-го потребителя 80-40=40.

7. В матрице C остался единственный элемент C 23 =8. Записываем в клетку таблицы (2,3) перевозку X 23 =40.

8. Проверяем правильность построения опорного решения.
Число занятых клеток таблицы равно N=m+n — 1=3+4 -1.
Методом вычеркивания проверяем линейную независимость векторов-условий, соответствующих положительным координатам решения. Порядок вычеркивания показан на матрице X:

Вывод: Решение методом минимальной стоимости (таблица 38.3) является "вычеркиваемым" и, следовательно опорным.

Составить экономико-математическую модель и решить задачу с помощью надстройки «Поиск решения».

Решение:

Экономико-математическая модель:

Целевая функция:

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

Ограничения:

x ij – равное 1 показывает, что i-го работника необходимо назначить на выполнение j-ой работы.

Экономико-математическая модель задачи составлена. Решим эту задачу с использованием надстройки Excel «Поиск решения».

На рисунке 1 представлен ход работы утилиты «Поиск решения».

Рисунок 1 – Ход работы утилиты Поиск решения

На рисунке 2 представлен результат решения задачи.

Рисунок 2 – Результат решения задачи

Вывод: из рисунка 2 следует, что для того, чтобы общая величина затрат была минимальной необходимо для выполнения работы А1 назначить работника В4, А2 – В3, А3 – В5, А4 – В1, А5 – В2, при этом суммарные затраты будут минимальны и составят 25 ед.

Задача 2 Транспортная задача

Исходная информация транспортной задачи представлена в таблице 2.

Таблица 2 – Исходные данные

	В1	В2	В3	В4	Запасы
А1
А2
А3
Потребности

Определить:

1. приближенный план, схему перевозок, а также его стоимость методом северо-западного угла;

2. приближенный план, схему перевозок, а также его стоимость методом минимального элемента;

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

Метод северо-западного угла

Проверим необходимое и достаточное условие разрешимости задачи.

Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 3 (120-117). Тарифы перевозки единицы груза из базы во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную таблицу 3.

Таблица 3 – Распределительная таблица

Первый опорный план начинается заполняться с верхнего левого угла (таблица 4).

Таблица 4 – Опорный план 1

	В1	В2	В3	В4	В5		Запасы
А1						u 1 =0

А2						u 2 =-2

А3						u 3 =-4

	v 1 =3	v 2 =6	v 3 =10	v 4 =5	v 5 =4
Потребности

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 3*30 + 6*10 + 4*17 + 8*23 + 6*7 + 1*30 + 0*3 = 474

u 1 + v 2 = 6; 0 + v 2 = 6; v 2 = 6

u 2 + v 2 = 4; 6 + u 2 = 4; u 2 = -2

u 2 + v 3 = 8; -2 + v 3 = 8; v 3 = 10

u 3 + v 3 = 6; 10 + u 3 = 6; u 3 = -4

u 3 + v 4 = 1; -4 + v 4 = 1; v 4 = 5

u 3 + v 5 = 0; -4 + v 5 = 0; v 5 = 4

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;3): 0 + 10 > 5; ∆ 13 = 0 + 10 - 5 = 5

(1;4): 0 + 5 > 2; ∆ 14 = 0 + 5 - 2 = 3

(1;5): 0 + 4 > 0; ∆ 15 = 0 + 4 - 0 = 4

(2;5): -2 + 4 > 0; ∆ 25 = -2 + 4 - 0 = 2

max(5,3,4,2) = 5

Выбираем максимальную оценку свободной клетки (1;3): 5

Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 5).

Таблица 5 – Цикл 1

	В1	В2	В3	В4	В5
А1						u 1 =0
		-		+
А2						u 2 =-2
		+		-
А3						u 3 =-4

	v 1 =3	v 2 =6	v 3 =10	v 4 =5	v 5 =4

Цикл приведен в таблице (1,3 → 1,2 → 2,2 → 2,3).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план (таблица 6).

Таблица 6 – Опорный план 2

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =3

А3						u 3 =1

	v 1 =3	v 2 =1	v 3 =5	v 4 =0	v 5 =-1

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u i , v j . по занятым клеткам таблицы, в которых u i + v j = c ij , полагая, что u 1 = 0.

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 2 + v 3 = 8; 5 + u 2 = 8; u 2 = 3

u 2 + v 2 = 4; 3 + v 2 = 4; v 2 = 1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(2;1): 3 + 3 > 3; ∆ 21 = 3 + 3 - 3 = 3

(2;5): 3 -1 > 0; ∆ 25 = 3 -1 - 0 = 2

Выбираем максимальную оценку свободной клетки (2;1): 3

Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 7).

Таблица 7 – Цикл 2

	В1	В2	В3	В4	В5
А1						u 1 =0
-				+
А2						u 2 =3
+				-
А3						u 3 =1

	v 1 =3	v 2 =1	v 3 =5	v 4 =0	v 5 =-1

Цикл приведен в таблице (2,1 → 2,3 → 1,3 → 1,1).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 13. Прибавляем 13 к объемам грузов, стоящих в плюсовых клетках и вычитаем 13 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план 3 (таблица 8).

Таблица 8 – Опорный план 3

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =0

А3						u 3 =1

	v 1 =3	v 2 =4	v 3 =5	v 4 =0	v 5 =-1

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5

u 3 + v 3 = 6; 5 + u 3 = 6; u 3 = 1

u 3 + v 4 = 1; 1 + v 4 = 1; v 4 = 0

u 3 + v 5 = 0; 1 + v 5 = 0; v 5 = -1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(3;2): 1 + 4 > 3; ∆ 32 = 1 + 4 - 3 = 2

Выбираем максимальную оценку свободной клетки (3;2): 3

Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 9).

Таблица 9 – Цикл 3

	В1	В2	В3	В4	В5
А1						u 1 =0
-				+
А2						u 2 =0
+		-
А3						u 3 =1
		+		-
	v 1 =3	v 2 =4	v 3 =5	v 4 =0	v 5 =-1

Цикл 3 приведен в таблице (3,2 → 3,3 → 1,3 → 1,1 → 2,1 → 2,2).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 7. Прибавляем 7 к объемам грузов, стоящих в плюсовых клетках и вычитаем 7 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план 4.

Таблица 10 – Опорный план 4

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =0

А3						u 3 =-1

	v 1 =3	v 2 =4	v 3 =5	v 4 =2	v 5 =1

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 2 + v 1 = 3; 3 + u 2 = 3; u 2 = 0

u 2 + v 2 = 4; 0 + v 2 = 4; v 2 = 4

u 3 + v 5 = 0; -1 + v 5 = 0; v 5 = 1

u 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + v j > c ij

(1;5): 0 + 1 > 0; ∆ 15 = 0 + 1 - 0 = 1

(2;5): 0 + 1 > 0; ∆ 25 = 0 + 1 - 0 = 1

Выбираем максимальную оценку свободной клетки (1;5): 0

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-» (таблица 11).

Таблица 11 – Цикл 4

	В1	В2	В3	В4	В5
А1						u 1 =0
-							+
А2						u 2 =0
+		-
А3						u 3 =-1
		+					-
	v 1 =3	v 2 =4	v 3 =5	v 4 =2	v 5 =1

Цикл 4 приведен в таблице (1,5 → 1,1 → 2,1 → 2,2 → 3,2 → 3,5).

Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 5) = 3. Прибавляем 3 к объемам грузов, стоящих в плюсовых клетках и вычитаем 3 из Х ij , стоящих в минусовых клетках. В результате получим новый опорный план 5 (таблица 12).

Таблица 12 – Опорный план 5

	В1	В2	В3	В4	В5
А1						u 1 =0

А2						u 2 =0
		-
А3						u 3 =-1

	v 1 =3	v 2 =4	v 3 =5	v 4 =2	v 5 =0

u 1 + v 1 = 3; 0 + v 1 = 3; v 1 = 3

u 2 + v 1 = 3; 3 + u 2 = 3; u 2 = 0

u 2 + v 2 = 4; 0 + v 2 = 4; v 2 = 4

u 3 + v 2 = 3; 4 + u 3 = 3; u 3 = -1

u 3 + v 4 = 1; -1 + v 4 = 1; v 4 = 2

u 1 + v 3 = 5; 0 + v 3 = 5; v 3 = 5

u 1 + v 5 = 0; 0 + v 5 = 0; v 5 = 0

Опорный план 5 является оптимальным, так все оценки свободных клеток удовлетворяют условию u i + v j ≤ c ij .

Минимальные затраты составят:

F(x) = 3*7 + 5*30 + 0*3 + 3*23 + 4*17 + 3*10 + 1*30 = 368

Схема перевозок:

из 1-го склада необходимо груз направить 1-му потребителю в количестве 7 ед., 3-му потребителю в количестве 30 ед.;

из 2-го склада необходимо груз направить 1-му потребителю – 23 ед., 2-му потребителю – 17ед.;

из 3-го склада необходимо груз направить второму потребителю – 10 ед., 4-му – 30 ед.

На 1-ом складе остался невостребованным груз в количестве 3 ед.

Оптимальный план является вырожденным, так как базисная переменная x 15 =0.

©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-08-26

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

> ПРИМЕР 3.1. У поставщиков А и А 2 , А 3 сосредоточено соответственно 30, 190 и 250 единиц некоторого однородного груза, который необходимо доставить потребителям В, В 2 , B 2 , В 4 в количестве 70, 120, 150 и 130 единиц. Стоимость перевозок единицы груза от поставщиков к потребителям задается матрицей

Элемент в 1-й строке и 3-м столбце равен 2, т. е. стоимость перевозки единицы груза от поставщика^ к потребителю В ъ равна 2, и т. д.

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

Суммарная мощность поставщиков равна: 30 + 190 + 250 = 470.

Суммарный спрос потребителей равен: 70 + 120 + 150 + 130 = 470.

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

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

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

Северо-западный угол таблицы - это ее левый верхний угол, т. е. клетка в 1-й строке и 1-м столбце - клетка (1, 1). Поэтому рассмотрим 1-го поставщика и 1-го потребителя. У поставщика А есть 30 единиц груза, а потребителю В нужно 70 единиц. Находим минимум из этих двух чисел: min (30, 70) = 30. Клетка (1,1) перечеркивается по диагонали сплошной чертой (-), в правом нижнем углу пишется найденный минимум 30. Это означает, что поставщик А должен доставить потребителю В 30 единиц груза. Такие клетки в дальнейшем будем называть отмеченными.

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

1-й строки перечеркнем по диагонали пунктиром (----). Такие

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

После первого шага наша таблица примет следующий вид:

Первая строка в дальнейшем не рассматривается. Северо-западный угол этой таблицы - это клетка (2, 1). Поэтому рассмотрим 2-го поставщика и 1-го потребителя. Мощность поставщика А 2 равна 190 единиц. Спрос потребителя В - 70 единиц груза. Но 30 единиц груза он получил от поставщика А (об этом говорит отмеченная клетка (1, 1). Поэтому непокрытый спрос потребителя В равен 70 - 30 = 40. Находим минимум min (190, 70 - 30) = 40. Клетка (2, 1) становится отмеченной. Запишем там этот минимум 40.

Поставщики А (30 единиц) и А 2 (40 единиц) полностью покрывают спрос потребителя В (70 единиц). Поэтому остальные клетки 1-го столбца объявим пустыми и в дальнейшем исключим из рассмотрения.

После второго шага таблица примет следующий вид:

Северо-западный угол этой таблицы - это клетка (2, 2). Min (190-40, 120)= 120.

Получаем следующую таблицу:

Северо-западный угол этой таблицы - это клетка (2, 3). Min (190-40- 120, 150) = 30. Получаем следующую таблицу:

Северо-западный угол этой таблицы - это клетка (3, 3). Min (250, 150 - 30) = 120. Получаем следующую таблицу:

Осталась одна незаполненная клетка - это клетка (3, 4). Min (250 - 120, 130) = 130. Получаем следующую таблицу:

После выполнения очередного шага мы исключали из рассмотрения либо строку, либо столбец. Только на последнем шаге отпали и строка, и столбец. Поэтому для полностью заполненной таблицы должно соблюдаться следующее соотношение: число отмеченных клеток = число строк + число столбцов - 1. В нашем случае это так: 6 = 34-4-1.

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

Посчитаем суммарные затраты. Для этого надо в каждой отмеченной клетке перемножить ее числа и результаты сложить: 4 х 30 + 3 х 40 + 1 х 120 + 2 х 30 + 3 х 120 + 7 х 130 = 1690.

Задача 3.1. Найти первоначальный план поставок северо- западного угла.

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

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

Найти стоимость перевозок.

Решение. Строим распределительную таблицу и находим груз х 11 = min (20; 15) = 15. По первому столбцу не перемещаемся, так как спрос І потребителя удовлетворен. Перемещаемся по І строке в клетку (1; 2):

х 12 = min (а 1 – х 11 ; b 2) = min (5; 35) = 5.

Теперь переходим по ІІ столбцу в клетку (2; 2):

х 22 = min (30;b 2 – х 12) = min (30; 30) = 30.

Так как спрос ІІ потребителя удовлетворен и у ІІ поставщика продукция уже выбрана, то переходим к клетке (3; 3):

х 33 = min (40; 20) = 20.

х 34 = min (а 3 – х 33 ; b 4) = min (20; 20) = 20.

Таким образом, получен план перевозок:

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

Б) Метод минимального элемента (наименьшей стоимости).

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

Пример. Построить начальный опорный план методом минимальной стоимости и найти транспортные расходы для транспортной задачи: поставщики а = (20; 30; 40); потребители = (15; 35; 20; 20); тарифы перевозок

Решение. Строим распределительную таблицу и начинаем ее заполнять с клетки (2; 1), т.к. в ней наименьший тариф х 21 = min (30; 15) = 15.

Потом заполняем клетку (3; 2) с тарифом с 32 = 3;

х 32 = min (40; 35) = 35.

х 14 = min (20; 20) = 20;

х 23 = min (а 2 – х 21 ; b 3 – х 33) = min (15; 15) = 15.

Сравнивая значение Z в а) и б), видим, что учитывая стоимости перевозок, затраты при втором методе значительно меньше.

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

В пунктах а) и б) , а число заполненных клеток 5. Следовательно, полученные планы – вырожденные.

Метод потенциалов. Признак оптимальности опорного плана.

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

I. для всех заполненных клеток; (5)

II. для всех пустых клеток. (6)

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

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

Если же найдется хотя бы одна клетка, для которой , то план не оптимальный и можно перейти к нехудшему опорному плану.

Переход к нехудшему опорному плану.

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

Приведем примеры разновидностей форм циклов:

В каждом случае только одна вершина цикла находится в незаполненной клетке. Ее называют началом цикла и определяют по наибольшему нарушению условия оптимальности (6), т.е. по максимальной оценке . Клетке начала цикла присваивают знак «+», во всех остальных вершинах цикла знаки чередуют «–»,«+» и т.д. Из клеток цикла со знаками «–» выбирают ту, в которой находится минимальный груз. Это и будет то количество груза, которое нужно перераспределить по циклу, т.е. в клетке со знаком «+» это количество груза прибавляется, а со знаком «–» – вычитается. Клетки, которые не задействованы в цикле, остаются неизменными.

Таким образом, получаем новый опорный план. Подсчитываем транспортные расходы, которые должны быть не более предыдущих. В противном случае где-то допущена ошибка. Новый план опять проверяем на оптимальность, используя условия (5) и (6). Если план оптимальный, то задача решена. Если же план опять не оптимальный, то работаем, согласно пункту 3) до получения оптимального плана и нахождения Z min .

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

Похожая информация:

Поиск на сайте:

Методов формирования опорного плана в транспортной задаче придумано немало, но, пожалуй, самый простой из них – это метод Северо-Западного угла . Алгоритм заполнения клеток транспортной таблицы в его случае сводится к следующему: сначала заполняется клетка в верхнем левом угле («северо-западном» углу), затем следующая клетка справа и т.д., пока не заполнится вся строка.

Затем мы переходим ко второй строке и снова заполняем ее слева направо. И так далее.

Метод Северо-Западного угла, в самом деле, прост и понятен, но его недостаток – низкая эффективность. Сформированный с его помощью план в большинстве случаев не является оптимальным.

Итак, у нас имеется транспортная таблица с исходными данными.

Формирование опорного плана начинаем с внесения в верхнюю левую клетку максимально возможного объема перевозки.

Запасы на складе A 1 закончились, поэтому в оставшиеся ячейки данной строки ставим прочерки. Затем переходим к следующей строке и заполняем ее ячейки слева направо.

Переходим к третьей строке и тоже заполняем ее слева направо.

Все, нами получен опорный план. Еще раз отмечу, что при методе «Северо-Западного угла» транспортная таблица просто заполняется в направлении сверху вниз и слева-направо.

Галяутдинов Р.Р.

Рассмотрим закрытую транспортную задачу. Обозначим через x ij – количество груза, перевозимого из пункта A i в пункт B j . Условия закрытой транспортной задачи запишем в распределительную таблицу, которую будем использовать для нахождения решения.

Математическая модель закрытой транспортной задачи имеет вид

Систему ограничений получаем из следующих условий задачи:

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

Оптимальным решением задачи является матрица

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

Рассмотрим каждый из приведенных выше этапов.

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

· метод северо-западного угла;

· метод минимальной стоимости;

· метод двойного предпочтения и т.д.

План составляется последовательным заполнением по одной клетке в таблице перевозок так, что каждый раз либо полностью удовлетворяется потребность одного из потребителей, либо полностью вывозится груз от некоторого поставщика. В теории доказывается, что базисное решение системы ограничений (из m + n уравнений с m´ n переменными) в условиях транспортной задачи имеет m + n – 1 базисных переменных, т.е. заполненных клеток (ее ранг равен m + n – 1 ), поэтому, совершив m + n – 1 указанных шагов, получим первый опорный план. Различие метода северо-западного угла и различных модификации метода наименьшей стоимости отыскания первого опорного плана состоит в различии способов выбора последовательности заполнения клеток.

Метод северо-западного угла . В соответствии с этим методом загрузка клеток (распределение объемов пунктов отправления по пунктам назначения) начинается с верхней левой клетки х 11 («северо-западная» часть таблицы), продолжается вниз и вправо (по диагонали) и заканчивается в клетке неизвестного x mn .

Метод минимальной (наименьшей) стоимости (минимального тарифа, минимального элемента).

Исходный опорный план, построенный методом северо-западного угла, как правило, оказывается весьма далеким от оптимального, так как при его определении совершенно игнорируется величины затрат c ij . Поэтому требуются в дальнейших расчетах много итераций для достижения оптимального плана. Число итераций можно сократить, если исходный план строить по более рациональному правилу «минимального элемента». Сущность его состоит в том, что на каждом шаге заполняется клетка с наименьшей величиной c ij .

Потребности

Если такая клетка не единственная, то лучше заполнять ту, по вертикали или по горизонтали которой встречаются большие c ij , а в принципе заполняется любая из них.

Пусть это будет клетка (i, j). Запишем в эту клетку x ij = min(a i , b j ). Если a i < b j , то запасы поставщика A i исчерпаны, а потребность B j стала Поэтому, не принимая более во внимание i-ю сроку, снова ищем клетку с наименьшей стоимостью перевозок и заполняем ее с учетом изменившихся потребностей. Для случая a i > b j из рассмотрения исключается j-й столбец, а запасы A i полагаются равными Продолжаем этот процесс до тех пор, пока все запасы не будут исчерпаны, а все потребности – удовлетворены. Необходимо отметить, что при наличии в таблице клеток с одинаковыми тарифами, планы, полученные с помощью этого метода, могут быть разными, однако они, несомненно, ближе к оптимальному, чем план, составленный по методу северо-западного угла.

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

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

Таблица 3.1

Порядок заполнения клеток: (А 1 ;В 1), (А 1 ;В 2), (А 2 ;В 2), (А 2 ;В 3), (А 3 ;В 3), (А 3 ;В 4). Число занятых клеток равно m + n – 1 = 3 + 4 – 1 = 6. Суммарные затраты на реализацию данного плана перевозок составят

Z опт = 4·30 + 5·30 + 3·70 + 6·30 + 7·10 + 4·110 = 1170.

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

Таблица 3.2

Порядок заполнения клеток: (А 2 ;В 1), (А 3 ;В 2), (А 2 ;В 4), (А 1 ;В 3), (А 1 ;В 4), (А 3 ;В 4). Суммарные затраты на реализацию данного плана перевозок составляют

Z опт = 1·30 + 2·100 + 2·70 + 2·40 + 3·20 + 4·20 = 590.

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

Таблица 3.3

Порядок заполнения клеток: (А 2 ;В 1), (А 3 ;В 2), (А 1 ;В 3), (А 2 ;В 4), (А 1 ;В 4), (А 3 ;В 4). Суммарные затраты на перевозки, представленные в табл. 3.3, составляют

Z опт = 1·30 + 2·100 + 2·40 + 2·70 + 3·20 + 4·20 = 590.

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

При распределении грузов может оказаться, что количество занятых клеток меньше, чем m + n – 1 . Такой план называется вырожденным. В этом случае недостающее их число заполняется клетками с нулевыми поставками такие клетки называют условно занятыми .

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

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

Нахождение оптимального плана транспортной задачи

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

Существуют несколько таких методов: распределительный, метод потенциалов, венгерский метод и др. Рассмотрим метод потенциалов.

Метод потенциалов

Основой вычислительного процесса при улучшении опорного плана является определение критерия оптимальности:

где - расчетные затраты или косвенные тарифы, связанные с доставкойодной единицы груза из i -го пункта отправления в j -й пункт назначения, определяемые для тех клеток опорного плана, ресурсы в которые не распределены (для незаполненных клеток); c ij - затраты (истинные тарифы), связанные с доставкой одной единицей груза из i -го пункта отправления в j -й пункт назначения.

Т е о р е м а 4.1. Если для всех свободных клеток таблицы перевозок значение критерия оптимальности ≤0, то этот план перевозок является оптимальным.

Если для всех свободных клеток таблицы перевозок значение критерия оптимальности <0, то этот оптимальный план перевозок является единственным.

Если для некоторых свободных клеток значение критерия оптимальности = 0, то этот оптимальный план перевозок не является единственным.

Если имеются свободные клетки, для которых критерий оптимальности >0, то полученный план перевозок не является оптимальным.

Алгоритм метода потенциалов

Каждому поставщику A i ,где i = 1,2,...,т , ставится в соответствие некоторое число U i ,где i = 1, 2, ., т, которое называется потенциалом А-гопоставщика или i -й строки.

Каждому потребителю B j ,где j = 1,2,…,п , ставится в соответствие некоторое число V j ,которое называется потенциалом B j -го потребителя или j-го столбца.

Для каждой заполненной клетки, т.е. для каждой базисной переменной, строитсясоотношениеU i + V j = c ij Получают систему с числом уравнений, равным количеству базисных переменных (количеству заполненных клеток).Из этой системы определяют неизвестные потенциалы строк U i и столбцов V j .

Поскольку число неизвестных п+ т превышает на единицу число уравнений т+ п-1, одно из неизвестных можно положить равным произвольному числу, например, U 1 = 0 и найти значения остальных неизвестных. Значения потенциалов записываются в ту же матрицу планирования перевозок.

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

Проверяют полученный план на оптимальность по критерию S j оптимальности опорного плана транспортной задачи. Если для каждой незаполненной клетки выполняется условие

То исходный план является оптимальным.

Если некоторое >0, то необходимо перейти к новому базисному планупутем перемещения перевозки в клетку, отвечающую условию max . Еслитаких клеток несколько, то выбирают любую из них.

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

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

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

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

В клетках с отрицательными знаками выбирается минимальная величина поставки и обозначается А .В те вершины, которые имеют знак «+» прибавляется еще поставка А , а в вершинах со знаком «-» поставки уменьшают на величину А . При этом суммы поставок по строкам a i и по столбцам bjне изменятся.

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

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

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

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

Такое улучшение плана можно проводить до тех пор, пока все критерии для незаполненных клеток окажутся <0. Затем вычисляется оптимальная стоимость перевозок.

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

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

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

Строится исходный опорный план. Если он оказывается вырожденным, то вводятся условно занятые клетки с нулевыми поставками, дополняя число занятых клеток до m + n- 1.

Вычисляется значение целевой функции Z .

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

Выполняется пересчет поставок по циклу, загружается клетка, для которой не выполняется критерий оптимальности. Строится новый опорный план с числом занятых клеток, равным m + n -1.

Выполняется переход к пункту 3.

Следует иметь в виду, что при решении транспортной задачи возможны случаи вырождения, которые встречаются, если при построении плана перевозок число заполненных клеток окажется меньше, чем m + n- 1. В этом случае следует в свободные клетки ввести недостающее количество поставок, считая их нулевыми, но заполненными. Желательно вводить эти поставки в клетки с наименьшими тарифами. Однако если при выполнении дальнейших расчетов встречаются затруднения, например, происходит зацикливание, надо поменять заполненную нулем клетку.

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

решить транспортную задачу в соответствии с предложенным вариантом с использованием ТП Excel ;

найти исходный опорный план методом северо-западного угла для вариантов с нечетным номером и методом наименьшей стоимости для вариантов с четным номером;

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

Пример выполнения работы

Некоторый однородный продукт, сосредоточенный у трех поставщиковА 1 , А 2 , A 3 в количестве а 1 , а 2 , а 3 тонн соответственно, необходимо доставить потребителям B 1 , B 2 , B 3 , B 4 , B 5 в количестве b 1 , b 2 , b 3 , b 4 , b 5 тонн.

Последовательность решения:

подготовить таблицы и заполнить их исходными данными: Стоимостиперевозки тонны продукта (D ), Ресурсы (а ) и Потребности (b );

с помощью функции СУММ найти суммы ресурсов (ячейка D 12) и потребностей (G 14);

подготовить таблицу оптимальных перевозок. Диапазон G 09:G 21 заполнить начальными значениями - нулями;

с помощью функции СУММ найти суммы перевозок по потребителям (C 22:G 22) и поставщиками (Н 19:Н 21);

в ячейку G 16 ввести выражение стоимости оптимального плана перевозок;

запустить инструментальное средство Поиск решения (меню Сервис/Поиск Решения) и ввести необходимые параметры: адрес целевой ячейки, изменяемые ячейки и ограничения (рис. 4.2).

Требования к отчету

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

название лабораторной работы;

цель лабораторной работы;

результат решения в ТП Excel;

исходный опорный план, найденный методом северо-западного угла или методом наименьшей стоимости;

последовательность шагов нахождения оптимального плана методомпотенциала.

Варианты 1-8.Некоторый однородный продукт, сосредоточенный у трех поставщиков А 1 , А 2 , А 3 в количестве а 1 , а 2 , а 3 тонн соответственно, необходимо доставить потребителям В 1 , В 2 , В 3 , В 4 , В 5 в количестве b 1 , b 2 , b 3 , b 4 , b 5 тонн. Стоимость C ij перевозки тонны груза от i- го поставщика j -му потребителю задана матрицей D . Составить план перевозок, имеющий минимальную стоимость и позволяющий вывести все грузы и полностью удовлетворить потребности.

Варианты 9-16.Пусть на предприятии имеется т видов станков, максимальное время работы которых соответственно равно а, где i = 1,2, ..., т часов. Каждый из станков может выполнять п видов операций. Суммарное время выполнения каждой операции соответственно b j , j = 1, 2, п. Известна производительность (C j)i -го станка при выполнении j -й операции. Определить, сколько времени и на какой операции нужно использовать
каждый из станков, чтобы разработать максимальное количество деталей.

Для решения этой задачи линейную функцию умножить на -1, т.е. считать в таблице все значения C j отрицательными.

Приведем сходные данные для вариантов

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t			bj

a t	bj

a t	bj

a t	bj

a t	bj

a t	bj

a t			bj

a t			bj

a t	bj

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

1. Как формулируется транспортная задача?

2. Каков общий вид матрицы планирования перевозок?

3. Что называется планом транспортной задачи?

4. Какие существуют способы отыскания исходного опорного плана?

5. Охарактеризуйте метод северо-западного угла.

6. Охарактеризуйте метод наименьшей стоимости.

7. Какие существуют способы улучшения исходного опорного плана для транспортной задачи?

РАБОТА №5. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

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

Программное обеспечение: интегрированная математическая системаMathCAD .

Теоретическое введение

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

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

Классический метод минимизации функций одной переменной.Рассмотрим задачу нахождения минимума функции f(x) на отрезке [a; b ]. Классический метод подробно излагается в курсе математического анализа. Основным недостатком классического метода является узкая область его применения.

Если значения целевой функции определены из наблюдений или в результате проведения экспериментов, то получить аналитическое выражение для производной трудно. Но даже если f" (х ) найдена, то отыскание корней уравнения f" (х )=0 может составить сложную вычислительную задачу. Поэтому разработаны методы минимизации, которые не требуют числового значения производных и в которых объем вычисления значений целевой функции является наименьшим.

Унимодальные функции. Выделим класс функций, обладающих важным свойством.

Функция f(x)называется унимодальнойна отрезке [a; b ],если онаимеет на этом отрезке единственнуюточку глобального минимума x min
и слева от этой точки является строгоубывающей, а справа - строго возрастающей.

Другими словами, функция f(x) унимодальная, если точка x min существует и является единственной. Нарис. 5.1 представлен пример графикаунимодальной функции.

Имеет место следующее свойство унимодальной функции. Рассмотрим
две произвольные точки x 1 , x 2 є[a; b ] и a<x 1 <x 2

Если f(x 1) x 2) , то x min <x 2 (рис. 5.2, а), если же f (x 1) >f(x 2), то тогда
x min >x i (рис. 8.2, б).

Метод золотого сечения. Будем искать точку глобального минимума унимодальной функции f(x) на отрезке так, чтобы количество вычислений значений f (x) для заданной точности было наименьшим.

Рассмотрим на исходном отрезке точку x 1 и вычислимf(x) .Зная значение f (x ) только в одной точке, невозможно сузить область поиска точки x min . Поэтому выбираем вторую точку x 2 так, чтобы a<x 1 <x 2 f (x 2).

Возможен один из двух случаев:

f (x 1) x 2), согласно свойству унимодальной функции область поиска сужается до [a ; x 2 ];

f (x 1) >f (x 2), тогда область поиска сужается до [x 1 ; b ].

Где же лучше всего на исходном отрезке брать точки х 1 и х 2 ?

Так как первоначально ничего неизвестно о положении точки x min , то оба указанных выше случая равно возможны. Отсюда ясно, что точки х 1 и х 2 должны быть расположены симметрично относительно середины отрезка [a ; b ].

Чтобы найти «золотую середину», рассмотрим для простотыотрезок (рис. 5.3).

Чтобы точкаВ была «выгодной» как на первом этапе, так и на следующем, она должна делить отрезок ADв таком же отношении, как и АС, т.е.АВ/AD = BC/AC. При этом в силу симметрии аналогичным свойствам будетобладать и точка С.

В терминах координаты х пропорция примет вид

Это уравнение имеет корень меньше 1 и равный .

О точке, которая расположена на расстоянии % длины от одногоиз концов отрезка, говорят, что она выполняет «золотое сечение» данного отрезка. Очевидно, каждый отрезок имеет две такие точки, расположенные симметрично относительно середины.

Итак, точки x 1 и х 2 должны осуществлять «золотое сечение» исходного отрезка [a ; b ].

Вычисляем координаты точек, осуществляющих «золотое сечение» исходного отрезка,
, z 0 =a 0 +b 0 - y 0 и определяем значения f (y 0) иf (z 0).

Сравниваем значения f(y k - 1) и f(z k - 1), (к>1).

Если f(y k - 1) - 1 и вычисляем координату точки (слева от имеющейся) y k = a k + b k -z k и значениеf (y k).

Если f(y k - 1) >f(z k - 1), то полагаем a k =a k - 1 , b k =z k - 1 , z k =y k - 1 и вычисляем координату точки (справа от имеющейся) z k = a k + b k - y k и значение f(z k).

В любом из двух случаев вычисляется длина (k +1)-го отрезка: ∆ k - 1 =b k - y k или∆ k - 1 = z k -a k

Работа выполняется до тех пор, пока ∆ k - 1 0 - заданная точность вычислений.

Выбираем наименьшее из чисел f(y k) и f(z k)- приближенный минимум. А точка, которая ему соответствует, дает приближение к x min .

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

Решить задачу оптимизации в системе MathCAD по алгоритму:

задать начальные условия задачи оптимизации;

построить график функции f (x );

оформить вычислительный блок Given с привлечением функции maximize или minimize ;

получить значения f (х ) опт и х опт.

Проанализировать полученный результат.

Обратите внимание! Для поиска значений переменных x 1 ,x 2 ,…,x n ,при которых функция f (x 1 ,x 2 ,...,x n) имеет максимальное или минимальное значение используются функцииmaximizef (x 1 , x 2 ,..., x n) и minimizef(x 1 , x 2 , ., x n). Обе эти функции реализованы достаточно универсальным алгоритмами оптимизации. Эти функции должны использоватьсяв составе вычислительного блока, открываемого директивой Given , и возвращают векторнеизвестных, при котором заданная функция имеет максимальное или минимальное значение. Внутри блока могут быть различные ограничительные условия в виде равенств илинеравенств. Число условий ограничено только памятью ПК. Перед блоком решения нужнозадать начальные значения искомых переменных.

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

Пример выполнения лабораторной работы

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

Длина дуги выкройки становится длиной окружности в основании конуса ,

где R– радиус заготовки; – значение угла вырезки; r – радиус основания конуса.

Высота конуса h , радиус его основания rи радиус заготовки Rсвязаны теоремой Пифагора.

Пусть радиус заготовки равен одному метру: R = 1. Длина окружностиоснования конуса , высота конуса , объемконуса .

Математическая формулировка задачи имеет следующий вид (рис. 5.4).Требуется рассчитать значение угла вырезки а, при котором объем V () будет максимальным, угол задаетсяв радианной мере.

При решении задачи воспользуемся встроенной функциейинтегрированной математической системы MathCADmaximize (f ,var l, var2,...), возвращающей значения переменных varl, varl, ..., которыедоставляют функцииf максимальное значение.

Решение задачи с использованием панели программирования приведено на рис.5.5.

Требования к отчету

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

копию документа, созданного в MathCAD ;

поясняющие записи из теории по теме лабораторной работы.

Варианты индивидуальных заданий

Вариант 1. f (x ) = 72x + 6х 2 - 8x 3 -x 4 наотрезке . Точку х*

Вариант 2. Вычислить максимальное значение функции f (x ) = 2х - x 2- e X на отрезке. Точку х* определить с точностью до 0,05.

Вариант 3. Вычислить максимальное значение функции f (х) = 2 sinx – tgx на отрезке. Точку х* определить с точностью до 0,05.

Вариант 4. f (х ) = 1 - 32х + 4х 2 + х 4 наотрезке . Точку х*

Вариант 5. Вычислить минимальное значение функции f (х ) = 1 + 4х + 2х 2 + х 4 на отрезке [-1; 0]. Точку х* определить с точностью до 0,01.

Вариант 6. Вычислить максимальное значение функции f (х ) = 2 + 5х -

10х 2 + 5х 3 - x 5 на отрезке [-3; -2]. Точку х* определить с точностью до 0,01.

Вариант 7. Вычислить максимальное значение функции f (х ) = 3 + 120х - 4х 2 - х 4 наотрезке . Точку х* определить с точностью до 0,01.

Вариант 8. Вычислить максимальное значение функции f (х ) = х- 1х 2 + 2х 3 - 1х 7 наотрезке . Точку х* определить с точностью до 0,01.

Вариант 9. Вычислить максимальное значение функции f (х ) = 5х + х 2 - 1х 4 на отрезке . Точку х* определить с точностью до 0,01.

Вариант 10. Вычислить максимальное значение функции f (х ) = 1 + х- 2х 2 + 4х 4 наотрезке . Точку х* определить с точностью до 0,01.

Вариант 11. Вычислить минимальное значение функции f (х ) = 2х +х-
- 5x 3 + 2x 4 на отрезке [-1; 0,5]. Точку х* определить с точностью до 0,01.

Вариант 12. Вычислить минимальное значение функции f (х ) = 2х + (х + 1)4на отрезке [-3; -1]. Точку х* определить с точностью до 0,01.

Вариант 13. Вычислить минимальное значение функции f (х ) = 2х + х- 5х на отрезке [-1; -0,5]. Точку х* определить с точностью до 0,01.

Вариант 14. Вычислить максимальное значение функцииf (х ) = х- 2х + 5х на отрезке . Точку х* определить с точностью до 0,01.

Вариант 15. Вычислить максимальное значение функции f (х ) = 1 - 6х - 3х 2 - х 6 наотрезке [-1; 0]. Точку х* определить с точностью до 0,01.

Вариант 16. Вычислить максимальное значение функции f (х) = 80х - 30х 2 - наотрезке . Точку х* определить с точностью до 0,01.

Вариант 17. Вычислить максимальное значение функции f (х ) = 1 + 2х + - наотрезке . Точку х* определить с точностью до 0,01.

Вариант 18. Вычислить минимальное значение функцииf (x ) = x 2 + x (lnx -1) наотрезке . Точку х* определить с точностью до 0,01.

Вариант 19. Вычислить максимальное значение функции f (x ) = x 3 - e x - 2x на отрезке [-2; 1]. Точку х* определить с точностью до 0,01.

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

1. В чем состоит классический метод оптимизации функции одной переменной?

2. Какие функции называются унимодальными?

3. В чем состоит суть метода золотого сечения?

4. Какая точка выполняет золотое сечение отрезка ?

РАБОТА №6. ПЛАНИРОВАНИЕ РАБОЧЕЙ СИЛЫ

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

Предположим, что проект будет выполняться в течение n недель и минимальная потребность в рабочей силе на протяжении i -й недели составит b i рабочих. При идеальных условиях хотелось бы на протяжении i -й недели иметь в точности b i рабочих. Однако в зависимости от стоимостных показателей может быть более выгодным отклонение численности рабочей силы как в одну, так и в другую сторону от минимальных потребностей. Если x i -й недели, то возможны затраты двух видов:

C 1 (x i – b i) – затраты, связанные с необходимостью содержать избыток x i – b i рабочей силы

C 2 (x i – x i -1) – затраты, связанные с необходимостью дополнительного найма x i – x i -1 рабочих.

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

Этап i представляется порядковым номером недели i , i = 1,2,..., n .

Вариантами решения на i -м этапе являются значения x i – количество работающих на протяжении i -й недели.

Состоянием на i -м этапе является x i -1 – количество работающих на протяжении (i – 1)-й недели (этапа).

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

,i = 1, 2, …, n ,

где f n +1(x n) º 0

Вычисления начинаются с этапа n при х n = b n и заканчиваются на этапе 1.

Пример 1 . Для реализации проекта строительный подрядчик определил минимальные потребности в рабочей силе на ближайшие пять недель следующим образом: 5, 7, 8, 4 и 6 рабочих соответственно. Содержание избытка рабочей силы обходится подрядчику в 300 долларов за одного рабочего в неделю, а наем рабочей силы на протяжении одной недели обходится в 400 долларов (независимо от количества принимаемых на работу человек) плюс 200 долларов за обучение одного нового рабочего в неделю.Необходимо определить, каким образом должна регулироваться численность рабочих в период реализации проекта. Задачу решить методом динамического программирования.

Решение. Выражая затраты в сотнях долларов, имеем:

b 1 =5, b 2 =7, b 3 =8, b 4 =4, b 5 =6,

C 1 (x i -b i)=3(x i -b i), x i >b i , i =1, 2, 3, 4, 5,

C 2 (x i -x i -1)=4+2(x i -x i -1), x i >x i -1, i =1, 2, 3, 4, 5.

Решение задачи начинаем с последнего (5-го этапа). По условию на этом этапе должно работать 6 работников. На предыдущем этапе в штате могло быть 4 (необходимый минимум), 5 или 6 работников (с учетом численности на 5-ом этапе).

Этап 5. (b 5 =6)

На третьем этапе должно работать максимальное число (8) работников. Поэтому в таблице 6.2х 3 = 8.

Этап 3. (b 3 =8)

x 2	С 1 (х 3 -8)+С 2 (х 3 -х 2)+ f 4 (x 3)	Опт.решение
х 3 = 8	f 3 (x 2)	x 3 *
	3(0)+4+2(1)+6=12
	3(0)+0+6=6

На втором этапе в штате может быть 7 исполнителей (необходимый минимум) или 8 исполнителей (с учетом потребностей следующего этапа). Поэтому в таблице 6.3х 2 = 7, 8.

Этап 2. (b 2 =7)

x 1	С 1 (х 2 -7)+С 2 (х 2 -х 1)+ f 3 (x 2)	Опт.решение
х 2 = 7	х 2 = 8	f 2 (x 1)	x 2 *
	3(0)+4+2(2)+12=20	3(1)+4+2(3)+6=19
	3(0)+4+2(1)+12=18	3(1)+4+2(2)+6=17
	3(0)+0+12=12	3(1)+4+2(1)+6=15
	3(0)+0+12=12	3(1)+0+6=9

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