Применение классических методов имеет некоторые трудности. Поэтому разработаны приближенные методы решения нелинейных задач программирования, особенно плодотворные для некоторых классов функций, например, для выпуклых (вогнутых) функций.
3. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ПРЕПОДАВАТЕЛЯ ПО ПРАКТИЧЕСКИМ, СЕМИНАРСКИМ ЗАНЯТИЯМ, ЛАБОРАТОРНЫМ РАБОТАМ И ДРУГИМ ВИДАМ ЗАНЯТИЙ
Методические указания к практическим занятиям
Задача линейного программирования
Оптимизационные (экстремальные) модели в экономике возникают при практической реализации принципа оптимальности в управлении.
Выбор оптимального управленческого поведения в конкретной ситуации связан с проведением экономико-математического моделирования и решением задачи оптимального программирования, в простейшем случае — задачи линейного программирования.
В наиболее общем виде задача (модель) линейного программирования записывается следующим образом: требуется найти экстремум (максимум или минимум) линейной целевой функции: f(x1, х2,…, хn) = c1х1+ c2 х2+…+ cnхn
при ограничениях:
где ci,j , bi (i=1,2,…,m; j=1,2,…,n) — заданные постоянные величины.
Иногда невозможно получить решение по оптимизационной модели: область допустимых решений может оказаться пустым множеством (система ограничений задачи противоречива) или целевая функция является неограниченной на области определения.
Первый случай связан с некорректностями в постановке экономической задачи и (или) разработанной ЭММ. Например, имеющимся объемом ресурсов заведомо невозможно выполнить даже те минимальные объемы работ, которые закладываются в ограничения как необходимые минимальные плановые задания. Если в данной ситуации все же необходимо найти решение задачи, то следует построить непустое множество допустимых решений, исключив одно или несколько ограничений, т. е. фактически соблюсти принцип альтернативности.
Второй случай обычно означает, что ЭММ разработана некорректно, и некоторые существенные ограничения в ней отсутствуют.
Примеры задачи линейного программирования
Задача линейного программирования в том или ином виде интерпретируется как задача об оптимальном использовании ограниченных производственных ресурсов.
Задача. Найти решение ЗЛП
при ограничениях
,
Решение. Приведем задачу к каноническому виду, введя дополнительные неотрицательные переменные x3,, x4,, x5. Получим систему ограничений
xj³0, j=1,2,…,5
Решаем систему симплексным методом поэтапно.
Введем основные (базисные, связанные) и неосновные (свободные, принимающие нулевые значения) переменные. Базисные переменные выразим через неосновные.
1 шаг. Основные переменные x3, x4, x5; неосновные переменные x1, x2.
Первое базисное решение: X1 (0;0;60;34;8) – допустимое. Соответствующее значение линейной функции z1=0.
Переводим в основные переменную x2, которая входит в выражение линейной функции с наибольшим положительным коэффициентом. Находим максимально возможное значение переменной x2, которое «позволяет» принять система ограничений, из условия минимума соответствующих отношений:
т. е. разрешающим (выделенным) является третье уравнение. При x2=8 в этом уравнении x5=0, и в неосновные переходит переменная x5.
2 шаг. Основные переменные x2, x3, x4; неосновные переменные x1, x5
Первое базисное решение: X2 (0;8;20;2;0) – допустимое. Соответствующее значение линейной функции z2=24. Переводим в основные переменную x1,
,
а в неосновные x4.
3 шаг. Основные переменные x1, x2, x3; неосновные переменные x4, x5.
.
X3 (
;8;18;0;0); 
Базисное решение X3 оптимальное для задачи.
(
), так как в выражении линейной функции отсутствуют неосновные переменные с положительными коэффициентами.
Основным методом решения ЗЛП является симплекс-метод. Именно этот метод реализован в программе Поиск решения пакета Ехсеl.
Первым шагом при работе с командой (программой, надстройкой) Сервис/Поиск решения является создание специального (рабочего) листа, т. е. специальная запись ЭММ в терминах электронной таблицы (ЭТ) Ехсеl.
Для этого необходимо создать в рабочем листе Ехсеl целевую ячейку, в которой записывается целевая функция моделей, а также одну или несколько изменяемых (переменных) ячеек, которые, как правило, отвечают управляющим переменным в модели и значения которых могут изменяться для достижения экстремума (максимума или минимума) целевой функции. Для успешного поиска решения необходимо, чтобы каждая из переменных ячеек влияла на целевую ячейку (другими словами, формула в целевой ячейке должна опираться в вычислениях на значения переменных ячеек). В противном случае при выполнении команды Поиск решения появляется сообщение об ошибке: Результаты целевой ячейки не сходятся.
Ограничения модели записываются в соответствующих ячейках в виде значений, которые должны находиться в определенных пределах или удовлетворять граничным условиям. Ограничения могут налагаться как на целевую, так и на переменные ячейки (по два ограничения для каждой изменяемой ячейки с указанием верхнего и нижнего пределов, а также до ста дополнительных). Таким образом, на специальном листе должны содержаться ячейки, в которых вычисляются ограничиваемые величины. Тип каждого из ограничений модели (≤,=,≥) задается (вводится) в специальном окне диалога при выполнении команды Поиск решения. Численные значения самих ограничений включать в специализированный лист необязательно – они также вводятся в специальном окне диалога при выполнении команды Поиск решения. В режиме Параметры окна диалога Поиск решения задается тип модели (линейная или нелинейная).
После команды Выполнить диалогового окна Поиск решения осуществляется поиск оптимального решения – в итоге появляется диалоговое окно Результаты поиска решения.
В режиме Справки этого диалогового окна содержатся сведения об итоговых сообщениях процедуры поиска решения. Например, в случае несовместности системы ограничений Ехсеl будет выдавать сообщение Поиск не может найти подходящего решения. Если же решение задачи отсутствует вследствие неограниченности целевой функции на множестве допустимых решений, то Ехсеl будет выдавать сообщение Значения целевой ячейки не сходятся. При успешном завершении решения задачи появляется диалоговое окно Результат поиска решения. Решение найдено. С помощью вкладки Результаты этого диалогового окна можно получить отчет по результатам решения, вкладки Устойчивость и Пределы позволяют провести дополнительный экономико-математический анализ оптимального плана и подучить отчеты по устойчивости и по пределам.
Задача. Предприятие выпускает продукцию четырех видов П1, П2, П3, П4 с использованием для этого ресурсов, виды и нормы расхода по которым, а также уровень получаемой от их реализации прибыли приведены в таблице. Составьте оптимальный план производства продукции, дающий максимальную прибыль.
Вид ресурса | Вид продукции | Запас ресурса | |||
П1 | П2 | П3 | П4 | ||
Трудовые | 1 | 1 | 1 | 1 | 16 |
Сырье | 6 | 5 | 4 | 3 | 110 |
Оборудование | 4 | 6 | 10 | 13 | 100 |
Прибыль | 60 | 70 | 120 | 130 |
Экономико-математическая модель:
Введём необходимые обозначения: пусть xj (j=1,2,3,4) – объемы каждого вида продукции. Тогда ЭММ задачи запишется следующим образом:
max f(x1, x2, x3, x4) =60x1+70x2+120x3+130x4,
Решение.
1. Создадим форму для ввода условий задачи. Для этого запустим Excel, выбрав Microsoft Excel из подменю Программы главного меню Windows. Создадим текстовую форму – таблицу для ввода условий задачи.
2. Укажем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Значения компонент вектора X=(x1, x2, x3, x4) поместим в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции – в ячейку F4.
3. Введем исходные данные задачи в созданную форму-таблицу:
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
