Практическая работа № 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):

- переменные решения;

- целевую функцию;

- ограничения.

В данном случае очевидно, что переменные решения (иначе — неизвестные), от которых зависит целевая функция (прибыль) цеха, — это количество шкафов и тумб, выпускаемых цехом. Обозначим эти переменные соответственноx₁их₂.

Таблица 2 – Элементы модели

Переменные решения	Целевая функция
x1— количество шкафов х2— количество тумб, производимых цехом	прибыль цеха
Ограничения

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

Прибыль от продажи одного шкафа равна 200 у. е., значит, прибыль от продажи x₁шкафов будет 6∙x₁. Аналогично прибыль от продажиx₂тумб равна 5∙x₂, что и отражено в соответствующей графе таблицы. Глядя на выражение для целевой функции (типичное для моделей линейного программирования), можно легко увидеть, что, чем больше будут значения переменныхx₁иx₂, тем больше будет и прибыльР. Если бы было возможно беспредельно увеличивать ежедневный выпуск шкафов и тумб, прибыль росла бы беспредельно. Ясно, однако, что это невозможно, поскольку доступные запасы ресурсов ограничены. Это приводит к ограничениям на значения переменныхx₁иx₂.

Займемся теперь этими ограничениями. Запишем неравенство, отражающее ограниченность запасов шкафов. Поскольку на 1 шкаф расходуется 3,5 м ДСП, а на 1 тумбу — 1 м, то суммарный расход ДСП на x₁шкафов иx₂тумб будет, очевидно,, что не должно превышать запаса ДСП в цехе, т.е. 350 м ДСП. Это отражено первым неравенством, записанным в таблице 2. Точно так же получаются второе и третье неравенства, отражающие ограниченность запасов стекла ичеловеко-день трудозатрат. Естественно, переменные решения не могут быть отрицательными числами, что отражено в последнем ограничении в таблице 2.

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