Сенс двоїстих оцінок, електронна бібліотека

Згадаймо, що додаток (або віднімання) одного і того ж числа до всіх показниками будь-якого рядка матриці не ">

Сенс потенціалів той же, причому інакше, як ми тепер уже знаємо, не могло б бути: потенціали і двоїсті оцінки в алгоритмі диференціальних рент це одне і те ж. Якщо відняти (з урахуванням знаків) з показників всіх стовпців і рядків матриці відповідні потенціали, то виходить точно така ж матриця, як і в алгоритмі диференціальних рент, в якій всі гуртки сидять на мінімумах.

Оскільки, визначаючи потенціали, величину першого з них ми вибираємо довільно, може здатися, що і матриця після такого перетворення буде інший. Однак це, звичайно, не так.

В черговий раз згадаємо, як ставиться і вирішується транспортна задача. Відомі дані про кількість вантажу в пунктах відправлення і про потреби в ньому в пунктах призначення. Відома матриця показників витрат на перевезення одиниці продукції. Потрібно знайти оптимальний план перевезень, в якому загальна сума витрат була б мінімальною.

Критерієм оптимальності в задачі є загальна сума витрат на перевезення, однак самі по собі показники витрат не можуть дати і не дають відповіді на питання про те, якою має бути схема перевезень. Або, точніше, показники витрат могли б привести нас до вірного рішення, тільки коли запас вантажу у постачальників був би не обмежений - в такому випадку можливо розставити гуртки на мінімумах витрат і, ледве встигнувши почати, вже покінчити з рішенням завдання.

Однак, оскільки в завданні є обмеження, показники витрат виявляються недостатніми для безпосереднього отримання рішення; більш того, часто виявляється, що в оптимальному плані немає гуртка на мінімальному елементі матриці.

Весь сенс оптимального програмування полягає в тому, що якщо деякий показник прийнятий в якості критерію, то в умовах, коли є певні обмеження, знайти оптимальне рішення, користуючись тільки їм, не можна.

Двоїсті оцінки і з'єднують воєдино критерій і обмеження.

Двоїсті оцінки - це якась нова «субстанція», що дозволяє проводити вимірювання в екстремальну задачу з точки зору заданого критерію.

Показник в ">, а проте поза зв'язком з іншими умовами завдання, він не відповідає на головне питання, яке нас цікавить, - везти чи не везти вантаж з пункту А i в пункт В j. Але коли з'являється подвійна оцінка (характеристика), все стає зрозумілим - характеристика точно відповідає

на основне питання завдання, вона каже, наскільки зміниться значення функціоналу, якщо прийняти таке перевезення.

Безглуздо ставити питання таким чином, що двоїсті оцінки замінюють вартісні оцінки, або взагалі будь-яким чином протиставляти ці оцінки один одному. Але треба бачити істотна відмінність між ними.

Вартість виражає витрати суспільно необхідної праці, а важливість знання величини цих витрат не треба доводити.

Двоїсті оцінки вимірюються в тих же одиницях, що і показники критерію оптимальності даної конкретної задачі. Якщо в транспортній задачі елементи матриці представляють ">

Різниця між вартістю і подвійними оцінками полягає в тому, що