Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович




Скачать 446.07 Kb.
НазваниеЭкономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович
страница5/6
Дата публикации05.08.2013
Размер446.07 Kb.
ТипМетодические указания
lit-yaz.ru > Математика > Методические указания
1   2   3   4   5   6
^

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



Пусть имеется m поставщиков А1, А2, ..., Аm однородного груза в количествах соответственно а1, а2, .., .аm единиц и n потребителей В1, В2, ..., Вn этого груза, потребность которых составляет соответственно b1, b2 ..., bn единиц.

Известны стоимости перевозок (тариф) единицы груза от i-го поставщика к j-му потребителю - сij (i=1,m; j=1,n).

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

Возможны три ситуации:

1) количество груза у всех поставщиков равно потребности в данном грузе всех потребителей:

или .

2) количество груза у всех поставщиков больше потребности в данном грузе всех потребителей:

или .

3) количество груза у всех поставщиков меньше потребности в данном грузе всех потребителей:

или .

В первом случае модель задачи называется закрытой, во втором и третьем – открытой.

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

В случае превышения запаса над потребностью вводится фиктивный (n + 1)-й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю.

Аналогично вводится фиктивный (m + 1)-й пункт отправления с запасом груза и тарифы полагаются равными нулю. Этим задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

Решение транспортной задачи включает следующие этапы:

1. Нахождение первоначального опорного плана (метод северо-западного угла, метод минимальной стоимости). При этом число заполненных клеток должно быть равно m+n-1.

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

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

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

^ 2. Проверка опорного плана на оптимальность, например, методом потенциалов.
Пример. Четыре предприятия используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 100, 90, 170 и 30 ед. Сырьё сосредоточено в трёх пунктах, а запасы соответственно равны 200, 160, и 140 ед. Тарифы перевозок заданы матрицей

.
Составить такой план перевозок, при котором общая стоимость перевозок является минимальной?

Данная задача является открытой, так как потребности в сырье 100+90+170+30=390 меньше запасов 200+160+140=500. Введём 5-го фиктивного потребителя с потребностью .

Теперь исходные данные задачи запишем в виде таблицы, а опорный план получим методом северо-западного угла.

Заполнение таблицы начинаем с клетки (1,1). х11 = min(a1=200,b1=100)=b1=100 – запасы А1 позволяют полностью удовлетворить потребности пункта В1, значит исключаем этого потребителя из рассмотрения. Теперь запасы пункта A1 считаем равными a1=200-100=100 ед. В оставшейся части таблицы левой верхней клеткой является (1,2): х12 = min(a1,b2)=b2=90 – снова запасы удовлетворяют потребность полностью. Внесём значение в соответствующую клетку и исключим из рассмотрения столбец В2. Запасы пункта А1 считаем равными a1=100-90=10 ед. Теперь «северо-западным углом» является клетка (1,3). х13 = min(a1,b3)=a1=10 – запасы могут удовлетворить потребность пункта B3 частично. Заполняем клетку (1,3) и исключаем из рассмотрения строку A1. Потребности пункта B3 считаем равными b3=170-10=160. х23 = min(a2,b3)=a2=b3=160 – запасы A2 исчерпаны, потребность B3 удовлетворена. Но по правилам мы не можем вычеркнуть и строку и столбец одновременно. Поэтому исключим из рассмотрения сначала столбец B3, а в клетку (2,4) запишем х24 =0 (так как запасы А2 уже исчерпаны) и только теперь вычеркнем строку А2. И так далее. Получим следующую таблицу.
Потребности

Запасы b1=100b2=90b3=170b4=30b5=110β1=12β2=15β3=21β4=16β 5=4a1=200α1=012 10015 9021 10140a2=160α2=-613815 16010 00a3=140α3=-419162612 300 110

Число заполненных клеток равно 7 и m+n-1=3+5-1=7 – план невырожденный. Оптимальный план найдём методом потенциалов.

Теорема. В оптимальном плане транспортной задачи заполненным клеткам отвечают равенства , а пустым неравенства .

Расставим потенциалы:

, положим , тогда.

(Обычно равным нулю принимают потенциал строки или столбца с наибольшим числом заполненных клеток.)

Теперь проверим пустые клетки на выполнение неравенства .

.

Для клеток (1,4), (1,5), (2,2) неравенство не выполняется, значит опорный план не является оптимальным. В одну из этих клеток нужно "ввезти" груз. Выбираем ту, для которой разница максимальна, т. е. в (1,5). Строим цикл.

Цикл перерасчёта таблицы - это последовательность ячеек, начинающаяся и заканчивающаяся в одной и той же клетке, с вершинами, лежащими в занятых клетках, кроме одной.

Вершина цикла – клетка, в которой происходит поворот под прямым углом.

"Перемещаем" груз по следующим правилам:

  1. каждой из клеток, связанных циклом присваивается знак: пустой ячейке "+", остальным - поочерёдно знаки "-" и "+" .

  2. среди минусовых клеток находим число и прибавляем его к числам, стоящим в плюсовых клетках, и вычитаем из чисел, стоящих в минусовых клетках; остальные клетки вне цикла остаются без изменения.

В нашем примере цикл образуют шесть ячеек: (1,5) – пустая, для которой не выполняется неравенство, и (3,5), (3,4), (2,4), (2,3), (1,3) – заполненные.

х = min(10,0,110)=0. Значит в плюсовые клетки "завозим" 0 ед. груза, из минусовых "вывозим". Получим новый опорный план:
Потребности

Запасы b1=100b2=90b3=170b4=30b5=110β1=12β2=15β3=21β4=12β 5=0a1=200α1=012 10015 9021 10140 0a2=160α2=-613815 160100a3=140α3=019162612 300 110

Расставим потенциалы и проверим пустые клетки на выполнение неравенства . Для клетки (2,2) неравенство не выполняется. Строим новый цикл.

х = min(90,160)=90. Значит в плюсовые клетки "завозим" 90 ед. груза, из минусовых "вывозим". Получим новый опорный план:
Потребности

Запасы b1=100b2=90b3=170b4=30b5=110β1=12β2=15β3=21β4=12β 5=0a1=200α1=012 1001521 100140 0a2=160α2=-6138 9015 70100a3=140α3=019162612 300 110

Расставим потенциалы и проверим пустые клетки на выполнение неравенства . Полученный план является оптимальным.

Ответ: ,

=100*12+100*21+90*8+70*15+30*12=5430.

Так как пятый потребитель является фиктивным, то 110 ед. груза у третьего поставщика останутся невостребованными.

1   2   3   4   5   6

Похожие:

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconОтчет по лабораторной работе №1 по предмету «Экономико-математические...
Предложения (рекомендации) лицу, ответственному за принятие решений, по оптимальному управленческому поведению 6

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания к выполнению контрольных...
В методических указаниях приведены программа изучения курса, контрольные вопросы, контрольные задания и методические указания по...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания по дисциплине «Экономика организации»
Методические указания составлены в соответствии с примерной программой по дисциплине

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по выполнению курсового проекта с использованием...
Изложены общие указания по курсовому проектированию, приведены задания на проекты, даны методические указания по отдельным этапам...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по анализу финансового 12 состояния организации 12
Методические указания предназначены для выполнения курсовых работ по дисциплине «Анализ хозяйственной деятельности» для студентов...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания к контрольной работе по дисциплине «Экономический...
Методические указания предназначены для обучающихся по специальности 051800 «Учет и аудит (по отраслям)»

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и контрольные задания для студентов заочной...
Методические указания составлены в соответствии с Учебно-методическим комплексом дисциплины на основе требований Государственного...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания по контрольно-курсовой работе по дисциплине эксплуатацияэвми систем
Методические указания по ккр составлены доц каф ЭВМ лебеденко Ю. И. и обсуждены на заседании кафедры ЭВМ факультета кибернетики

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания к лабораторным работам по курсу «Информатика»
Методические указания предназначены для выполнения лабораторных работ по написанию программ на языке C. Работы проводятся с использованием...

Экономико-математические модели методические указания и задания к типовой работе утёмов вячеслав Викторович iconМетодические указания и задания к выполнению курсовой работы по курсу «базы данных»
Методические указания и задания к выполнению курсовой работы по курсу «Базы данных» (направление подготовки 050103 ”Программная инженерия”)....



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница