Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод потенціалів.

Читайте также:
  1. FAST (Методика быстрого анализа решения)
  2. I Методические указания к решению практических
  3. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  4. I. 2.4. Принципы и методы исследования современной психологии
  5. I. МЕТОДОЛОГИЧЕСКОЕ ВВЕДЕНИЕ
  6. I. Методы изучения фактического питания
  7. I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

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

Щоб опорний план був оптимальним, необхідно і достатньо, щоб виконувались умови:

– для базисних клітинок ;

– для вільних клітинок ,

де потенціали і відповідно (, ).

Розглянемо застосування цього методу на прикладі 11. Потенціали для постачальників – , для споживачів – .

 

aі bj        
v1 v2 v3 v4
  u1 2 3 65 2 4
  u2 2 60 4 6 20 5
  u3 45 1 5 15 4 45 5

 

Обчислимо кількість базисних невідомих , маємо 6 заповнених клітинок, тому опорний план не вироджений. Запишемо рівняння для заповнених (базисних) клітинок

 

 

Нехай , тоді з системи рівнянь можемо знайти інші потенціали , , , , , .

Перевіримо виконання умови оптимальності для вільних клітин

 

0–1<2 виконано

0+2<3 виконано

0+3<4 виконано

2–1<2 виконано

2+2<6 виконано

2+2<5 виконано

 

Всі умови виконуються, план оптимальний.

 

 

Обчислимо вартість перевезення

 

Приклад 12.

aі bj        
  5 1 2 3
  6 3 7 1
  4 5 3 2
  2 4 6 8

Розв’язання.

Заповнимо таблицю методом мінімальної вартості (див. приклад 11).

 

aі bj        
  5 300 1 2 3
  6 3 7 200 1
  4 5 300 3 200 2
  230 2 120 4 350 6 8

 

Перевіримо цей план на оптимальність за допомогою методу потенціалів. Запишемо рівняння для заповнених клітинок

 

, , ,

, , .

 

Нехай , обчислимо інші потенціали u 2=–1, u 3=0, u 4=3, v 1=–1, v 2=1, v 3=3, v 4=2.

Результати занесемо в таблицю:

 

aі bj        
v 1= –1 v 2=1 v 3=3 v 4=2
  u 1=0 5 300 1 2 3
  u 2= –1 6 3 7 200 1
  u 3=0 4 5 300 3 200 2
  u 4=3 230 2 120 4 350 6 8

 

Перевіримо виконання нерівностей:

 

або

 

Умова оптимальності не виконується, потрібно поліпшити опорний план.

Поліпшити план можна за допомогою циклу перерахунку.

 

 


Дата добавления: 2015-08-05; просмотров: 52 | Нарушение авторских прав


Читайте в этой же книге: Задачі математичного і лінійного програмування | Математична модель задачі про використання сировини. | Геометричний метод розв’язування ЗЛП | Зведення ЗЛП до канонічної форми | Алгоритм однократного заміщення Жордана-Гауса | Симплексний метод | Отримання допустимого базисного розв’язку | Двоїста задача | Задача цілочисельного програмування. | ЗАВДАННЯ 2. |
<== предыдущая страница | следующая страница ==>
Транспортна задача.| Цикл перерахунку

mybiblioteka.su - 2015-2024 год. (0.011 сек.)