- •Линейные методы оптимизации. Задачи линейного программирования
- •1.1 Общая постановка задачи линейного программирования.
- •Линейное программирование в экономике
- •1.3 Решение систем линейных алгебраических уравнений в форме жордановых таблиц
- •1.3.1 Основные понятия
- •1.3.2 Жордановы таблицы
- •1.3.3 Алгоритм решения слау в форме жордановых таблиц
- •1.3.4 Примеры решения типовых задач
- •1.4 Базисные и опорные решения слау
- •1.4.1 Основные понятия
- •1.4.2 Алгоритм отыскания опорных решений слау
- •1.4.3 Примеры решения типовых задач
- •1.3.5 Задания для самостоятельного решения
- •Задания для самостоятельной работы
- •Графическое решение задач линейного программирования
- •1.5.1 Геометрическая интерпретация
- •1.5.2 Алгоритм графического решения злп
- •1.5.3 Пример решения типовой задачи
- •1.5.4 Задания для самостоятельной работы
- •1.6 Симплексный метод решения задач линейного программирования
- •1.6.1 Укрупненный алгоритм симплексного метода
- •1.6.2 Алгоритм отыскания начального опорного плана
- •1.6.3 Алгоритм отыскания оптимального опорного плана
- •1.6.4 Пример решения типовой задачи
- •1.6.5 Задания для самостоятельной работы
- •Двойственность в линейном программировании
- •1.7.1 Понятие двойственности для симметричных задач
- •1.7.2 Экономическая интерпретация симметричных двойственных задач
- •1.7.3 Связь между решениями прямой и двойственной задачи
- •2. Оптимальное распределение ресурсов. Транспортная задача
- •2.1. Метод северо-западного угла (мсзу)
- •2.2. Метод минимального тарифа (ммт)
- •2.3. Определение оптимального плана перевозок методом потенциалов
- •2.4. Транспортная задача с усложнениями
- •2.5. Транспортная задача по критерию времени
- •2.6 Задания для самостоятельной работы
- •3. Элементы нелинейного программирования
- •Постановка задач нелинейного программирования
- •Особенности решения задач нелинейного программирования
- •Метод множителей Лагранжа
- •4 Метод наименьших квадратов
- •4.1 Некоторые типы эмпирических формул
- •Примеры решения типовых задач
- •4.3 Задания для работы в аудитории
- •4.4 Подбор эмпирических формул по выборочным данным
- •4.3 Задание для самостоятельной работы
- •Элементы сетевого планирования
- •При управлении такими проектами применяются специальные способы изображения сетей, позволяющие разработать очень эффективные и простые процедуры вычислений информации о состоянии проекта.
- •5.1 Построение сетевой модели
- •5.2 Наиболее ранний срок наступления события
- •5.3 Наиболее поздний срок наступления события
- •Пример 3. Для всех узлов (событий) сети из примера 1 определить наиболее поздний допустимый срок наступления события.
- •5.4 Резерв времени и критический путь
- •5.5 Оптимизация плана комплексных работ
- •5.6 Задания для самостоятельной работы
- •Литература
- •Методы решения оптимизационных задач
- •346493, Донской гау, пос. Персиановский,
1.7.2 Экономическая интерпретация симметричных двойственных задач
Рассмотрим экономическую интерпретацию понятия двойственности на примере задачи оптимального использования сырья.
Пусть
на предприятии решили рационально
использовать отходы основного
производства. Пусть на предприятии
имеются отходы сырья
видов в объемах
единиц
.
Из этих отходов можно наладить выпуск
видов неосновной продукции. Обозначим
через
норму
расхода сырья
-го
вида на единицу продукции
-го
типа
,
через
–
цену реализации единицы
-ой
продукции. Неизвестные величины задачи:
–
объемы выпуска
-ой
продукции, обеспечивающие предприятию
максимум выручки.
Математическая модель задачи имеет вид (13)-(15).
Пусть
с самого начала при изучении вопроса
об использовании отходов основного
производства на предприятии появилась
возможность продать их некоторой
организации. Необходимо установить
оценки (цены) на эти отходы. Обозначим
цену единицы отходов сырья каждого вида
через
Оценки должны быть установлены исходя
из следующих требований, отражающих
несовпадающие интересы продавца и
покупателя:
1) общую стоимость отходов сырья покупатель стремится минимизи-
ровать;
2) предприятие согласно продать отходы только по таким ценам, при
которых оно получит за них выручку, не меньшую той, что могло бы
получить, организовав собственное производство.
Эти требования приводят к следующей математической модели.
Требование 1 покупателя –минимизация стоимости покупки:
Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если
.
Здесь левая часть означает выручку за сырье, идущее на производство единицы продукции первого вида; правая – цену реализации каждой единицы этой продукции.
Аналогичные рассуждения можно провести в отношении выпуска продукции каждого вида. Так мы получим двойственную задачу
(16)-(18).
Пример.
Предприятие может выпускать четыре вида продукции. Сбыт обеспечен. Для изготовления продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объем ресурсов (в расчете на трудовую неделю), расход каждого ресурса на единицу выпускаемой продукции и прибыль, полученная за единицу продукции, приведены в таблице. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить послеоптимизационный анализ решения и параметров модели.
Решение.
Пусть
-
объемы продукции
,
планируемой к выпуску;
–сумма
выручки. Математическая модель прямой
задачи.
при ограничениях
Ресурсы |
Выпускаемая продукция |
Объем ресурсов |
||||
П1 |
П2 |
П3 |
П4 |
|||
Р1 |
Трудовые ресурсы, чел-час |
4 |
2 |
2 |
8 |
4800 |
Р2 |
Полуфабрикаты, кг |
2 |
10 |
6 |
0 |
2400 |
Р3 |
Станочное оборудование, станко-час |
1 |
0 |
2 |
1 |
1500 |
Цена единицы продукции, руб |
65 |
70 |
60 |
120 |
|
|
Пусть
–оценка
стоимости одного человеко-часа,
–оценка
одного килограмма полуфабриката,
-
оценка стоимости одного станко- часа.
Тогда математическая модель двойственной
задачи имеет вид:
при ограничениях
