19815

Початковий розподіл поставок

Доклад

Информатика, кибернетика и программирование

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

Украинкский

2013-07-17

26.87 KB

5 чел.

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

^ 7.2. Найти первоначальное базисное распределение поставок для транспортной задачи 7.1.

Решение. Дадим переменной максимально возможное значение или, иными словами, максимально возможную поставку в клетку (1,1) — "северо-западный" угол таблицы поставок: = = min {60, 20} = 20. После этого спрос 1-го потребителя будет полностью удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией (см. табл. 7.2) клетки, выпавшие из последующего рассмотрения, перечеркнуты пунктирной линией. В таблице поставок найдем новый "северозападный" угол — клетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1-й поставщик уже отдал 20 единиц груза и у него осталось только 40 = 60—20 единиц груза, получаем, что xl2 = min {40, 110} = 40. После этого мощность 1-го поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы поставок (перечеркиваем сплошной линией клетку (1,2) и пунктирной линией оставшиеся свободные клетки первой строки). В оставшейся таблице снова находим "северозападный угол" и т. д. В результате получаем следующее исходное распределение поставок (см. табл.7.2).>

Таблица 7.2

20

110

40

110

60

1

20

2

40

5

У

3 X

120

У

1

6

70

5

40

2

10

100

6

У

У

У

З х’

7 >»

У

У ‘

4

100

Число заполненных клеток в полученном распределении оказалось равным т+п~ -1 = 3+4-1 = 6, т. е. числу основных (базисных) переменных. Это, конечно, не случайно. Действительно, на каждом шаге (кроме последнего) данного метода из

5 Исследование операций в экономике

Рассмотрения выпадали либо строка, либо столбец, а на последнем шаге и столбец, и строка. Поэтому число заполненных клеток (число шагов) на единицу меньше, чем сумма числа строк и столбцов таблицы поставок, т. е. равно т+п—1. Оказывается (см. теорему 7.2), что эта особенность шагов метода "северозападного" угла служит причиной того, что полученное распределение является базисным.

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

Таблица 7.3

20

110

40

110

60

1

2

5

3

120

1

20

6

5

2

100

6 X ^ /

3

7

4

Таблица 7.4

20

110

40

110

60

1 у

2

5

3

120

6

5

У

У

У

2

100

100

6

3

7

4

Решение. Находим в таблице поставок (см. табл. 7.1) клетки с наименьшим коэффициентом затрат. Таких клеток две — (1,1) и (2,1) с коэффициентами затрат, равными 1. Сравним максимально возможные поставки для этих клеток: для клетки (1,1) хц = = min {60, 20} = 20, для клетки (2,1) х21 = min {120, 20} = = 20. Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам, в клетку (2,1). В результате спрос первого потребителя удовлетворен и первый столбец таблицы поставок выпадает из последующего рассмотрения (табл. 7.3).

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с\2 = с24= 2. Сравним максимально возможные поставки для этих клеток: для клетки (1,2) х\2 = min {60, 110} = 60; для клетки (2,4) х24 = nun {120-20, 110} = 100. Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: х24 = 100. При этом из рассмотрения выпадает вторая строка таблицы поставок (табл. 7.4).

Аналогично, продолжая заполнение таблицы поставок шаг за шагом, получаем ~хп — min{60, 110} = 60,= min{100, 110-60} = 50, х34 = min {100-50, 110-100} = 10, х33 = min {100-60, 40} = 40 (табл. 7.5)>

Сравним найденное распределение поставок с распределением, полученным для той же задачи по методу "северо-западного" угла (см. задачу 7.2, табл. 7.2). Вычислим для каждого из этих распределений суммарные затраты в денежных единицах:

В задаче 7.2:

F0 = 1 • 20 + 2 • 40 + 6 • 70 + 5 ¦ 40 + 2 • 10 + 4 ¦ 100 = 1140 ;

В задаче 7.3:

Таблица 7.5

20

110

40

110

60

1

2

60

5

У

3

120

1

20

6

У

?

5

X

У

2

// 100

100

6

?

/

3

50

7

40

4 ^^ 10

F0 = 1 ¦ 20 + 2 • 60 + 3 • 50 + 2 -100 + 7 ¦ 40 + 4 ¦ 10 = 810.

Как и ожидалось, при использовании метода "северо-западного" угла суммарные затраты больше, чем при применении метода наименьших затрат. Таким образом, во втором случае мы находимся ближе (по числу необходимых шагов) к оптимуму, чем в первом. Докажем, что распределения, получаемые с помощью указанных методов, являются базисными, и рассмотрим те особые случаи, которые могут встретиться при использовании этих методов.[19]

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

? Из линейной алгебры известно, что если ранг системы линейных уравнений равен г и некоторые г переменных системы выражены через остальные переменные, то эти г переменных можно взять за основные (базисные). Из условия данной теоремы следует, что число заполненных клеток равно т+п—1, т. е. равно рангу системы (7.4), (7.5) (см. пояснения к методу "северо-западного" угла). Поэтому теорема будет доказана, если показать, что переменные, соответствующие заполненным клеткам, могут быть выражены через переменные, соответствующие свободным клеткам.

Предположим, что переменные заполненных клеток, возникшие на первых t шагах метода, где Г = 1, 2, …, т+п—2, можно выразить через переменные, соответствующие свободным клеткам тех строк и столбцов, которые были вычеркнуты (выпали из рассмотрения) на первых? шагах. Пусть на (Г +1)-м шаге метода заполнена (р, д)-я клетка и из рассмотрения выпала, например, р-я строка. Выразим переменную х™ из уравнения баланса по р-й строке:

Л

М

}*Ч

Пусть среди переменных правой части последнего равенства есть переменные клеток, заполненных на одном из первых t шагов. Тогда по предположению их можно выразить через переменные свободных клеток тех строк и столбцов, которые были вычеркнуты на первых Г шагах. В случае, если на (Н-1)-м шаге из рассмотрения выпал q-й столбец, хрч следует выразить из уравнения баланса по столбцу. Подобные рассуждения следует последовательно провести для каждого из шагов заполнения таблицы поставок. ¦

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

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

7.4. Найти первоначальное базисное распределение поставок для следующей транспортной задачи (табл. 7.6).

Решение. Воспользуемся методом "северо-за — падного" угла. На первом шаге следует дать поставку, равную 20 единицам, в клетку (1,1). В результате будет удовлетворен спрос 1- го потребителя и из рассмотрения выпадет первый столбец. На втором шаге поставку в 10 единиц следует дать в клетку (1,2). При этом из последующего рассмотрения выпадет и 1-й поставщик (который реализовал остатки своего груза), и 2-й потребитель, полностью удовлетворивший свой спрос. Продолжая использовать метод "северо-западного" угла, мы получим, конечно, заполнение таблицы поставок, но число заполненных клеток окажется меньше, чем число основных (базисных) переменных, равное т+п—1=3+3— —1=5. Такое распределение не будет базисным, и для продолжения решения распределительный метод будет неприемлем. Избежать этого можно, используя следующий искусственный прием.

Разобьем второй шаг на два шага. Допустим, что после поставки в клетку (1,2) из рассмотрения выпадает, например, только первая строка. Для того чтобы вывести из рассмотрения второй столбец, делаем еще один шаг: даем нулевую (фиктивную) поставку в произвольную, но не вычеркнутую клетку второго столбца, например, в клетку (2,2). После таких трех шагов имеем табл. 7.7.

20

10

40

30

1

3

5

30

3

3

2

10

4

1

2

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

При последующем заполнении таблицы поставок используем метод "северо-западного" угла обычным способом. В результате получаем распределение поставок (табл. 7.8).^

Таблица 7.7 Таблица 7.8

20

10

40

30

1 У""

// 20

3

10

3 X

У

30

3

У

У

У

3

0

2 у"" 30

10

4

У

1 X

У

2 у^ 10

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

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


 

А также другие работы, которые могут Вас заинтересовать

81665. Особенности развития русской литературной критики 1830-х гг. Романтическая критика на страницах ж-ла Н.А.Полевого «Московский телеграф» 35.24 KB
  Полевого создавал атмосферу новизны непрестанного поиска. Полевого; с романтических повестей Вечера на хуторе близ Диканьки начинает писательское поприще И. Полевого ярко раскрылись и в его рецензии на книгу АГалича Опыт науки изящного 1826. Полевого О романах Виктора Гюго и вообще о новейших романах 1832 обнаруживала ориентацию автора на романтизм в его французской разновидности.
81666. Философская критика (Д.В.Веневитинов, И.В.Киреевский и др.). Литературно-критическая и журналистская деятельность Надеждина 37.23 KB
  Манна философская предоснова восприятия искусства строго говоря присущая любой художественной теории в том числе классицизму романтизму и т. здесь уже ощущается недостаточной и уступает место целенаправленному включению искусства в философское наукоучение. Высокую оценку Галича получали идеи натурфилософии Шеллинга понимание природы как целесообразного целого где происходит взаимодействие противоположно направленных сил и основные положения шеллинговой философии искусства: представление о самоценности искусства об идеале как...
81667. А.С. Пушкин как литературный критик. Проблематика его литературно-критических статей и заметок; жанровое, стилевое своеобразие. Типологический анализ одной из работ 35.6 KB
  Его статьи и художественные произведения становились итогом долгих и основательных раздумий о самых разнообразных теоретических проблемах художественного творчества о предмете и назначении искусства о взаимосвязи писателя и общества об историзме и народности литературы роли критики в развитии эстетического вкуса читателей путях становления русского литературного языка и т. В многообразном по своему составу литературнокритическом наследии Пушкина есть и опыты больших историколитературных обобщений незавершенная статья О ничтожестве...
81668. Творчество А. С. Пушкина в критике разных эпох. Сравнительный типологический анализ статей В. Г. Белинского (8-я, 9-я, из цикла «Сочинения Александра Пушкина»), Д. И. Писарева («Пушкин и Белинский»), Д. С. Мережковского («Пушкин») 39.06 KB
  Пушкина в критике разных эпох. Белинского 8я 9я из цикла Сочинения Александра Пушкина Д. Вообще творчеству Пушкина Белинский посвящает огромное количество критических статей и сочинений. Обратимся к 89 статьям сочинения Александра Пушкина.
81669. Литературно-критическое тв-во Н.В.Гоголя. Типологический анализ одной из статей 40.33 KB
  Статья Плетнева Чичиков или Мертвые души Гоголя опубликованная в июльском номере Современника за 1842 г. Плетнев как и Белинский ставил Гоголя в первый ряд среди современных писателей отмечая удивительную верность автора действительности. В произведениях Гоголя П. Вяземский решительно противился тому что именем Гоголя теоретики натуральной школы пытались придать ей идейную и эстетическую целостность.
81670. Особенности развития литературной критики в 1840-е гг. Литер.критика «Отечественных записок». Славянофильская критика. Литературно-критическая позиция журнала «Современник» 34.72 KB
  Анненков определялись противостоянием двух сформировавшихся на рубеже 1830 1840х годов течений русской общественной мысли западничества и славянофильства. отстаивали необходимость исторического движения России по европейскому пути выдвигали на первый план идею свободы и самоценности человеческой личности подчеркивали исчерпанность тех начал которые составляли основу древнерусской жизни. публиковали свои статьи на страницах Москвитянина Московских литературных и ученых сборниковРусской беседы выступили против перенесения...
81671. Понятие о литературной критике, ее происхождение. Значение термина «критика» 28.26 KB
  Значение термина критика. В широком общекультурном смысле литературная критика обозначение восходящей к глубокой древности филологической рефлексии по поводу любого словесно-организованного текста. В современной западной культуре понятия литературная наука и литературная критика часто совпадают и употребляются на правах синонимов. В специальном литературоведческом смысле закрепленном отечественной гуманитарной традицией литературная критика род литературно-творческой и литературно-коммуникативной деятельности направленной на...
81672. Природа и предмет литературной критики. Взаимодействие критики с различными отраслями искусства и науки. Соотношение критики и литературоведения. Основные функции критики 31.97 KB
  Литературная критика двойственна по своей природе. Литературная критика естественно соотносится со многими областями науки и культуры: с филологией философией историей эстетикой герменевтикой культурологией психологией социологией книговедением с публицистикой и журналистикой с критикой художественное музыкальной театральной с кинокритикой телевизионной критикой и др. Испытывая непосредственное влияние близких или смежных гуманитарных сфер литературная критика в слою очередь способствует их развитию. Литературная критика одна...
81673. Типология литературной критики с точки зрения субъекта критической деятельности 38.99 KB
  Для критики словесного искусства нужны люди которые бы показывали бессмыслицу отыскивания мыслей в художественном произволении м постоянно руководили бы читателем в том бесконечном лабиринте сцеплений в котором и состоит сущность искусства и к тем законам которые служат основанием этих сцеплений. Сопряжение собственного эстетического опыта и литературной неизведанности явленной в оцениваемых словеснохудожественных произведениях одна из постоянно одолеваемых сложностей профессиональной литературной критики. Лидеров профессиональной...