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


Полезное:

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


Категории:

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






Закрытая транспортная задача





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

· Нахождение исходного опорного решения;

· Проверка этого решения на оптимальность;

· Переход от одного опорного решения к другому.

Нахождение опорного решения.

Неотрицательная матрица Х, удовлетворяющая условиям задачи называется планом (или допустимым планом) задачи. Допустимый план называется оптимальным, если он доставляет минимум целевой функции.

Допустимый план имеющий не более m+n-1 отличных от нуля компонентов xij, называется базисным или опорным. Опорный план, имеющий ровно низкий m+n-1 отличных от нуля компонент, называется невырожденным, а если число отличных от нуля компонент меньше, чем m+n-1, то план называют вырожденным. Другими словами, опорным называется такой план, в котором количество не нулевых перевозок равно сумме количеств поставщиков и потребителей минус единица. Оптимальный план перевозок следует искать только среди множества опорных планов.

Условия задачи и её исходное опорное решение будем записывать в распределительную таблицу. Клетки, в которых поместим грузы, называются занятыми, им соответствуют базисные переменные опорного решения. Остальные клетки – незанятые, или пустые, им соответствуют свободные переменные. В верхнем правом углу каждой клетки будем записывать тарифы. Существует несколько способов нахождения опорного решения, которые рассмотрим на примере решения конкретной задачи.

Пример. У поставщиков А1, А2, А3 сосредоточено соответственно 30, 190 и 250 единиц некоторого однородного груза, который необходимо доставить потребителям В1, В2, В3, В4 в количестве 70, 120, 150 и 130 единиц. Стоимость перевозок единицы груза от поставщиков к потребителям задается матрицей:

 

Пункты отправления (поставщики) Пункты назначения (потребители) Запасы ai
В1 В2 В3 В4
А1          
А2          
А3          
Заявки bj         Σai=470   Σbj=470

 

 

Обозначив количество груза, поставляемого i-м поставщиком j-му потребителю через xij, запишем задачу в математической форме:

Найти: F(x)=4x11+7x12+2x13+3x14+3x21+1x22+2x23+4x24+5x31+6x32+3x33+7x34 min

при ограничениях:

хij ≥ 0.







Date: 2015-07-27; view: 632; Нарушение авторских прав



mydocx.ru - 2015-2024 year. (0.014 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию