Головна |
Экономико-математическая модель и содержательная интерпретация двойственной задачи выглядит следующим образом:
(1)
при ограничениях
(2)
и условии не отрицательности
(3)
Найти такой набор цен (оценок) ресурсов , при котором общие затраты на ресурсы буду минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции.
Алгоритм составления двойственной задачи:
1. Привести все неравенства системы ограничений к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду « », а если минимум - к виду « ». Для этого неравенства, в которых данное требвание не выполняется, умножить на -1.
2. Составить расширенную матрицу системы , в которую включить матрицу коэффициентов при переменных А, столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции.
3. Найти матрицу , транспонированную к матрице .
4. Сформулировать двойственную задачу на основании полученной матрицы и условия не отрицательности переменных.
Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности:
Достаточный признак оптимальности. Сформулируем теорему.
Теорема. Если и - допустимые решения взаимно двойственных задач, для которых выполняется равенство
,(4)
то - оптимальное решение исходной задачи, а - двойственной задачи.
Первая (основная) теорема двойственности.Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальные значения их линейных функций равны:
или (5)
Экономический смысл первой теоремы двойственности: план производства и набор цен (оценок) ресурсов оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах , равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам .
установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи
(6)
Теорема. Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, то есть для любых и : если , то ; если , то , и аналогично, если , то ; если , то .
Соответствие (1) между переменными взаимно двойственных задач при достижении оптимума представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и не основными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения.
Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через не основные переменные е оптимального решения.
Третья теорема двойственности. Компоненты оптимального решения двойственной задачи равны значениям частных производных линейной функции по соответствующим аргументам, то есть
. (7)
В соответствии с выражением (1) оптимальное (минимальное) значение линейной функции
.
На рис. 1 для простейшего случая двух переменных оптимальное решение соответствует точке B.
II. Практическая часть
У файлі зберігається інформація про пасажирів і багаж. Багаж пасажира характеризується кількістю речей і вагою кожної речі. З'ясувати, чи є пасажир, вагу багажу якого перевищує вага багажу кожного з пасажирів.
Public Type Passanger
FIO As String * 50 'Ф. И. О. пассажира
Info As String * 1000 'дополнительная информация о пассажире
Things(1000) As String * 25 'список вещей пассажира
Q(1000) As Single 'вес каждой вещи
End Type
Function GetMinQ(FileName As String) As String
Dim MinQP As Passanger, PInfo As Passanger
min_total_q = -1
min_count = 0
Open FileName For Random As #1 Len = Len(PInfo) 'открываем бинарный файл
For i = 1 To LOF(1) / Len(PInfo)
Get 1, i, PInfo 'просматриваем каждую запись файла и помещаем ее в переменную PInfo
total_q = 0
For Each j In PInfo.Q 'находим общий вес багажа пассажира (сумму весов каждой вещи)
total_q = total_q + PInfo.Q(j)
Next j
'проверяем, является ли вес багажа ткущего пассажира минимальным
If min_total_q = -1 Or total_q < min_total_q Then 'если да, то принимаем его за минимальный
MinQP = PInfo
min_total_q = total_q
min_count = 1
ElseIf total_q = min_total_q Then 'если найденеще один пассажир с минимальным весом багажа, то прибавляем счетчик
min_count = min_count + 1
End If
Next i
Close 1
If min_count = 1 Then 'если только один пассажир с минимальным весом багажа
GetMinQ = "Ф. И. О. пассажира: " & MinQP.FIO & vbCrLf & "Вес багажа: " & min_total_q
ElseIf min_count > 1 Then 'если таковых найдено несколько
GetMinQ = "Обнаружено больше одного пассажира с минимальным весом багажа"
End If
End Function
Основні детерміновані методи оптимізації і їх короткий огляд. | Формати графічних файлів. | Adobe PostScript | Скласти рекурсивну процедуру, яка видаляє від'ємні елементі зі списку S. | Воздействие вибрации на организм человека | Стохастичні задачі пошуку оптимальних рішень. Економіко-статистичні моделі. | Сканер: назначение, методика сканирования, основные параметры. | Безпечність технологічного обладнання. | Безпечність технологічного процесу. | Синтез оптимального управління для лінійних систем з квадратичним критерієм. |