19814

Підбиття підсумків для оптимального (мінімального) значення цільової функції

Доклад

Информатика, кибернетика и программирование

4.Підбиття підсумків для оптимального мінімального значення цільової функції Оптимальним значенням транспортної задачі називають матрицю яка задовольняє умови задачі і для якої цільова функція 5.1 5.1 набирає найменшого значення. Теорема умова існування розв

Украинкский

2013-07-17

95 KB

0 чел.

4.Підбиття підсумків для оптимального (мінімального) значення цільової функції

Оптимальним значенням транспортної задачі називають матрицю , яка задовольняє умови задачі, і для якої цільова функція (5.1)

(5.1)

набирає найменшого значення.

Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі є її збалансованість: .

Транспортная задача

Класична транспортна задача лінійного програмування формулюється так: деякий однорідний продукт, що знаходиться у m постачальників Аі в обсягах одиниць відповідно необхідно перевезти n споживачам в обсягах одиниць. При цьому виконується умова, що загальний наявний обсяг продукції у постачальників дорівнює загальному попиту всіх споживачів. Відомі вартості перевезень одиниці продукції від кожного Аі-го постачальника до кожного Вj-го споживача, що подані як елементи матриці виду:

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

У такій постановці задачі ефективність плану перевезень визначається його вартістю і така задача має назву транспортної задачі за критерієм вартості перевезень.

Запишемо її математичну модель. Позначимо через обсяг продукції, що перевозиться від постачальника до споживача . Тоді умови задачі зручно подати у вигляді такої таблиці:

Таблиця 5.1

Споживачі

В1

В2

...

Вn

Постачальники

b1

b2

...

bn

A1

а1

с11

x11

с12

x12

...

с1n

x1n

A2

а2

с21

x21

с22

x22

с2n

x2n

Am

аm

сm1

xm1

сm2

xm2

сmn

xmn

Мають виконуватися такі умови:

сумарний обсяг продукції, що вивозиться з кожного і-го пункту, має дорівнювати запасу продукції в даному пункті:

сумарний обсяг продукції, що ввезений кожному j-му споживачеві, має дорівнювати його потребам:

сумарна вартість всіх перевезень повинна бути мінімальною:

Очевидно, що .

У скороченій формі запису математична модель транспортної задачі за критерієм вартості перевезень має такий вигляд:

(5.1)

за обмежень:

; (5.2)

; (5.3)

. (5.4)

У розглянутій задачі має виконуватися умова:

. (5.5)

Транспортну задачу називають збалансованою, або закритою, якщо виконується умова (5.5). Якщо ж така умова не виконується, то транспортну задачу називають незбалансованою, або відкритою.

Домовимося планом транспортної задачі називати будь-який невід’ємний розв’язок системи обмежень (5.2)—(5.4), який позначають матрицею . Значення невідомих величин — обсяги продукції, що мають бути перевезені від i-х постачальників до j-х споживачів, називатимемо перевезеннями.

Оптимальним планом транспортної задачі називають матрицю , яка задовольняє умови задачі, і для якої цільова функція (5.1) набирає найменшого значення.

Теорема (умова існування розв’язку транспортної задачі): необхідною і достатньою умовою існування розв’язку транспортної задачі (5.1)—(5.4) є її збалансованість: .

Доведення. Необхідність. Нехай задача (5.1)—(5.4) має розв’язок , тоді для нього виконуються рівняння-обмеження (5.2) і (5.3). Підсумуємо відповідно ліві та праві частини систем рівнянь (5.2) і (5.3). Матимемо:

, (5.6)

(5.7)

Оскільки ліві частини рівнянь (5.6) та (5.7) збігаються, то праві також рівні одна одній, отже, виконується умова:

. (5.8)

Достатність. Потрібно показати, що за заданої умови (5.8) існує хоча б один план задачі, і цільова функція на множині планів обмежена.

Нехай W > 0. Розглянемо величини (). Підставивши значення в систему обмежень задачі (5.1)—(5.4), матимемо:

;

.

Оскільки умови (5.2) та (5.3) виконуються, то є планом наведеної транспортної задачі.

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

.

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

.

Тобто цільова функція на множині допустимих планів транспортної задачі є обмеженою:

.

Теорему доведено.

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

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

Як згадувалося вище, транспортна задача (5.1)—(5.4) є звичайною задачею лінійного програмування і може бути розв’язана симплексним методом, однак особливості побудови математичної моделі транспортної задачі дають змогу розв’язати її простіше. Легко помітити, що всі коефіцієнти при змінних у рівняннях (5.2), (5.3) дорівнюють одиниці, а сама система обмежень (5.2), (5.3) задана в канонічній формі. Крім того, система обмежень (5.2), (5.3) складається з mn невідомих та m + n рівнянь, які пов’язані між собою співвідношенням (5.8). Якщо додати відповідно праві та ліві частини систем рівнянь (5.2) та (5.3), то отримаємо два однакових рівняння:

;

.

Наявність у системі обмежень двох однакових рівнянь свідчить про її лінійну залежність. Якщо одне з цих рівнянь відкинути, то в загальному випадку система обмежень буде містити m + n – 1 лінійно незалежне рівняння, отже, їх можна розв’язати відносно m + n – 1 базисних змінних. Назвемо опорним планом транспортної задачі такий допустимий її план, що містить не більш ніж m + n – 1 додатних компонент, а всі інші його компоненти дорівнюють нулю. Такий план є невиродженим. Якщо ж кількість базисних змінних менша ніж m + n – 1, то маємо вироджений опорний план.


 

А также другие работы, которые могут Вас заинтересовать

80895. Стратегическое планирование в Муниципальном Образовании 44.44 KB
  Недостаток опыта стратегического планирования комплексного подхода к определению целей и приоритетов перспективного развития муниципальных образований приводит к тому что разработанные концепции и стратегические планы иногда носят декларативный характер отсутствуют механизмы их реализации. В зависимости от стоящих задач концепции и стратегические планы бывают среднесрочные 3 5 лет и долгосрочные до 10 15 лет. Основные этапы разработки концепции комплексного социальноэкономического развития муниципального образования...
80896. Основные направления по противодействию коррупции государственных и муниципальных органах власти 45.12 KB
  Коррупция - злоупотребление служебным положением, дача взятки, получение взятки, злоупотребление полномочиями, коммерческий подкуп либо иное незаконное использование физическим лицом своего должностного положения вопреки законным интересам общества и государства в целях получения выгоды в виде денег, ценностей, иного имущества или услуг имущественного характера, иных имущественных прав для себя или для третьих лиц либо незаконное предоставление такой выгоды указанному лицу другими физическими лицами;
80897. Информационное обеспечение муниципального управления 45.52 KB
  Распоряжения главы администрации и его заместителей протоколы заседаний коллегии ведомости учета изданных мун. Население выражает свое отношение к дти мун. Общественные объединения граждан выражают отношение к деятельности мун.
80898. Сущность и содержание муниципального управления 43.04 KB
  Местное самоуправление в РФ форма осуществления народом своей власти обеспечивающая в пределах установленных Конституцией РФ федеральными законами а в случаях установленных федеральными законами законами субъектов РФ самостоятельное и под свою ответственность решение населением непосредственно и или через органы местного самоуправления вопросов местного значения исходя из интересов населения с учетом исторических и иных местных традиций . Дана характеристика основных признаков местного самоуправления отличающих его от...
80899. Система муниципальных правовых актов (МПА), Устав муниципального образования 43.13 KB
  РФ федеральным конституционным законам ФЗ №131ФЗ другим федеральным законам и иным нормативным правовым актам РФ а также конституциям уставам законам иным нормативным правовым актам субъектов РФ. В систему МПА входят: 1 устав МО правовые акты принятые на местном референдуме сходе граждан; 2 нормативные и иные правовые акты ПО МО; 3 правовые акты главы МО постановления и распоряжения главы местной администрации иных ОМС и должностных лиц МС предусмотренных уставом МО. Устав МО и оформленные в виде правовых актов решения...
80900. ПОНЯТИЕ, ОСОБЕННОСТИ, ФУНКЦИИ И ЗАКОНЫ СОЦИАЛЬНОГО УПРАВЛЕНИЯ 44.44 KB
  В основе социального управления лежит приоритет человеческого фактора над всеми иными. Функции управления не являются универсальными так как зависят от вида рассматриваемой организации. Законы управления.
80901. МОДЕЛИ СОЦИАЛЬНОГО УПРАВЛЕНИЯ И ИХ ХАРАКТЕРИСТИКА 44.37 KB
  Под моделью управления следует понимать теоретически выстроенную целостную совокупность представлений о том как выглядит и как должна выглядеть система управления как она воздействует и как должна воздействовать на объект управления как она адаптируется и как должна адаптироваться к изменениям во внешней среде чтобы управляемая организация могла добиваться поставленных целей устойчиво развиваться и обеспечивать свою жизнеспособность. Модель управления включает в себя базовые принципы управления стратегическое видение целевые установки и...
80902. ХАРАКТЕРИСТИКА СРЕДЫ УПРАВЛЕНИЯ. БЛАГОПРИЯТНАЯ, НЕЙТРАЛЬНАЯ, АГРЕССИВНАЯ СРЕДА УПРАВЛЕНИЯ 43.99 KB
  Среда управления это совокупность внутренних и внешних субъектов сил активно влияющих на положение и перспективы организации на эффективность деятельности менеджеров. Типы среды: микросреда мезосреда макросреда. Микросреда внутр среда организации ее собственный персонал и взаимодействие человека с условиями жизни в личном окружении; Мезосреда среда непосредственного окружения партнеры поставщики потребители или социокультурная среда и сфера труда; Макросреда среда...
80903. ПОНЯТИЕ И КЛАССИФИКАЦИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ В УПРАВЛЕНИИ 44.22 KB
  Об информации информационных технологиях и о защите информации ИТ – процессы методы поиска сбора хранения обработки предоставления распространения информации и способы осуществления таких процессов и методов. Информационная технология ИТ процесс использующий совокупность методов и средств реализации операций сбора регистрации передачи накопления и обработки информации на базе программноаппаратного обеспечения для решения управленческих задач экономического объекта. Особенности ИТ: цель процесса – получение информации; предмет...