Линейное программирование.
Пример задачи линейного программирования и ее решения.
Известно, что на предприятии для производства изделий №1, 2, 3 требуются определенные ресурсы, и каждое изделие приносит определенную прибыль, например:
| Изделие | №1 | №2 | №3 | Объем ресурсов |
| Объем производственных фондов Рабочая сила | ||||
| Прибыль на одно изделие |
Задача линейного программирования - получить ответы на следующие и тому подобные вопросы:
1. Найдите оптимальное решение: какие изделия (они будут называться базисными) и в каком количестве (Х1, Х2 и Х3) необходимо производить, чтобы получить максимальную прибыль (величину целевой функции) при указанном объеме ресурсов?
2. Какой прирост общей прибыли предприятия возможен при увеличении объема каждого из ресурсов (по очереди) на одну единицу?
3. Какое изменение прибыли на одно изделие возможно при сохранении оптимального решения?
4. Какова предельная величина каждого ресурса, т.е. дальнейшее увеличение этого ресурса не приведет к увеличению целевой функции?
Например: общая прибыль производства (в математических терминах):
105*X1+96*X2+100*X3 àMAX (целевая функция)
При этом ограничения по ресурсам:
3*X1+ 4*X2+ 5*X3<=120
7*X1+ 6*X2+ 4*X3<=300
Пуск / Сетевое меню / STORM / Linear Programming
(выбор по меню осуществляется клавишами со стрелками, подтверждение выбора - клавишей Enter. Если для завершения операции требуется нажатие любой другой клавиши, например End или Esc, то рекомендация записана в соответствующем окне)
1.Создайте новый набор данных.
Title Заглавие
Number of variables: Число переменных
Number of constraints: Число ограничений
Starting solution given: Стартовое данное решение: (сохранять или нет)
|
|
Objective function: Направление целевой функции на max или min?
VAR1…VAR N переменные (изделия)
CONST TYPE тип ограничений для ресурсов
RHS граница для ресурсов (объем ресурсов)
RANGE предел границы для ресурсов
OBJ COEFF коэффициенты целевой функции при соответствующих переменных (прибыль на изделие).
CONSTR1… CONSTR N ресурсы для соответствующих переменных
VARBL TYPE тип переменных
LOWR BOUND нижняя граница переменной (количество этого изделия должно быть более или равно этому числу)
UPPR BOUND верхняя граница переменной
INIT SOLN начальное значение
После введения всех данных режим редактирования завершается нажатием функциональной клавиши F7 (End).
2.Сохраните введенный файл под именем LP.dat
3.Решите задачу с имеющимся набором данных.
Меню представления результатов обработки данных:
1.Оптимальное решение
2.Общий отчет
3.Детальный отчет
4.Перейти к следующей итерации
5.Выделить переменную, для которой надо произвести анализ
Меню оптимального решения:
1.Общий отчет по поиску оптимального решения
2.Подробный отчет по поиску оптимального решения
3.Анализ оптимального решения на чувствительность (коэффициентов целевой функции и объемов ресурсов)
4.Параметрический анализ по ресурсам
5.Выделить переменную и идти к следующему повторению
6.Записать оптимальное решение как начальное решение
Воспользуйтесь первым пунктом меню оптимального решения, чтобы ответить на первый вопрос задачи.
Общая рекомендация: воспользуйтесь словами для справки, расположенными ниже, чтобы определить смысл каждого столбца выведенной таблицы
|
|
Создайте файл “Линейное программирование.rtf”, в котором записывайте все ответы на вопросы задачи.
Второй пункт меню представляет информацию на двух страницах по порядку.
На первой странице выводится информация об изделиях – какое изделие вошло в базис, какое не вошло и при каких условиях оно может войти в базис оптимального решения (особое внимание обратите на столбец Red.cost).
На второй странице выводится информация о ресурсах – начальный объем, остаток и какой прирост целевой функции обеспечит увеличение какого ресурса на одну единицу (особое внимание обратите на столбец Shadow price).
Ответьте на второй вопрос задачи.
Проверьте полученный ответ, вернувшись в режим редактирования (клавиша F7) и задав величину этого ресурса на одну единицу больше. Какова при этом стала величина целевой функции?
Вернувшись в режим редактирования восстановите исходные данные задачи.
Третий пункт меню представляет информацию на двух страницах по порядку.
На первой странице выводится информация об изделиях – для каждого изделия указана минимальная и максимальная прибыль, при которых действительно найденное оптимальное решение.
На второй странице выводится информация о ресурсах – для каждого ресурса указан минимальный и максимальный объем, при которых действительно найденное оптимальное решение.
Ответьте на третий вопрос задачи.
Четвертый пункт меню представляет информацию о влиянии величины каждого ресурса (при входе осуществляется выбор ресурса) на величину целевой функции найденного оптимального решения и на изменение оптимального решения.
Ответьте на четвертый вопрос задачи.
Слова для справки:
Allowable – приемлемый
Cost – прибыль
Infeasible – невыполнимый
Infinity – бесконечность
Red.cost– то изменение прибыли на изделие, которое позволит изменить целевую функцию
Shadow price– возможное изменение целевой функции при изменении ресурса на 1 единицу
Slack – резерв
Value – объем производства
Leave – выходит из базиса; Enter – вводится в базис