- •Практическая работа № 1: Методы оптимизации управления для менеджеров. Технология решения оптимизационных задач с помощью инструментария ms Excel «Поиск решения»
- •Линейное программирование
- •1 Построение моделей задач линейного программирования
- •2 Решение задачи лп при помощи надстройки «Поиск решения» в ms Excel
- •2.1 Формализация примера и основные соотношения (математическая модель)
- •2.2 Решение задачи об оптимальном плане выпуска продукции с помощью Excel
- •3 Анализ оптимального решения задач лп
- •3.1 Отчет об устойчивости
- •4 Двойственная задача. Теневые цены
- •4.1 Постановка двойственной задачи к задаче об оптимальном плане выпуска продукции мебельного цеха
- •4.2 Общая формулировка исходной и двойственной задач лп
- •4.3 Решение двойственной задачи об оптимальном плане выпуска продукции мебельного цеха с помощью ms Excel
- •1. Организуйте данные так, как показано на рис. 12.
- •Задание 1. Задача лп
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Вариант 11
- •Вариант 12
- •Вариант 13
- •Вариант 14
- •Вариант 15
- •Вариант 16
- •Вариант 17
- •Вариант 18
- •Вариант 19
- •Вариант 20
- •Вариант 21
- •Вариант 22
- •Вариант 23
- •Вариант 24
- •Вариант 25
- •5 Транспортная задача
- •5.1 Математическая модель задачи
- •5.2 Решение задачи вExcel
- •Задание 2. Решить транспортную задачу Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Варианты 7–12. Условие
- •Вариант 16
- •6 Задача коммивояжера
- •6.1 Математическая модель
- •6.2 Решение вExcel
- •Задание 3. Решить задачу коммивояжера
Практическая работа № 1: Методы оптимизации управления для менеджеров. Технология решения оптимизационных задач с помощью инструментария ms Excel «Поиск решения»
1 Построение моделей задач линейного программирования 2
2 Решение задачи ЛП при помощи надстройки «Поиск решения» в MS Excel 3
3 Анализ оптимального решения задач ЛП 8
4 Двойственная задача. Теневые цены 11
5 Транспортная задача 26
6 Задача коммивояжера 35
Контрольные вопросы 45
Линейное программирование
1 Построение моделей задач линейного программирования
Математическое программирование («планирование») — это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются в экономических, организационных, военных и др. системах для решения так называемых распределительных задач. Распределительные задачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности.
Линейное программирование (ЛП) является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач ЛП следующие:
1) показатель оптимальности (целевая функция) L(X) представляет собой линейную функцию от элементов решения ;
2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.
Общая форма записи модели задачи ЛП
Целевая функция (ЦФ) , при ограничениях |
((1.1) |
Допустимое решение — это совокупность чисел (план) , удовлетворяющих ограничениям задачи (1.1).
Оптимальное решение — это план, при котором ЦФ принимает свое максимальное (минимальное) значение.
2 Решение задачи лп при помощи надстройки «Поиск решения» в ms Excel
Пример: Оптимальный план выпуска продукции мебельного цеха
Цех может выпускать два вида продукции: шкафы и тумбы для телевизора. На каждый шкаф расходуется 3,5 м стандартных ДСП, 1 м лицевого стекла и 1 человеко-день трудозатрат. На тумбу -1м ДСП, 2 м стекла и 1 человеко-день трудозатрат. Прибыль от продажи 1 шкафа составляет 200 у. е., а 1 тумбы -100 у е. Материальные и трудовые ресурсы ограниченны: в цехе работают 150 рабочих, в день нельзя израсходовать больше 350 м ДСП и более 240 м стекла. Какое количество шкафов и тумб должен выпускать цех, чтобы сделать прибыль максимальной?
2.1 Формализация примера и основные соотношения (математическая модель)
Сведем все данные в следующую таблицу
Таблица 1 – Параметры задачи
Ресурсы |
Запасы |
Продукты | |
Шкаф |
Тумба | ||
ДСП |
350 |
3,5 |
1 |
Стекло |
240 |
1 |
2 |
Труд |
150 |
1 |
1 |
Прибыль, у.е. |
200 |
100 |
В колонке «Ресурсы»запишем предельный расход ресурсов (ДСП, стекла и труда). В колонках«Шкаф»и«Тумба»(продукция, выпускаемая цехом) запишем расход сырья на единицу продукции. Наконец, на пересечении колонок«Шкаф»и«Тумба» и строки«Прибыль»запишем величины прибыли от продаж 1 шкафа и 1 тумбы.
Определим теперь все элементы математической модели данной ситуации (таблица 2):
- переменные решения;
- целевую функцию;
- ограничения.
В данном случае очевидно, что переменные решения (иначе — неизвестные), от которых зависит целевая функция (прибыль) цеха, — это количество шкафов и тумб, выпускаемых цехом. Обозначим эти переменные соответственноx1их2.
Таблица 2 – Элементы модели
Переменные решения |
Целевая функция |
x1— количество шкафов х2— количество тумб, производимых цехом |
прибыль цеха |
Ограничения | |
Нетрудно также понять, как в данном случае записывается выражение для целевой функции.
Прибыль от продажи одного шкафа равна 200 у. е., значит, прибыль от продажи x1шкафов будет 6∙x1. Аналогично прибыль от продажиx2тумб равна 5∙x2, что и отражено в соответствующей графе таблицы. Глядя на выражение для целевой функции (типичное для моделей линейного программирования), можно легко увидеть, что, чем больше будут значения переменныхx1иx2, тем больше будет и прибыльР. Если бы было возможно беспредельно увеличивать ежедневный выпуск шкафов и тумб, прибыль росла бы беспредельно. Ясно, однако, что это невозможно, поскольку доступные запасы ресурсов ограничены. Это приводит к ограничениям на значения переменныхx1иx2.
Займемся теперь этими ограничениями. Запишем неравенство, отражающее ограниченность запасов шкафов. Поскольку на 1 шкаф расходуется 3,5 м ДСП, а на 1 тумбу — 1 м, то суммарный расход ДСП на x1шкафов иx2тумб будет, очевидно,, что не должно превышать запаса ДСП в цехе, т.е. 350 м ДСП. Это отражено первым неравенством, записанным в таблице 2. Точно так же получаются второе и третье неравенства, отражающие ограниченность запасов стекла ичеловеко-день трудозатрат. Естественно, переменные решения не могут быть отрицательными числами, что отражено в последнем ограничении в таблице 2.
Определение переменных решения, целевой функции и ограничений — это почти все, что должен сделать менеджер, чтобы воспользоваться результатами оптимизации и анализа линейной модели. Далее необходимо только правильно организовать данные для компьютера, а все остальное сделает компьютерный алгоритм оптимизации.