Лекции.Орг


Поиск:




Категории:

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

 

 

 

 


Теорема 3




Якщо всі і у транспортній задачі — цілі, то всі у будь-якому ДБР (включаючи й оптимальний) також будуть цілими числами.

Метод потенцiалiв

Метод потенціалів – один з тих, що найчастіше використовують для розв’язання ТЗЛП. Цей метод є реалізацією симплекс-методу в умовах транспортної задачі.

Загальна схема алгоритму

Крок 1. Знайти початковий допустимий розв’язок.

Крок 2. Виділити з числа небазисних змінних ту, що вводиться до базису. Якщо всі небазисні змінні задовольняють умову оптимальності (симплекс-методу), закінчити обчислення; інакше – перейти до кроку 3.

Крок 3. Вибрати змінну, що виводиться з базису (використовуючи умову допустимості) із числа змінних поточного базису; потім знайти новий базисний розв’язок. Повернутися до кроку 2.

Далі ТЗЛП наводимо таблицею (табл. 5.1):

Таблиця 5.1

         
x 11 x 12 x 1 n
         
x 21 x 22 x 2 n
         
         
xm 1 xm 2 xmn

Кількість рядків табл. 5.1 дорівнює кількості виробників m, а кількість стовпчиків – кількості споживачів n. Кожна клітина цієї таблиці відповідає деякій парі “виробник i – споживач j”. Кожному маршруту i, j відповідають вартість перевезення одиниці продукції та обсяг перевезення (кількість продукції) . Вартість перевезень одиниці продукції подано в правих верхніх кутах відповідних клітин. Обсяги виробництва та попиту виражено в кількостях виробів.

Реалізацію алгоритму розглянемо на прикладі задачі, наведеної в табл. 5.2.

Таблиця 5.2

                 
       
                 
       
                 
       
         

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





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 366 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Неосмысленная жизнь не стоит того, чтобы жить. © Сократ
==> читать все изречения...

4328 - | 4003 -


© 2015-2026 lektsii.org - Контакты - Последнее добавление

Ген: 0.009 с.