Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Оглавление

1. Постановка задачи

2. Разработка тестовых данных

3. Этап I. Поиск первого опорного плана

4. Этап II. Улучшение опорного плана

5. Решение задачи в среде Excel

6. Отчет о результатах

7. Отчет об устойчивости

8. Отчет о пределах

9. Анализ результатов

10. Разработка инструкций

Выводы

1. Постановка задачи

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

Дано:

· запасы (предложения) автомобильные (поставщиков);

· потребности (спрос) рынков (потребителей);

· затраты (цена) на транспортировку между каждой парой «поставщик-потребитель».

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

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

Найти план перевозок при котором

Об_затраты=План*Цена_перевозок - min

При ограничениях: Ввезено=Потребности; Вывезено<=Запасы и План>=0

2. Разработка тестовых данных

программа транспортный задача математический

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

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

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

Далее в соответствующих полях буду писать только цифры.

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

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

3. Этап I. Поиск первого опорного плана

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

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

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

4. Этап II. Улучшение опорного плана

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

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

Выбираем максимальную оценку свободной клетки .

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

Цикл приведен в таблице .

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

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

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

Выбираем максимальную оценку свободной клетки .

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

Цикл приведен в таблице .

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

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

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

Выбираем максимальную оценку свободной клетки .

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

Цикл приведен в таблице .

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

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

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

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

.

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

5. Решение задачи в среде Excel

Создаем таблицу с формулами, которые связывают план, ограничения и целевую функцию (Об_затраты):

· столбец Вывезено заполняем формулой: =СУММ(План_ произв);

· строку Ввезено заполняем формулой: =СУММ (План_рынк);

· в столбец Остаток вводим формулу: Запас-Вывезено;

· в целевую ячейку (Об_затраты) вводим формулу: =СУММПРОИЗВ (Цена; План).

Запускаем программу Поиск решений командой Данные/Анализ/Поиск решения (В Excel 2007). В полях Установить целевую ячейку, Изменяя ячейки, Ограничения вводим соответствующие адреса ячеек. Так как это линейная модель, то не забываем фиксировать в окне Параметры поиска решений переключатель на позицию Линейная модель и Неотрицательные значения. Нажимаем кнопку Выполнить и в появившемся окне Результаты поиска решения выводим отчет по устойчивости.

6. Отчет о результатах

7. Отчет об устойчивости

8. Отчет о пределах

9. Анализ результатов

Минимальные затраты на транспортирование составляют 1144,5 д. ед.

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

10. Разработка инструкций

По умолчанию в Excel надстройка “Поиск решения” отключена. Чтобы активизировать ее в Excel 2010, щелкните Файл, “Параметры”, а затем выберите категорию “Надстройки”. В поле “Управление” выберите значение “Надстройки Excel” и нажмите кнопку “Перейти”. В поле “Доступные надстройки” установите флажок рядом с пунктом “Поиск решения” и нажмите кнопку “ОК”.

Процедура поиска решения.

Транспортная задача (минимум)

1. Выделите целевую ячейку, которая должна принять необходимое значение, и выберите команду: Данные/Анализ/Поиск решения;

2. Установите переключатели Равной, задающие значение целевой ячейки, --Min (минимальному значению).

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

4. Создайте ограничения в списке Ограничения. Для этого щелкните на кнопке Добавить и в диалоговом окне Добавление ограничения определите ограничение.

5. Щелкните на кнопке на кнопке Параметры, и в появившемся окне установите переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям)

6. Щелкнув на кнопке Выполнить, запустите процесс поиска решения.

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

8. Щелкните на кнопке ОК.

Параметры средства “Поиск решения"

Максимальное время - служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.

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

Относительная погрешность - определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выводы

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

1 - оптимальный план задачи. В нашем случае, чтобы получить минимальные затраты на транспортировку в размере 1144,5 д. ед.

· 2 - Приведенная стоимость. Этот показатель, как изменится оптимальное значение ЦФ при перевозе товаров, цен на которые нет в оптимальном плане.

· 3 - коэффициенты ЦФ;

· 4, 5 - границы изменений значений коэффициентов ЦФ при условии, что количество оптимальной продукции (план) не изменится.

· 6 - количество использованных ресурсов и спрос;

· 7 - теневая цена касается ограничений, то есть, определенное значение указывает на «ценность» ограниченного ресурса в сравнении с другими ресурсами. Этот показатель указывает, как изменится оптимальное значение ЦФ (Доход) при изменении запасов ресурсов на 1 единицу.

· 8 - запасы ресурсов;

· 9, 10 - задают диапазон для 8, в котором действует теневая цена 7 (аналогично 4, 5).

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

Размещено на Allbest.ru