Реферат: Транспортная задача линейного программирования

Международныйуниверситет

Калининградский филиал

Заочное отделениеСпециальность-менеджментКурсовая работа

по дисциплинеэкономико–математические методы

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

линейного программирования

Курсовая работа

по высшей математике

Тема:

”Транспортная задача линейного программирования”

Содержание:

1. История зарождения и создания линейногопрограммирования.

2. Транспортная задача. Общая постановка, цели, задачи.Основные типы, виды моделей.

3. Методы составления начального опорного плана.

4. Понятие потенциала и цикла.

5. Критерий оптимальности базисного решения транспортнойзадачи. Методы отыскания оптимального решения.

6. Задача, двойственная к транспортной.

7. Пример решения транспортной задачи.

8. Выводы.

1.История зарождения и создания линейногопрограммирования.

Каждыйчеловек ежедневно, не всегда осознавая это, решает проблему: как получитьнаибольший эффект, обладая ограниченными средствами. Наши средства и ресурсывсегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Нетрудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобыдостичь наибольшего эффекта, имея ограниченные средства, надо составить план,или программу действий. Раньше план в таких случаях составлялся “на глазок”(теперь, впрочем, зачастую тоже). В середине XX века былсоздан специальный математический аппарат, помогающий это делать “по науке”.Соответствующий раздел математики называется математическим программированием.Слово “программирование” здесь и в аналогичных терминах (“линейноепрограммирование, динамическое программирование” и т.п.) обязано отчастиисторическому недоразумению, отчасти неточному переводу с английского.По-русски лучше было бы употребить слово “планирование”. С программированиемдля ЭВМ математическое программирование имеет лишь то общее, что большинствовозникающих на практике задач математического программирования слишкомгромоздки для ручного счета, решить их можно только с помощью ЭВМ,предварительно составив программу. Временем рождения линейного программированияпринято считать 1939г., когда была напечатана брошюра Леонида ВитальевичаКанторовича “Математические методы организации и планирования производства”.Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручногосчета, а быстродействующих вычислительных машин в то время не существовало,работа Л.В.Канторовича осталась почти не замеченной.

Свое второе рождение линейное программирование получило в начале пятидесятыхгодов с появлением ЭВМ. Тогда началось всеобщее увлечение линейнымпрограммированием, вызвавшее в свою очередь развитие других разделовматематического программирования. В 1975 году академик Л.В.Канторович иамериканец профессор Т.Купманс получили Нобелевскую премию по экономическимнаукам за “вклад в разработку теории и оптимального использования ресурсов вэкономике”.

В автобиографии, представленной вНобелевский комитет, Леонид Витальевич Канторович рассказывает о событиях,случившихся в 1939 году. К нему, 26-летнему профессору-математику, обратилисьза консультацией сотрудники лаборатории планерного треста, которым нужно былорешить задачу о наиболее выгодном распределении материала между станками. Этазадача сводилась к нахождению максимума линейной функции, заданной намногограннике. Максимум такой функции достигался в вершине, однако число вершинв этой задаче достигало миллиарда. Поэтому простой перебор вершин не годился.Леонид Витальевич писал: “оказалось, что эта задача не является случайной. Яобнаружил большое число разнообразных по содержанию задач, имеющих аналогичныйматематический характер: наилучшее использование посевных площадей, выборзагрузки оборудования, рациональный раскрой материала, распределениетранспортных грузопотоков… Это настойчиво побудило меня к поиску эффективногометода их решения”. И уже летом 1939 года была сдана в набор книгаЛ.В.Канторовича “Математические методы организации и планированияпроизводства”, в которой закладывались основания того, что ныне называетсяматематической экономикой.

Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, былиобъявлены ересью, и его работа была прервана. Концепции Леонида Витальевичавскоре после войны были переоткрыты на западе. Американский экономист Т.Купмансв течение многих лет привлекал внимание математиков к ряду задач, связанных своенной тематикой. Он активно способствовал тому, чтобы был организованматематический коллектив для разработки этих проблем. В итоге было осознано,что надо научиться решать задачи о нахождении экстремумов линейных функций намногогранниках, задаваемых линейными неравенствами. По предложению Купмансаэтот раздел математики получил название линейного программирования.

Американский математик А.Данциг в 1947 году разработал весьма эффективныйконкретный метод численного решения задач линейного программирования (онполучил название симплекс метода). Идеи линейного программирования в течениепяти шести лет получили грандиозное распространение в мире, и имена Купманса иДанцига стали повсюду широко известны.

Примерно в это время Купманс узнал, что еще довойны в далекой России уже было сделано нечто похожее на разработку началлинейного программирования. Как легко было бы Данцигу и Купмансу проигнорироватьэту информацию! Маленькая книжица, изданная ничтожным тиражом, обращенная дажене к экономистам, а к организаторам производства, с минимумом математики, безчетко описанных алгоритмов, без доказательств теорем – словом, стоит липринимать такую книжку во внимание… Но Купманс настаивает на переводе и изданиина западе книги Канторовича. Его имя и идеи становятся известны всем. Воздадимдолжное благородству американского ученого!

А самому Леониду Витальевичу – какестественно было бы ему, испытав первые грозные удары ретроградов, остеречьсяот “грехов” молодости, забыть про всю эту экономику и вернуться к математике.Но Л.В.Канторович продолжает писать математические работы, навеянныеэкономическими идеями, участвует и в конкретных разработках на производстве.При этом (одновременно с Данцигом, но, не зная его работ) он разрабатываетметод, позже названный симплекс-методом. Как только в 50-е годы образуетсямаленький просвет, и кое-что из запретного становится возможным, онорганизует группу студентов на экономическом факультете ЛГУ для обученияметодам оптимального планирования. А, начиная с 1960 года, Леонид Витальевичзанимается только экономической и связанной с нею математической проблемами.Его вклад в этой области был отмечен Ленинской премией в 1965 году (присужденаему совместно с В.С.Немчиновым и В.В.Новожиловым) и, как уже говорилось,Нобелевской премией в 1975 году.

2.Транспортная задача. Общая постановка, цели, задачи.Основные типы, виды моделей.

Под названием “транспортнаязадача” объединяется широкий круг задач с единой математической моделью. Данныезадачи относятся к задачам линейного программирования и могут быть решенысимплексным методом. Однако матрица системы ограничений транспортной задачинастолько своеобразна, что для ее решения разработаны специальные методы. Этиметоды, как и симплексный метод, позволяют найти начальное опорное решение, азатем, улучшая его, получить оптимальное решение.

В общей постановкетранспортная задача состоит в отыскании оптимального плана перевозокнекоторого однородного груза с />баз /> /> потребителям />.

Различают два типатранспортных задач: но критерию стоимости (план перевозок оптимален,если достигнут минимум затрат на его реализацию) и по критерию времени(план оптимален, если на его реализацию затрачивается минимум времени).

(1.1)

Обозначим количество груза, имеющегося накаждой из /> баз(запасы), соответственно />, а общее количество имеющегося в наличии груза–/>:

/>;

(1.2)

заказы каждого из потребителей(потребности) обозначим соответственно/>, а общее количество потребностей – />:

/>,

(1.3)

Тогда при условии

(1.4)

мы имеем закрытую модель, а приусловии

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

Очевидно, в случае закрытоймодели весь имеющийся в наличии груз развозится полностью, и все потребностизаказчиков полностью удовлетворены; в случае же открытой модели либо всезаказчики удовлетворены и при этом на некоторых базах остаются излишки груза />, либо весь груз оказывается израсходованным, хотя потребностиполностью не удовлетворены />.

Так же существуют одноэтапные моделизадач, где перевозка осуществляется напрямую от, например, базы или заводаизготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочныйпункт”, например – склад.

План перевозок с указанием запасов ипотребностей удобно записывать в виде следующей таблицы, называемой таблицейперевозок:

Пункты

Отправления

Пункты назначения Запасы

…

… … … … … …

…

Потребности

…

или

Условие /> или /> означает, с какой задачей мы имеем дело, с закрытоймоделью или открытой моделью транспортной задачи. Переменное /> означает количество груза, перевозимого с базы /> потребителю />: совокупность этих величин образует матрицу (матрицуперевозок).

Очевидно, переменные /> должны удовлетворять условиям:

(2.1.1)

(2.1)

/>/>

Система (2.1) содержит /> уравнений с /> неизвестными. Её особенность состоит в том, чтокоэффициенты при неизвестных всюду равны единице. Кроме того, все уравнениясистемы (2.1) могут быть разделены на две группы: первая группа из тпервых уравнений (“горизонтальные” уравнения) и вторая группа из постальных уравнений (“вертикальные” уравнения). В каждом из горизонтальныхуравнений содержатся неизвестные с одним и тем же первым индексом (ониобразуют одну строку матрицы перевозок), в каждом из вертикальных уравненийсодержатся неизвестные с одним и тем же вторым индексом (они образуют одинстолбец матрицы перевозок). Таким образом, каждая неизвестная встречается всистеме (2.1) дважды: в одном и только одном горизонтальном и в одном и толькоодном вертикальном уравнениях.

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

(2.1’)

где символы />и />означают суммирование по соответствующему индексу.Так, например,

При этом легко заметить,что под символами такого суммирования объединяются только свободные неизвестные(здесь />, />).

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

или короче

(2.2)

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

(2.2’)

Так как для закрытой модели транспортнойзадачи />, то полученные нами уравнения (2.2) и (2.2’) одинаковыи, исключив из одного из них неизвестное />, мы получим уравнение-тождество 0=0, котороеиз системы вычеркивается.

/>Итак, преобразование системы (2.1) свелось к замене двухуравнений (первого горизонтального и первого вертикального) уравнением (2.2).Остальные уравнения остаются неизменными. Система приняла вид

(2.3)

В системе (2.3) выделенуказанный выше базис: базисные неизвестные из первых т уравненийобразуют первый столбец матрицы перевозок, а базисные неизвестные остальныхуравнений образуют первую строку матрицы перевозок без первого неизвестного /> [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется/> уравнений, выделенный базис содержит /> неизвестных, а, следовательно, и ранг системы (2.1) />.

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

Совокупность тарифов /> также образует матрицу, которую можно объединить с матрицей перевозоки данными о запасах и потребностях в одну таблицу:

Пункты

Отправления

Пункты назначения Запасы

…

… … … … … …

…

Потребности

…

или

/> /> /> /> /> /> /> /> /> /> />

Сумма всех затрат, т. е.стоимость реализации данного плана перевозок, является линейной функциейпеременных />:

(2.4)

Требуется в области допустимых решений системыуравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).

Таким образом, мы видим, чтотранспортная задача является задачей линейного программирования. Для ее решенияприменяют также симплекс-метод, но в силу специфики задачи здесь можно обойтисьбез симплекс-таблиц. Решение можно получить путем некоторых преобразованийтаблицы перевозок. Эти преобразования соответствуют переходу от одного планаперевозок к другому. Но, как и в общем случае, оптимальное решение ищется средибазисных решений. Следовательно, мы будем иметь дело только с базисными (илиопорными) планами. Так как в данном случае ранг системы ограничений-уравненийравен /> то среди всех /> неизвестных /> выделяется /> базисных неизвестных, а остальные />·/>

неизвестных являются свободными. В базисном решениисвободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают,оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок,представляющей опорный план, мы имеем /> заполненных и />·/> пустых клеток.

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

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

Замечание 2. Под величинами />, очевидно, не обязательно подразумевать только тарифы. Можно такжесчитать их величинами, пропорциональными тарифам, например, расстояниями от баздо потребителей. Если, например, /> выражены в тоннах, а /> в километрах, то величина />, определяемая формулой (2.4), является количествомтонно-километров, составляющих объем данного плана перевозок. Очевидно, чтозатраты на перевозки пропорциональны количеству тонно-километров и,следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицурасстояний.

3. Методы составления начального опорного плана.

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

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

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

Начиная с первоначальноданной таблицы и повторив /> раз описанный шаг, мы придем к “таблице”, состоящейиз одной строки и одного столбца (иначе говоря, из одной пустой клетки).Другими словами, мы пришли к задаче с одной базой и с одним потребителем,причем потребности этого единственного заказчика равны запасу груза на этойединственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу иудовлетворяем потребность последнего заказчика. В результате, совершив /> шагов, мы и получим искомый опорный план.

Замечание. Может случиться, что уже на некотором (но не напоследнем!) шаге потребность очередного заказчика окажется равной запасу грузана очередной базе. Тогда после заполнения очередной клетки объем таблицы какбы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мыдолжны считать, что уменьшение объема таблицы происходит либо на один столбец,а на базе сохраняется “остаток” равный нулю, либо на одну строку, а у заказчикаеще осталась неудовлетворенная “потребность” в количестве нуля единиц груза,которая и удовлетворяется на одном из следующих шагов. Этот нуль (“запас” или“потребностью” – безразлично) надо записать в очередную заполняемую клетку наодном из последующих шагов. Так как при этом оказывается равной нулю одна избазисных неизвестных, то мы имеем дело с вырожденным случаем.

Различиеметодов отыскания первого опорного плана состоит в различии способов наборазаполняемой клетки.

1.Диагональный метод, или метод северо-западного угла. При этомметоде на каждом шаге построения первого опорного плана заполняется леваяверхняя клетка (северо-западный угол) оставшейся части таблицы. При такомметоде заполнение таблицы начинается с клетки неизвестного /> и заканчивается в клетке неизвестного />, т. е. идет как бы по диагонали таблицы перевозок.

Пример.

Пункты

Отправления

Пункты назначения Запасы

70 50 15 80 70 300 170 110 20

80 90 40 60 85 150 80 70

50 10 90 11 25 250 50 200 Потребности 170 110 100 120 200 700

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

Теперь переходим кзаполнению клетки для неизвестного /> и т.д.

Через шесть шагов у насостанется одна база /> с запасом груза (остатком от предыдущего шага) />и один пункт /> с потребностью/>. Соответственно этому имеется одна свободная клетка,которую и заполняем, положив />. План составлен. Базис образован неизвестными />. Правильность составленного плана легко проверить, подсчитав суммычисел, стоящих в заполненных клетках по строкам и столбцам.

Общий объем перевозок в тонно-километрах дляэтого плана составит

/>.

2.Метод наименьшейстоимости. При этом методе на каждомшаге построения опорного плана первою заполняется та клетка оставшейся частитаблицы, которая имеет наименьший тариф. Если такая клетка не единственная, тозаполняется любая из них.

Пример.

Пункты

Отправления

Пункты назначения Запасы

70 50 15 80 70 300 20 100 180

80 90 40 60 85 150 150

50 10 90 11 25 250 110 120 20 Потребности 170 110 100 120 200 700

В данном случае заполнениетаблицы начинается с клетки для неизвестного />, длякоторого мы имеем значение />, наименьше из всех значений />. Эта клетка находится на пересечении третьей строки и второго столбца,соответствующим третьей базе /> и второму заказчику />. Третья база /> может полностью удовлетворить потребность второгозаказчика /> />. Полагая />, вписываем это значение в клетку /> и исключаем из рассмотрения второй столбец. На базе /> остается изменённый запас />. В оставшейся новой таблице с тремя строками /> и четырьмя столбцами /> клеткой с наименьшим значением /> клетка, где/>. Заполняем описанным выше способом эту клетку ианалогично заполняем следующие клетки. В результате оказываются заполненными(в приведенной последовательности) следующие клетки:

/>.

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

/>.

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

Кроме рассмотренных выше способов иногдаиспользуется, так называемый, метод Фогеля. Суть его состоит в следующем: Враспределительной таблице по строкам и столбцам определяется разность междудвумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке(столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом.Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются.На каждом этапе загружается только одна клетка. Распределение грузапроизводится, как и ранее.

4.Понятие потенциала и цикла.

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

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

1. Одно из неизвестных последовательности свободное, авсе остальные – базисные.

2. Каждые два соседних в последовательности неизвестныхлежат либо в одном столбце, либо в одной строке.

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

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

Второе условие означает, чтоу двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

старые значения: />;

новые значения: />

Очевидно, если снабдитьвершины цикла поочередно знаками “+” и “–“, приписав вершине в свободной клеткезнак “+”, то можно сказать, что в вершинах со знаком “+” число /> прибавляется к прежнему значению неизвестного, находящегося в этойвершине, а в вершинах со знаком “–“ это число /> вычитается из прежнего значения неизвестного, находящегося в этойвершине.

Замечание. Так как число вершин в цикле всегда четно, то,возвращаясь в свободную клетку, мы должны будем приписать ей знак “+”, т. е.тот знак, который ей уже приписан при выходе из нее. Это очень существенноеобстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, вкаком направлении обходится цикл при “означивании” вершин.

Если в качестве /> выбрать наименьшее из чисел, стоящих в вершинах, снабженных знаком“–“, то, по крайней мере, одно из прежних базисных неизвестных примет значениенуль, и мы можем перевести его в число свободных неизвестных, сделав вместонего базисным то неизвестное, которое было свободным.

Так, например, врассмотренном выше цикле имеем отрицательные вершины /> и />; следовательно, выбрав />, мы получаем:

старые значения: />;

новые значения: />

т. е. вместо прежнего базисного решения получаем новоебазисное решение:

Пункты

Отправления

Пункты назначения Запасы

70 50 15 80 70 300 90 110 100

80 90 40 60 85 150 80 70

50 10 90 11 25 250 50 200 Потребности 170 110 100 120 200 700

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

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

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

Описанное вышепреобразование таблицы перевозок, в результате которого преобразуется базис,называется пересчетом по циклу.

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

Выясним теперь, какпересчет по циклу влияет на общий объем затрат на перевозки и при каком условииэти затраты становятся меньше.

Пусть /> – некоторое свободное неизвестное, для которого мы построили цикл иосуществили пересчет по циклу с некоторым числом />. Есливершине цикла, находящейся в /> строке и /> столбце таблицы перевозок, приписан знак “+”, тозначение неизвестного />,находящегося в этой вершине, увеличивается на />, что в свою очередь вызываетувеличение затрат на />. где /> – тариф, соответствующий этой клетке; если же указанной вершинеприписан знак “–”, то значение неизвестного /> уменьшается на />, что вызывает уменьшение затрат на />.

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

Теперь, очевидно, мы можем,заключить, что в целом при пересчете но циклу, соответствующему свободномунеизвестному /> общий объем затрат на перевозки изменится напроизведение алгебраической суммы тарифов на />, т. е. на величину />. Следовательно, если алгебраическая сумма тарифов длянекоторого свободного неизвестного /> отрицательна />, то пересчет по циклу, соответствующему этому неизвестному,приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если жеалгебраическая сумма тарифов положительна />, то пересчет по соответствующему циклу приведет к увеличению общейсуммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю />, то пересчет по соответствующему циклу не изменит общую сумму затрат(два различных базисных плана требуют одинаковых затрат на их реализацию).

Так, например, для цикла /> в рассмотренной задаче алгебраическая сумма тарифов

/>.

Значит, пересчет по этому циклу снижает расходы. Идействительно, осуществив такой пересчет, мы получаем план, по которому объемперевозок в тонно-километрах составляет

тогда как по исходному плану онсоставил />. Имеем снижение объема перевозок на 1200тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифовв данном случае равна –15, а пересчет по циклу осуществляется с помощью числа /> (изменение затрат равно />).

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

/>,

так что

(4.1)

/>,

где /> – тарифы, соответствующие клеткам, заполненным базисныминеизвестными. Эти числа /> и /> называются потенциалами соответствующих баз ипотребителей.

Зная потенциалы, легковычислить алгебраическую сумму тарифов. Действительно, если в алгебраической сумметарифов по циклу, соответствующему свободному неизвестному />, заменить тарифы базисных клеток их выражениями через потенциалы поформулам (4.1), то, в силу чередования знаков при вершинах цикла, всепотенциалы, кроме /> и /> сократятся, и мы получим:

/>.

Так, например, для цикла /> в рассмотренной выше задаче имеем

/>.

Для базисных клеток сумма потенциаловстроки и столбца, в которых находится эта клетка, равна тарифу, соответствующемуэтой клетке; если же клетка для неизвестного /> свободная, то сумму потенциалов

(4.2)

называют косвенным тарифом этой клетки.Следовательно, алгебраическая сумма тарифов для свободной клетки /> равна разности ее настоящего (“истинного”) и косвенного тарифов:

(4.3)

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

Потенциалы можно найти изсистемы равенств (4.1), рассматривая их как систему /> уравнений с /> неизвестными. Так как неизвестных здесь на единицубольше, чем уравнений, то, по крайней мере, один из потенциалов мы можемвыбрать произвольно, положив, например, />; тогда остальные потенциалы легко определяются из уравнений(4.1).

Например, для плана,полученного по диагональному методу в рассмотренной выше задаче, имеем

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

Положив,например, />, получаем значения потенциалов:

/> />

Найдем теперь косвенные тарифы для свободных клеток исравним их с истинными тарифами:

/>/>

Для клеток с неизвестными /> и /> косвенные тарифы больше истинных. Следовательно, дляних мы будемиметь отрицательные алгебраические суммы тарифов:

Значение /> мы уже имели раньше, вычисляя алгебраическую сумму тарифов для этойклетки непосредственно по циклу.

Замечание 1. Подсчитывая косвенные тарифы как суммы соответствующихпотенциалов, полезно не пропускать и клетки с базисными неизвестными(заполненные клетки). Для этих клеток сумма потенциалов равна истинному тарифу;последнее может служить проверкой правильности найденных значении потенциалов.

Замечание 2. Можно показать, что если сумму всех затрат по данномуплану перевозок выразить через свободные неизвестные [для этого надо исключитьбазисные неизвестные из выражения для S, см.формулу (2.4)], то коэффициент при каждом из таких неизвестных будет равеналгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок.Это еще раз подтверждает, что пересчет по циклам является специфической формойприменения симплекс-метода к решению транспортной задачи.

5. Критерий оптимальности базисного решения транспортнойзадачи. Методы отыскания оптимального решения.

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

Отсюда вытекает способотыскания оптимального решения транспортной задачи, состоящий в том, что, имеянекоторое базисное решение, вычисляют алгебраические суммы тарифов для всехсвободных клеток. Если критерий оптимальности выполнен, то данное решениеявляется оптимальным; если же имеются клетки с отрицательными алгебраическимисуммами тарифов, то переходят к новому базису, производя пересчет по циклу,соответствующему одной из таких клеток. Полученное таким образом новое базисноерешение будет лучше исходного – затраты на его реализацию будут меньшими. Длянового решения также проверяют выполнимость критерия оптимальности и в случаенеобходимости снова совершают пересчет по циклу для одной из клеток сотрицательной алгебраической суммой тарифов и т. д.

Через конечное числошагов приходят к искомому оптимальному базисному решению.

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

В зависимости от методовподсчета алгебраических сумм тарифов для свободных клеток различают два методаотыскания оптимальногорешения транспортной задачи:

1. Распределительный метод. При этомметоде для каждой пустой клеткистроят цикл и для каждого цикла непосредственно вычисляют алгебраическую суммутарифов.

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

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

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

Следует иметь в виду, чтопотенциалы (так же как и циклы) для каждого нового базисного плана определяютсязаново.

Выше рассматривалась закрытаямодель транспортной задачи, с правильным балансом, когда выполняется условие(1.3). В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

å аi > å bj ( где i=1,...,m; j=1,...,n );

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

å аi< å bj ( где i=1,...,m; j=1,...,n );

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого,сверх имеющихся n пунктов назначения В1, B2,…, Bn, введём ещё один, фиктивный, пункт назначения Bn+1,которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 = å аi — å bj ( где i=1,...,m; j=1,...,n ),

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем считать равной нулю. Введением фиктивного пункта назначения Bn+1 с его заявкой bn+1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести кобычной транспортной задаче с правильным балансом, если ввести фиктивныйпункт отправления Am+1 с запасом am+1 равнымнедостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.

6. Задача, двойственная к транспортной.

Построим задачу,двойственную к транспортной. С этой целью вспомним, что каждому пунктуотправления /> и назначения /> отвечает определенное ограничение

(6.1)

В то же время каждому ограничению из (6.1)сопоставляется определенная неизвестная в двойственной задаче. Тем самымустанавливается соответствие между всеми пунктами /> и /> и всеми неизвестными двойственной задачи.

Обозначим неизвестную вдвойственной задаче, отвечающую пункту отправления />, через />, а пункту назначения /> – через />.

Каждому неизвестному втранспортной задаче соответствует ограничение, связывающее неизвестные вдвойственной задаче. Неизвестное /> входит ровно в два ограничения системы (6.1): одно изних отвечает пункту />, а другое – пункту />. В обоих этих уравнениях коэффициент при /> равен 1. Поэтому соответствующее /> ограничение в двойственной задаче имеет вид

/> <td/>

(6.2)

/> />.

Правая часть неравенства (6.2) равна />, потому что именно с этим коэффициентом неизвестная /> входит в минимизируемую формулу (2.4).

Оптимизируемая форма двойственной задачиимеет вид

(6.3)

Таким образом, задача двойственная ктранспортной формулируется следующим образом. При ограничениях (6.2) максимизироватьформулу (6.3). Подчеркнем, что знак значений неизвестных /> и /> может быть произвольным.

Предположим, что нам известно некотороедопустимое базисное решение транспортной задачи, в котором все базисныенеизвестные строго положительны. Это решение оптимально лишь в том случае,когда соответствующая ей система оказывается совместной. Эта система возникаетиз системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным /> заменить точнымиравенствами.

В итоге приходим к соотношению:

(6.4)

/> (для всех свободных неизвестных />)

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

7.Пример решения транспортной задачи.

В городе N имеется 4склада Аi, на которых хранится ткань (в рулонах) и 5 магазинов Bj, занимающихся продажей ткани. Ниже, в таблице, приведены данные поколичеству рулонов на каждом складе, запросы магазинов и стоимость перевозкиодного рулона из Аi в Bj. Необходимо составить такой план перевозок, прикотором запросы магазинов будут удовлетворены при минимальной суммарнойстоимости перевозок.

/> Магазины

Склад

(b1=40)

(b2=50)

(b3=15)

(b4=75)

(b5=40)

А1 (а1=50)

1,0 2,0 3,0 2,5 3,5

А2(а2=20)

0,4 3,0 1,0 2,0 3,0

А3(а3=75)

0,7 1,0 1,0 0,8 1,5

А4(а4=80)

1,2 2,0 2,0 1,5 2,5

В данном случае Σai=225>Σbj=220 => имеем дело с открытой моделью транспортнойзадачи. Сведем ее к закрытой введением фиктивного магазина B6 с потребностью b5=225-220=5 и стоимостью перевозок сi6=0.Имеем таблицу:

/> Магазины

Склад

(b1=40)

(b2=50)

(b3=15)

(b4=75)

(b5=40)

(b6=5)

А1 (а1=50)

1,0 2,0 3,0 2,5 3,5

А2(а2=20)

0,4 3,0 1,0 2,0 3,0

А3(а3=75)

0,7 1,0 1,0 0,8 1,5

А4(а4=80)

1,2 2,0 2,0 1,5 2,5

Математическая модель:обозначим xij – количество товара, перевозимого из Аiв Bj. Тогда

/> x11 x12x13 x14x15x16

x21 x22x23 x24x25x26

X = x31 x32x33 x34x35x36 - матрица перевозок.

x41 x42x43 x44x45x46

min(x11+2x12+3x13+2,5x14+3,5x15+0,4x21+3x22+x23+2x24+3x25+0,7x31+x32+x33+0,8x34+1,5x35++1,2x41+2x42+2x43+1,5x44+2,5x45) (1)

/>x11+x12+x13+x14+x15+x16=50

x21+x22+x23+x24+x25+x26=20

x31+x32+x33+x34+x35+x36=75

x41+x42+x43+x44+x45+x46=80

x11+x21+x31+x41=40 (2)

x12+x22+x32+x42=50

x13+x23+x33+x43=15

x14+x24+x34+x44=75

x15+x25+x35+x45=40

x16+x26+x36+x46=5

xij≥0 (i=1,2,3,4; j=1,2,3,4,5,6 ) (3)

Двойственная ЗЛП:

max(50u1+20u2+75u3+80u4+40v1+50v2+15v3+75v4+40v5+5v6) (1*)

/>u1+v1≤1

u1+v2≤2

u1+v3≤3 (2*)

u1+v4≤2,5

u1+v5≤3,5

u1+v6≤0

ui,vj – произвольные (i=1,2,3,4; j=1,2,3,4,5,6) (3*)

Будем искать первоначальный план по методу наименьшейстоимости:

1) x21=20и 2-ую строку исключаем.2) x31=20и 1-ый столбец исключаем.

3) x34=55и 3-ю строку исключаем.4) x44=20и 4-ый столбец исключаем.

5) x12=50 и1-ю строку и 2-ой столбец исключаем и x32=0. 6) x43=150 и3-ий столбец исключаем.7) x45=40 и5-ый столбец исключаем.x46=5.Составимтаблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.

/> Магазины

Склад

(b1=40)

(b2=50)

(b3=15)

(b4=75)

(b5=40)

(b6=5)

А1 (а1=50)

/>1,0

2,0

/>3,0

/>2,5

/>3,5

А2(а2=20)

/>0,4

3,0 1,0 2,0 3,0

А3(а3=75)

/>0,7

1,0 1,0

0,8 1,5

А4(а4=80)

1,2 2,0

2,0

1,5

2,5

Стоимость 1-ого плана:

D1=2•50+0,4•20+0,7•20+0,8•55+2•15+1,5•20+2,5•40=326.

Будем улучшать этот план методом потенциалов: ui — потенциал Аi ,vj — потенциал Bj. Тогда u1+v2=2,u2+v1=0,4, u3+v1=0,7, u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5 ,u4+v6=0.Положимu1=0, тогда v2=2,u3=-1,v1=1,7,v4=1,8, u2=-1,3,u4=-0,3, v3=2,3,v5=2,8,v6=0,3.Составим таблицу:

Магазины

Склад

(b1=40)

v1=1,7

(b2=50)

v2=2

(b3=15)

v3=2,3

(b4=75)

v4=1,8

(b5=40)

v5=2,8

(b6=5)

v6=0,3

А1 (а1=50)

U1=0

1,0 2,0 3,0 2,5 3,5

А2(а2=20)

U2=-1,3

0,4 3,0 1,0 2,0 3,0

А3(а3=75)

U3=-1

0,7

1,0

0,8

- 0,7

1,5

А4(а4=80)

U4=-0,3

- 0,3

1,2

2,0

1,5

2,5

В верхнем левомуглу здесь и далее записываем значение ui+vj-cij. Имеем: u1+v1--c11 =0,7>0,u1+v6-c16 =0,3>0,u3+v3-c33 =0,3>0,u3+v5-c35 =0,3>0,

u4+v1-c41 =0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7.=> Поместим перевозку в клетку А1В1,сместив20=min(20,50) по циклу, указанному в таблице штрихом.Получим новую таблицу. Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8, u4+v3=2, u4+v4=1,5, u4+v5=2,5, u4+v6=0. Положимu1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=2,3,v5=2,8,v6=0,3. Составим таблицу:

/> Магазины

Склад

(b1=40)

v1=1

(b2=50)

v2=2

(b3=15)

v3=2,3

(b4=75)

v4=1,8

(b5=40)

v5=2,8

(b6=5)

v6=0,3

А1 (а1=50)

U1=0

/>/>/>

1,0

/>/>

- 0,7

2,0

- 0,7

3,0

- 0,7

2,5

3,5

А2(а2=20)

U2=-0,6

- 1,6

0,4

3,0

/>/>

- 0,8

1,0

- 0,8

2,0

- 0,3

3,0

-0,7

А3(а3=75)

U3=-1

0,7

/>/>

1,0

/>/>

0,8

- 0,7

1,5

-0,5

А4(а4=80)

U4=-0,3

- 0,3

1,2

2,0

/>/>

2,0

1,5

2,5

Стоимость 2-ого плана:

D2=1•20+2•30+0,4•20+1•20+0,8•55+2•15+1,5•20+2,5•40=312.

Имеем:u1+v6-c16=0,3>0, u2+v3-c23 =0,7>0, u3+v3-c33=0,3>0, u3+v5-c35 =0,3>0. => Покритерию оптимальности, второй план не оптимален. Далее max(0,3;0,7;0,3;0,3)=0,7=> Поместим перевозку в клетку А2В3,сместив15=min(20,30,55,15)по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдемпотенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u3+v4=0,8,u2+v3=1, u4+v4=1,5,u4+v5=2,5, u4+v6=0. Положим u1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,8, u3=-1, u4=-0,3,v3=1,6, v5=2,8, v6=0,3. Составимтаблицу:

/> Магазины

Склад

(b1=40)

v1=1

(b2=50)

v2=2

(b3=15)

v3=1,6

(b4=75)

v4=1,8

(b5=40)

v5=2,8

(b6=5)

v6=0,3

А1 (а1=50)

U1=0

1,0

-1,4

2,0

- 0,7

3,0

- 0,7

2,5

3,5

А2(а2=20)

U2=-0,6

- 1,6

0,4

3,0

- 0,8

1,0

- 0,8

2,0

- 0,3

3,0

-0,7

А3(а3=75)

U3=-1

0,7

-0,4

1,0

/>/>/>

0,8

/>/>

- 0,7

1,5

-0,5

А4(а4=80)

U4=-0,3

- 0,3

1,2

-0,7

2,0

/>/>

1,5

2,5

Стоимость 3-его плана:

D3=1•35+2•15+0,4•5+1•15+0,8•40+1•35+1,5•35+2,5•40=301,5.

Имеем:u1+v6-c16=0,3>0,u3+v5-c35 =0,3>0. => Покритерию оптимальности, третий план не оптимален. Далее max(0,3;0,3)=0,3.=> Поместим перевозку в клетку А3В5,сместив40=min(40,40)по циклу, указанному в таблице штрихом. Получим новую таблицу. Чтобы 4-ый планбыл невырожденным, оставим в клетке А4В5 нулевую перевозку.Найдем потенциалы: u1+v1=1,u1+v2=2,u2+v1=0,4,u3+v2=1, u4+v5=2,5,u2+v3=1, u4+v4=1,5,u3+v5=1,5, u4+v6=0. Положим u1=0, тогда v1=1,u2=-0,6,v2=2,v4=1,5, u3=-1,u4=0, v3=1,6, v5=2,5, v6=0. Составимтаблицу:

/> Магазины

Склад

(b1=40)

v1=1

(b2=50)

v2=2

(b3=15)

v3=1,6

(b4=75)

v4=1,5

(b5=40)

v5=2,5

(b6=5)

v6=0

А1 (а1=50)

U1=0

1,0

- 1,4

2,0

- 1

3,0

- 1

2,5

3,5

А2(а2=20)

U2=-0,6

- 1,6

0,4

3,0

- 1,1

1,0

- 1,1

2,0

- 0,6

3,0

-0,7

А3(а3=75)

U3=-1

0,7

-0,4

1,0

-0,3

1,0

0,8

- 1

1,5

-0,2

А4(а4=80)

U4=0

1,2

-0,4

2,0

1,5

2,5

Стоимость 4-ого плана: D4=1•35+2•15+0,4•5+1•15+1•35+1,5•40+1,5•75=289,5.

Для всех клеток последней таблицы выполнены условияоптимальности:

1)ui+vj-сij=0 для клеток, занятых перевозками;

2)ui+vj-сij≤0 для свободных клеток.

Несодержательные ответы:

Прямой ЗЛП:

/> 35 15 0 0 0 0

5 0 15 0 0 0

X = 0 35 0 0 40 0

0 0 0 75 0 5

min=289,5.

Двойственной ЗЛП:

U1=0;U2=-0,6; U3=-1; U4=0; V1=1; V2=2; V3=1,6; V4=1,5; V5=2,5; V6=0.

max=289,5.

Так как min=max, то по критерию оптимальности найдены оптимальныерешения прямой и двойственной ЗЛП. Содержательный ответ: Оптимально перевозитьтак:

Из А1 вB1 – 35 рулонов полотна;

Из А1 вB2 – 15 рулонов полотна;

Из А2 вB1 – 5 рулонов полотна;

Из А2 вB3 – 15 рулонов полотна;

Из А3 вB2 – 35 рулонов полотна;

Из А3 вB5 – 40 рулонов полотна;

Из А4 вB4 – 75 рулонов полотна.

При этом стоимость минимальна и составит Dmin=289,5. 5 рулонов полотна необходимо оставить на складе А4 для их последующейперевозки в другие магазины.

8.Выводы.

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

Алгоритм и методы решения транспортной задачимогут быть использованы при решении некоторых экономических задач, не имеющихничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретнойэкономической задачи. К таким задачам относятся следующие:

- оптимальное закрепление застанками операций по обработке деталей. В них cijявляется таким экономическим показателем, как производительность. Задачапозволяет определить, сколько времени и на какой операции нужно использоватькаждый из станков, чтобы обработать максимальное количество деталей. Так кактранспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;

- оптимальные назначения, илипроблема выбора. Имеется m механизмов, которые могут выполнять mразличных работ с производительностью cij. Задача позволяетопределить, какой механизм и на какую работу надо назначить, чтобы добитьсямаксимальной производительности;

- задача о сокращении производства сучетом суммарных расходов на изготовление и транспортировку продукции;

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

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

Таким образом, важность решения данной задачидля экономики несомненна. Приятно осознавать, что у истоков создания теориилинейного программирования и решения, в том числе и транспортной задачи, стоялрусский ученый – Леонид Витальевич Канторович.

Список используемой литературы:

1. Кузнецов А.В., Сакович В.А., Холод Н.И. ”Высшаяматематика. Математическое программирование ”, Минск, Вышейшая школа, 2001г.

2. Красс М.С., Чупрынов Б.П. ”Основы математики и ееприложения в экономическом образовании”, Издательство “Дело”, Москва 2001г.

3. В.И. Ермаков “Общий курс высшей математики дляэкономистов”, Москва, Инфра-М, 2000г.

еще рефераты

Еще работы по математике

Реферат по математике

Трансформация преобразований

20 Июня 2015

Реферат по математике

Три задачи по теории чисел

20 Июня 2015