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

Содержание

Введение…………………………………………………………………………2

Глава 1. Линейное программирование…………………….………………..3

1. История зарождения и создания линейного программирования…………3
2. Задача линейного программирования. Основные задачи…………………7

Глава 2. Транспортная задача……………………………………..……….11

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

2.2 Математическая модель транспортной задачи……………………………16

Глава 3. Решение транспортной задачи по пути развоза своей продукции компании «Coca-Colа» по г.Бишкек………………………………………..21

3.1 Описание компании «Coca-Cola»………………………………………….21

3.2 Решение транспортной задачи методом программирования.…………….23

Заключение…………………………………………………………………….37

Список использованной литературы………………………………………..39

 

Введение

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

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

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

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

 

 

 

 

 

 

Глава 1. Линейное программирование

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

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая  ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь  была бы менее интересной, если бы это  было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем  у противника. Чтобы достичь наибольшего  эффекта, имея ограниченные средства, надо составить план, или программу  действий. Раньше план в таких случаях  составлялся “на глазок” (теперь, впрочем, зачастую тоже).

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Задача линейного программирования. Основные задач

 

Напомним прежде всего постановку задачи линейного программирования. Под задачей линейного программирования или кратко задачей ЛП будем понимать следующую задачу. Даны система m линейных ограничений с n неизвестными (система может содержать как уравнения, так и (или) неравенства того или иного знака)

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n ≤ b₁,

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n ≥ b₂,

... ... ... ... ... ... ... ... ... ... ... . .

a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_m,   (1)

условие неотрицательности неизвестных

x₁ ≥ 0, x₂ ≥ 0, ... , x_n ≥ 0,               (2)

и целевая линейная функция, зависящая от n неизвестных,

f(X) = c₁x₁ + c₂x₂ + ... + c_nx_n,      (3)

где X = (x₁,x₂,... ,x_n) — вектор неизвестных.

Требуется найти такой  план системы линейных ограничений (1),

при котором целевая функция (3) примет наибольшее или наименьшее

значение, то есть найти оптимальный  план задачи (1)–(3).

Планом задачи (1)–(3) называется всякое неотрицательное решение

системы линейных ограничений (1), то есть план — это вектор X =

(x₁,x₂,... ,x_n), удовлетворяющий условиям (1) и (2).

План X∗ называется оптимальным планом задачи максимизации

(минимизации), если   f(X*) ≥ f(X)   f(X*) ≤ f(X), где X - любой план задачи.

При решении задачи ЛП возможны следующие случаи.

1. Существует оптимальный план (единственный или бесконечное

множество оптимальных планов).

2. Оптимальный план не существует, так как планы в задаче есть,

но на непустом множестве  планов целевая функция не ограничена

(сверху — в задаче  максимизации или снизу — в  задаче минимизации).

3. Оптимальный план не существует, так как в задаче вообще нет ни

одного плана.

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

а именно:

1) общая задача;

 2) основная задача;

3) каноническая задача.

Задачу ЛП будем называть общей задачей, если система линейных

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

Система линейных уравнений  называется канонической системой,

если она удовлетворяет  двум условиям:

1) в каждом уравнении содержится неизвестное с коэффициентом, равным единице, отсутствующее во всех остальных уравнениях и называемое базисным неизвестным;

2) свободные члены всех уравнений неотрицательны.

Неизвестные, не являющиеся базисными, называются свободными

неизвестными. При m = 2 , n = 4, если предполагать базисными

неизвестные x3 и x4, каноническую задачу можно записать в виде:

a₁₁x₁ + a₁₂x₂ + x₃ = b₁ ≥ 0,

a₂₁x₁ + a₂₂x₂ + x₄ = b₂ ≥ 0,                     (4)

  x_j ≥ 0 (x_j = 1 ÷ 4),                                   (5)

 f(X) = C₀ − C₁x₁ − C₂x₂ − max (min). (6)

   Если в канонической  системе положить все свободные  неизвестные

равными нулю, то базисные неизвестные  будут равны неотрицательным

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

базисным планом канонической задачи. При x₁ = x₂ = 0 из системы

(4) получим, что x₃ = b₁ ≥ 0, x₄ = b₂ ≥ 0, и базисный план задачи

(4)–(6) будет иметь вид:

X_bas = (0, 0, b₁, b₂),

причем, как видно из выражения (6), значение целевой функции для

этого плана f(X^bas) = C⁰.

Из трех форм задачи ЛП главная  роль отводится канонической, так

как алгоритм симплекс-метода непосредственно применяется к  канонической задаче, а общая и основная задачи в конечном счете сводятся к канонической. Для того, чтобы общую задачу привести к основной, то есть неравенства заменить уравнениями, достаточно ввести неотрицательные дополнительные неизвестные, прибавив их к левым частям неравенств "типа ≤ ", выч-тя из левых частей неравенств "типа ≥"и приписав к заданной целевой функции с нулевыми коэффициентами.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Глава 2. Транспортная задача

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

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

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