Головна

Економічна інтерпретація двоїстих задач. Геометричний сенс двоїстої задачі.

  1. Власність як правова і економічна категорія. Еволюція відносин власності.
  2. Геометрична інтерпретація
  3. Геометрична інтерпретація ОЗЛП
  4. Економічна база перспективного розвитку міст і визначення чисельності населення
  5. Економічна відповідальність за несвоєчасність здійснення розрахунків.
  6. Економічна система, її сутність. Цілі і основнці структурні елементи.

Экономико-математическая модель и содержательная интерпретация двойственной задачи выглядит следующим образом:

(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. | Воздействие вибрации на организм человека | Стохастичні задачі пошуку оптимальних рішень. Економіко-статистичні моделі. | Сканер: назначение, методика сканирования, основные параметры. | Безпечність технологічного обладнання. | Безпечність технологічного процесу. | Синтез оптимального управління для лінійних систем з квадратичним критерієм. |

© 2016-2022  um.co.ua - учбові матеріали та реферати