Получение первоначального плана поставок с помощью метода «северо-западного» угла

ГОУ ВПО  Московский государственный университет  экономики, статистики и информатики (МЭСИ)

Тверской  филиал 

(Заочное  отделение) 
 
 
 
 
 

Контрольная работа по дисциплине

«Математические методы исследования операций в экономике» 
 

На тему: Получение первоначального плана поставок с помощью метода «северо-западного» угла 
 
 
 
 
 

Выполнила-

Лапинская Анастасия Генриховна

Студентка группы З9-САУ-21

№ зачетной книжки 66821 

Проверила-

д.и.н., профессор

Славко  Татьяна Ивановна 
 
 
 
 
 
 
 
 

Тверь 2010 

Содержание: 
 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

    Транспортная  задача по своей математической постановке является задачей линейного программирования и может решаться общими для задач линейного программирования методами. Исторически сложилось так, что в пору бурного развития математических методов экономического анализа (1940-50-е гг.) мощности используемых ЭВМ были недостаточны для решения большинства реальных экономических задач. В это время наибольшие успехи были достигнуты в решении задач по перевозке грузов в связи с тем, что методы решения этих задач учитывали особенности их математической модели.

    В настоящее время термином «транспортная  задача» охватывается некоторый  класс задач линейного программирования, имеющих одинаковую математическую структуру. Некоторые особенности методов решения транспортной задачи позволяют использовать значения получаемых параметров для управления соответствующими экономическими объектами, построения системы взаимоотношений между поставщиками и потребителями и для других целей. Поэтому методы анализа и решения транспортной задачи сохраняют свою актуальность. Целью контрольной работы является изучение одного из методов решения транспортной задачи – метода «северо-западного» угла. Для этого поставлены следующие задачи:

    1.Ознакомиться  с понятием транспортная задача.

    2.Рассмотреть  метод решения «северо-западного»  угла. 
 
 
 
 
 
 

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

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

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

    Формулировка транспортной задачи: Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.

        Исходные данные транспортной  задачи обычно записываются в таблице (таб.1). 

Таблица1

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

    Математическая  модель транспортной задачи: Переменными (неизвестными)  транспортной задачи являются i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю.

       Так как произведение  определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны .

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

     ,   i=1,2,…,m.

       Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:

     ,   j=1, 2, … , n.

        Математическая формулировка транспортной  задачи такова: найти переменные  задачи  , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений,  условиям неотрицательности  и обеспечивающие минимум целевой функции.  
 

2. Метод  решения «северо-западного» угла

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

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

    1. если , то и исключается поставщик с номером i, , k=1, 2, …, n, k j, ;

    2. если , то и исключается потребитель с номером j, , k=1, 2, …, m, k i, ;

    3. если , то и исключается либо i-й поставщик, , k=1, 2, …, n, k j, , либо j-й потребитель, , k=1, 2, …, m, k i,

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

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

    Теорема. Решение транспортной задачи, построенное методом северо-западного угла, является опорным⁴.

    Доказательство. Число занятых опорным решением клеток таблицы должно быть равно N=m+n-1. на каждом шаге построения решения по методу северо-западного угла заполняется одна клетка и исключается из рассмотрения одна строка (поставщик) или один столбец (потребитель) таблицы задачи. Через m+n-2 шага в таблице будет занято m+n-2 клетки. В то же время останутся не вычеркнутыми одна строка и один столбец, при этом незанятая клетка одна. При заполнении этой последней клетки число занятых клеток составит m+n-2+1=m+n-1. 
 
 
 
 
 
 
 
 

3. Решение  задачи методом «северо-западного» угла

    Исходные  данные имеют следующий вид:

    На 3-х базах А₁, А₂, А₃ находиться однородный груз в количествах равных соответственно 140, 180, 160 единиц.  Груз требуется перевезти в 5 пунктов назначения В₁, В₂, В₃, В₄, В₅ соответственно в количествах 60, 70, 120, 130, 100 единиц. Стоимость единицы груза укажем в таблице: 

 

    Z = 60*2 + 70*3+ 10*4 + 110 + 70*4 + 60*7 + 100*2 = 1380 
 
 
 
 
 
 
 
 
 
 
 
 
 

Заключение

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

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

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

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

1. Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б. Математическое программирование.4-е изд. –М.: Высш. шк., 2005. – 467 с.
2. Математические методы и модели исследования операций: учебник / Под ред. В.А Колемаева. – М.:ЮНИТИ-ДАНА, 2009. – 592 с.
3. Общий курс высшей математики для экономистов: Учебник / Под ред. В. И. Ермакова.-М.: ИНФРА-М, 2008. – 384 с.