Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Табличная форма представления транспортной модели






 

^~^^_^ Потребители ^^" ---^^ ресурса Источники ^~" --^^^ ресурса ^~~~\                   п   Наличие ресурсов
  хп   с„ х\г   Сп Х\1 С, з   х\п С|я А
  *21   с21 х21   С22 хгъ с73   х2п Сгп Аг
                         
т хт\   Ст\ хт?   С„а хтЪ С„в   хтп г Ат
11отребности в > ссурсах   В\     Вг     в3   в„    

Для формализованного изложения методов решения транс­портной задачи сформулируем основные понятия, родственные введенным для общей задачи линейного программирования.

Допустимым решением транспортной задачи называется такая совокупность значений величин Ху, /= \,..., т, ]= \,..., п, для кото­рой выполняются все ограничения. Допустимое решение, при котором целевая функция достигает минимума (максимума), на­зывается оптимальным. Среди допустимых решений выделяют оазисные, в которых не более (т+п— I) величин Ху отличаются от нуля, а остальные строго равны нулю. Наличие таких реше­ний—общее свойство задач линейного программирования; ко-мичество ненулевых переменных в базисном решении не может превышать числа независимых ограничений. В данном случае в идаче имеется (т + п) ограничений типа (15.2), (15.3), но с уче­том балансового условия (15.4) независимых ограничений оста­ется только (т+п—1). Следовательно, в базисном решении транспортной задачи должно быть не более (т+п— 1) ненуле-пых переменных. Как и в общей задаче линейного программиро-


вания, при поиске оптимального решения транспортной задачи можно ограничиться анализом только базисных решений.

В матричном представлении задачи (табл. 84) клетки, в кото­рых величины Хц отличны от нуля, называют занятыми, а все ос­тальные — свободными. Таким образом, любое базисное решение содержит не более (т +п— 1) занятых клеток. Если число заня­тых клеток зш) в точности равно (т +п— 1), решение называ­ется невырожденным, в противном случае — вырожденным. По­скольку в рассматриваемом ниже алгоритме мы будем опериро­вать только базисными решениями, то в ходе решения для конт­роля необходимо рассчитывать величину Кзш. Если ^зан > (т + п 1)> то решение на очередной итерации найдено неверно и необходимо искать ошибку. В вырожденном решении некоторые базисные переменные равны нулю; соответствующие им клетки заполняются нулями и считаются условно занятыми.

Итерационная процедура решения транспортной задачи, как и в общей задаче линейного программирования, начинается с поиска хотя бы одного допустимого базисного решения; его так­же называют опорным решением (планом). Затем опорный план проверяется на оптимальность, при необходимости улучшается (с заменой одной из базисных переменных) и т. д.

В отличие от первого опорного плана симплекс-метода, име­ющего чисто условный характер, распределительный метод пред­полагает составление реального опорного плана; методы его на­хождения очень важны. Чем ближе опорный план к оптимально­му, тем меньше итераций необходимо будет произвести для дос­тижения оптимального решения, тем меньше затраты времени и выше точность вычислений.

Существует несколько методов нахождения опорного реше­ния; любой из них позволяет сделать это, но они существенно различаются по количеству вычислительных операций, которые необходимо осуществить, и по степени близости опорного реше­ния к оптимальному. Как правило, чем проще метод, тем хуже опорное решение (хотя не всегда это так).

Мы рассмотрим два наиболее часто используемых на практи­ке метода: один из простейших — метод минимального (макси­мального) элемента, полезный прежде всего в дидактическом от­ношении, и метод аппроксимации, требующий более сложных вычислений, но дающий опорное решение, более близкое к оп­тимальному.


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал