Автор: Пользователь скрыл имя, 18 Января 2012 в 20:53, контрольная работа
Оптимизация как раздел математики существует достаточно давно и обозначает выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточнённое решение. Хотя конечной целью оптимизации является отыскание наилучшего или "оптимального" решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.
Введение 3
Задание 1 4
Задание 2 6
Задание 3 8
Заключение 11
Список литературы 12
Матрицa затрат
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | 6 | 3 | 7 | 10 |
| B2 | 100 | 10 | 4 | 12 | 10 |
| B3 | 20 | 5 | 9 | 8 | 11 |
| B4 | 75 | 4 | 2 | 4 | 8 |
Опорный план перевозок
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | 30 | 15 | ||
| B2 | 100 | 65 | 35 | ||
| B3 | 20 | 20 | |||
| B4 | 75 | 40 | 35 |
Расчет потенциалов
| А1 | А2 | А3 | А4 | |||
| 30 | 80 | 95 | 35 | a | ||
| B1 | 45 | -4 | -5 | 0 | ||
| B2 | 100 | 3 | -6 | -1 | ||
| B3 | 20 | 2 | 9 | -1 | 3 | |
| B4 | 75 | 5 | 6 | 7 | ||
| b | 6 | 3 | 11 | 15 |
План не оптимален, т.к. в свободных клетках не выполняется условие a+Cij>=b
Помечена клетка, которая наиболее не соответствует условию оптимальности
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | 30 | 15 | ||
| B2 | 100 | 65 | (-) 35 | (+) | |
| B3 | 20 | 20 | |||
| B4 | 75 | (+) 40 | (-) 35 |
Перераспределим поставки: 35 (отнимем от клеток со знаком минус и добавим к клеткам со знаком плюс)
Новый план перевозок
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | 30 | 15 | ||
| B2 | 100 | 65 | 35 | ||
| B3 | 20 | 20 | |||
| B4 | 75 | 75 | 0 |
Расчет потенциалов
| А1 | А2 | А3 | А4 | |||
| 30 | 80 | 95 | 35 | a | ||
| B1 | 45 | 2 | 1 | 0 | ||
| B2 | 100 | 3 | 6 | -1 | ||
| B3 | 20 | -4 | 3 | -1 | -3 | |
| B4 | 75 | -1 | 0 | 1 | ||
| b | 6 | 3 | 5 | 9 |
План не оптимален, т.к. в свободных клетках не выполняется условие a+Cij>=b
Помечена клетка, которая наиболее не соответствует условию оптимальности
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | (-) 30 | (+) 15 | ||
| B2 | 100 | (-) 65 | (+) 35 | ||
| B3 | 20 | (+) | (-) 20 | ||
| B4 | 75 | (+) 75 | (-) 0 |
Перераспределим поставки: 0 (отнимем от клеток со знаком минус и добавим к клеткам со знаком плюс)
Новый план перевозок
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | 30 | 15 | ||
| B2 | 100 | 65 | 35 | ||
| B3 | 20 | 0 | 20 | ||
| B4 | 75 | 75 |
Расчет потенциалов
| А1 | А2 | А3 | А4 | |||
| 30 | 80 | 95 | 35 | a | ||
| B1 | 45 | -2 | 1 | 0 | ||
| B2 | 100 | 3 | 2 | -1 | ||
| B3 | 20 | 7 | 3 | 1 | ||
| B4 | 75 | 3 | 4 | 4 | 5 | |
| b | 6 | 3 | 9 | 9 |
План не оптимален, т.к. в свободных клетках не выполняется условие a+Cij>=b
Помечена клетка, которая наиболее не соответствует условию оптимальности
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | (-) 30 | 15 | (+) | |
| B2 | 100 | 65 | 35 | ||
| B3 | 20 | (+) 0 | (-) 20 | ||
| B4 | 75 | 75 |
Перераспределим поставки: 20 (отнимем от клеток со знаком минус и добавим к клеткам со знаком плюс)
Новый план перевозок
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| B1 | 45 | 10 | 15 | 20 | |
| B2 | 100 | 65 | 35 | ||
| B3 | 20 | 20 | |||
| B4 | 75 | 75 |
Расчет потенциалов
| А1 | А2 | А3 | А4 | |||
| 30 | 80 | 95 | 35 | a | ||
| B1 | 45 | 10 | 0 | |||
| B2 | 100 | 10 | 12 | -1 | ||
| B3 | 20 | 9 | 8 | 11 | 1 | |
| B4 | 75 | 4 | 2 | 8 | 3 | |
| b | 6 | 3 | 7 | 9 |
План перевозок оптимален, т.к. в свободных клетках выполняется условие a+Cij>=b
Затраты на перевозку составят 1255
Оптимальный план перевозок
| А1 | А2 | А3 | А4 | ||
| 30 | 80 | 95 | 35 | ||
| А1 | 45 | 10 | 15 | 20 | |
| А2 | 100 | 65 | 35 | ||
| А3 | 20 | 20 | |||
| А4 | 75 | 75 |
Заключение
Алгоритмы безусловной минимизации (максимизации) функций многих переменных можно сравнивать и исследовать как с теоретической, так и с экспериментальной точек зрения.
Первый подход может быть реализован полностью только для весьма ограниченного класса задач, например, для сильно выпуклых квадратичных функций. При этом возможен широкий спектр результатов от получения бесконечной минимизирующей последовательности в методе циклического покоординатного спуска до сходимости не более чем за n итераций в методе сопряженных направлений.
Мощным инструментом теоретического исследования алгоритмов являются теоремы о сходимости методов. Однако, как правило, формулировки таких теорем абстрактны, при их доказательстве используется аппарат современного функционального анализа. Кроме того, зачастую непросто установить связь полученных математических результатов с практикой вычислений. Дело в том, что условия теорем труднопроверяемы в конкретных задачах, сам факт сходимости мало что дает, а оценки скорости сходимости неточны и неэффективны. При реализации алгоритмов также возникает много дополнительных обстоятельств, строгий учет которых невозможен (ошибки округления, приближенное решение различных вспомогательных задач и т.д.) и которые могут сильно повлиять на ход процесса.