![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Соответствие между переменными пары взаимно двойственных линейных оптимизационных моделей
Рассмотрим исходную линейную оптимизационную модель, которая приведена к канонической форме записи введением дополнительных неотрицательных переменных: Найти максимум целевой функции:
при ограничениях:
Двойственную модель также приведем к канонической форме записи введением дополнительных неотрицательных переменных
при ограничениях:
Число переменных в системах (3.10) и (3.13) одинаково и равно n + m. Базисными переменными в исходной модели будут Между базисными переменными исходной и свободными переменными двойственной моделей можно установить следующее соответствие: Аналогично устанавливается соответствие между базисными переменными двойственной модели и свободными переменными исходной модели: Представим модели в виде симплексных таблиц. Таблица для исходной модели имеет вид: Таблица 3.1
Таблица для двойственной модели: Таблица 3.2
Положив свободные переменные Если прямая модель решается на минимум, то оптимальное решение двойственной модели равно компонентам индексной строки в последней симплексной таблице, взятыми с противоположными знаками, т.е. Пример 3.2. На предприятии имеется 4 вида сырья в количествах Таблица 3.3
Составить план производства трех видов продукции, при котором доход был бы максимальным. Найти двойственные оценки. Решение. Пусть Сформулируем двойственную модель. Пусть
Исходную задачу решим симплекс-методом. Для этого приводим систему ограничений к предпочтительному виду, вводя дополнительные неотрицательные переменные В целевую функцию дополнительные переменные вводятся с коэффициентами равными нулю Составляем симплексную таблицу № 1 (таблица 3.4):
Таблица 3.4
Строка функции цели заполняется компонентами, вычисляемыми по формулам:
Наименьшей компонентой индексной строки является «–4». Поэтому разрешающим столбцом является третий столбец. Находим симплексные отношения: 18/2 = 9, 16/1 = 16, 8/1 = 8, 6/1 = 6. Среди них наименьшее равно 6. Следовательно, разрешающей строкой является четвертая строка. Составляем новую симплексную таблицу № 2 (таблица 3.5).
Таблица 3.5
Опорный план задачи, после первого шага не является оптимальным, так как в индексной строке есть отрицательный элемент. Соответствующий столбец будет разрешающим. Находим симплексные отношения: 6/1 = 6, 10/2 = 5, 2/1 = 2. Наименьшее – «2», поэтому разрешающей строкой будет третья строка. Составляем новую симплексную таблицу № 3 (таблица 3.6): Таблица 3.6
Так как в Z - строке есть отрицательный элемент, то применяем еще раз симплекс-метод. Составляем симплексные отношения: 6/1 = 6, 6/2 = 3. Выбираем в качестве разрешающей - вторую строку. Составляем симплексную таблицу № 4 (таблица 3.7):
Таблица 3.7
Все элементы индексной строки положительные. Следовательно, построенный опорный план оптимальный. Приравняв свободные переменные нулю,
Значение двойственных оценок определим с учетом соответствия между переменными. При построении взаимно двойственных моделей соответствие между переменными следующее:
После решения и введения новых переменных в базис, получим:
Из последней симплексной таблицы находим значения двойственных оценок при условии, что свободные переменные равны нулю, т. е.
Оценка для сырья
Система ограничений двойственной задачи при подстановке оптимальных значений выполняется: 0 + 2 · Пример 3.3. Прутки стального проката длиной 600 см, согласно заявкам потребителей, нужно раскраивать на заготовки трех видов с длиной соответственно Решение. Прежде всего, построим таблицу 3.8 возможных вариантов раскроя. Таблица 3.8
Обозначим через
Аналогично составляются условия по заготовкам
Количество раскраиваемых прутков не может быть отрицательным, т. е.
Целевая функция, выражающая суммарную величину остатков, составляется с использованием величин остатков по каждому из способов раскроя (см. 5 столбец табл. 2.8):
Эта сумма должна быть минимальной. Таким образом, математическая модель задачи построена: требуется найти план количества раскраиваемых прутков
Сформулируем двойственную модель. Двойственная модель будет иметь три переменные, так как прямая модель содержит три ограничения равенства. Пусть Решим прямую задачу. Модель имеет каноническую форму и все свободные члены положительны. Система ограничений не имеет предпочтительного вида. Поэтому найдем начальный опорный план, составив следующую таблицу 3.9. Таблица 3.9
Будем перебрасывать нули из левого столбца наверх таблицы. Для первого шага исключения возьмем разрешающим первый столбец (в нем есть положительный элемент). Этот столбец исключим из следующей таблицы. Разрешающей строкой будет первая строка. Выполнив преобразования, получим следующую таблицу 3.10. Таблица 3.10
На втором шаге выбираем разрешающим столбцом четвертый столбец. Этот столбец также исключим из следующей таблицы. Так как min (180: 1=180; 225: 2=112, 5)=180, то разрешающей строкой будет третья строка. Выполнив преобразования, получим следующую таблицу 3.11.
Таблица 3.11
На третьем шаге выбираем разрешающим столбцом третий столбец. Так как min (67, 5: 1, 5=45; 112, 5: 0, 5=225)=45, то разрешающей строкой будет вторая строка. Выполнив преобразования, получим следующую таблицу 3.12. Таблица 3.12
Начальный опорный план найден:
Таблица 3.13
В строке целевой функции есть положительный элемент. Следовательно, первый столбец будет разрешающим. После очередного шага жорданова исключения приходим к таблице 3.14, содержащей оптимальный план Таблица 3.14
Значение двойственных оценок определим с учетом соответствия между переменными. При построении взаимно двойственных моделей соответствие между переменными следующее:
↕ ↕ ↕ ↕ ↕ ↕
После решения и введения новых переменных в базис, получим: Из последней симплексной таблицы находим значения двойственных оценок при условии, что свободные переменные равны нулю, т. е.
|