Теория двойственности в линейном программировании. Двойственный симплекс-метод (стр. 2 )

Возможны три случая:

а) если , то оставшуюся часть i-й строки заполняют нулями;

б) если , то оставшуюся часть j-ro столбца заполняют нулями.

в) если, то оставшуюся часть строки и столбца заполняют нулями. Далее этот процесс повторяют с незаполненной частью матрицы. Пусть элементом с k-м порядковым номером оказался

Тогда, где

Возможны три случая;

а) и оставшуюся часть строкизаполняют нулями;

б) и остаток столбцазаполняют нулями;

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

4.2. Экономические задачи, сводящиеся к транспортной модели

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

Оптимальное распределение оборудования

Оборудование т различных видов нужно распределить между п рабочими участ­ками. Производительность единицы оборудования i-го вида на j-м рабочем участке равна Потребность j-го участка в оборудовании составляет, . Запас оборудования i-го вида равен , Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна.

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

Обозначим через хij число единиц оборудования i-го вида, выделенное на j-й рабо­чий участок,, Математическая модель задачи имеет следующий вид:

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

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

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

4.3. Нахождение первоначального базисного распределения поставок

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

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

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

Число заполненных клеток в полученном распределении оказа­лось равным т+п— 1 = 3+4-1 = 6, т. е. числу основных (ба­зисных) переменных. Это, конечно, не слу­чайно. Действитель­но, на каждом шаге (кроме последнего) данного метода из рассмотрения выпадали либо строка, либо столбец, а на послед­нем шаге и столбец, и строка. Поэтому число заполненных кле­ток (число шагов) на единицу меньше, чем сумма числа строк и столбцов таблицы поставок, т. е. равно т+п—1. Оказывается (см. теорему 7.2), что эта особенность шагов метода "северо­западного" угла служит причиной того, что полученное рас­пределение является базисным.

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

Пример 4.3. Найти методом наименьших затрат первоначальное распреде­ление поставок в задаче 4.1.

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

Так как они совпадают, то мак­симально возможную поставку даем в любую из них. На­пример, даем постав­ку, равную 20 едини­цам, в клетку (2,1). В результате спрос пер­вого потребителя удо­влетворен и первый столбец таблицы по­ставок выпадает из последующего рас­ смотрения (табл. 7.3).

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

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

= + 2 • 40 + 6 • 70 + 5 • 40 + 2 • 10 + 4 -100 = 1140; в задаче 7.3:

= 1 • 20 + + 3 • 50 + 2 • 100 + 7 • 40 + 4 • 10 = 810.

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

4,4 Метод потенциалов

 Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90 , Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться.

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

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

 Для нахождения циклов с отрицательной ценой вводится система платежей

 

и определяются величины

 

называемые "псевдостоимостями" перевозок единицы груза из пункта i

в пункт j.  При этом цена цикла пересчета для каждой свободной клетки

равна

 

если платежи

 

для всех базисных клеток (i, j)

 

4.5 Вычислительная схема метода потенциалов  [1, 3]

  Шаг 1. Строим опорный план (методом северо-западного угла) с

n+m-1  базисными клетками.

  Шаг 2. Определяем платежи

для всех базисных клеток. Один из платежей (например a1 ) полагаем равньм нулю.

  Шаг 3. Считаем псевдостоимости

 

для всех свободных клеток. Если

 

 для всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.  

  Шаг 4. Если есть свободная клетка, для которой

 

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

  Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

  Пример

Решить методом потенциалов транспортную задачу

 

  Опорный план этой задачи найден методом северо-западного угла.

	1	2	3	ai
1	15 3	20 8	2	35
2	7	0 4	30 8	30
bj	15	20	30	=

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

  βj, j = 1, n 

 и добавляем столбец для платежей

 

 Псевдостоимости записываем в левом углу клетки, а стоимости - в правом углу.

  Из условий

 

 в базисных клетках получаем систему уравнений

 

Полагая  ,  находим последовательно платежи

 

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

 

Стоимость перевозок по плану этой таблицы

 

  Так как клетка (1,3) имеет отрицательную цену

 

то план не является оптимальным. Строим для клетки (1,3) цикл. Цена

цикла

 

 По циклу переносим 20 единиц груза (больше нельзя, чтобы перевозки в клетке (1, 2) не стали отрицательными).При этом стоимость плана уменьшается на

 

 Для нового плана вычисляем новые значения платежей и псевдостоимостей:

   

 Стоимость перевозок по плану этой таблицы

 

Полученная таблица имеет клетку (2,1 ) с отрицательной ценой

 

По циклу этой клетки переносим 10 единиц груза, при этом стоимость плана уменьшается на

 

единиц, и получаем новый опорный план с новой системой платежей и псевдостоимостей:

 

 Стоимость перевозок по плану этой таблицы

 

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

 

является оптимальным. Стоимость перевозок при этом  

 

5. СИСТЕМЫ УПРАВЛЕНИЯ ЗАПАСАМИ

5.1. Модели управления запасами

Возникновение теории управления запасами можно связать с работами Ф. Эджуорта и Ф. Харриса, появившимися в конце XIX – начале XX вв., в которых исследовалась простая оптимизационная модель определении экономичного размера партии поставки для складской системы с постоянным равномерным расходом и периодическим поступлением хранимого продукта.

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

Простейшая схема системы управления запасами выглядит следующим образом (рис.6.1.):

Рис. 6.1. Система управления запасами

Существуют причины, побуждающие организации создавать запасы:

1)  дискретность поставок при непрерывном потреблении;

2)  упущенная прибыль;

3)  случайные колебания:

-  в спросе за период между поставками;

-  в объеме поставок;

-  в длительности интервала между поставками;

4)  предполагаемые изменения конъюнктуры:

-  сезонность спроса;

-  сезонность производства;

-  ожидаемое повышение цен.

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

1)  плата за физическое хранение запаса;

2)  потери в количестве запаса;

3)  моральный износ продукта.

Рассмотрим определяющие понятия теории управления запасами.

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

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

Упущенная прибыль – издержки, связанные с неудовлетворенным спросом, возникающим в результате отсутствия продукта на складе.

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

Срок выполнения заказов – срок между заказом и его выполнением.

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

5.2. Краткая характеристика моделей управления запасами

1.1. Модель оптимального размера заказа.

Предпосылки:

1)  темп спроса на товар известен и постоянен;

2)  получение заказа мгновенно;

3)  отсутствуют количественные скидки при закупке больших партий товара;

4)  единственные меняющиеся параметры – издержки заказа и хранения;

5)  исключается дефицит в случае своевременного заказа.

Исходные данные: темп спроса; издержки заказа и хранения.

Результат: оптимальный размер заказа; время между заказами и их количество за период.

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

Исходные данные: темп спроса; издержки заказа и хранения; время выполнения заказа.

Результат: оптимальный размер заказа; время между заказами; точка восстановления запаса.

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

Исходные данные: темп спроса; издержки заказа и хранения; упущенная прибыль.

Результат: оптимальный размер заказа; время между заказами; точка восстановления запаса.

1.4. Модель с учетом производства (в сочетании с условиями 1.1 – 1.3). Необходимо рассматривать уровень ежедневного производства и уровень ежедневного спроса.

Исходные данные: темп спроса; издержки заказа и хранения; упущенная прибыль; темп производства.

Результат: оптимальный уровень запасов (точка восстановления)

Модель 1.1 Наиболее экономичного размера заказа. Заказ, пополняющий запасы, поступает как одна партия. Уровень запасов убывает с постоянной интенсивностью пока не достигнет нуля. В этой точке поступает заказ, размер которого равен Q, и уровень запасов восстанавливается до максимального значения. При этом оптимальным решением задачи будет тот размер заказа, при котором минимизируются общие издержки за период (рис. 6.2).

рис. 6.2

Пусть Q – размер заказа;

Т – протяженность периода планирования;

D – величина спроса за период планирования;

d – величина спроса в единицу времени;

K – издержки заказа;

H – удельные издержки хранения за период;

h – удельные издержки хранения в единицу времени.

Тогда:

совокупные издержки заказа = ;

совокупные издержки хранения = ; ; ;

оптимальный размер заказа ;

оптимальное число заказов за период ;

время цикла (оптимальное время между заказам) .

Модель 1.2. Введем предположение о том, что заказ может быть получен не мгновенно, а с течением времени. Тогда нам необходимо заранее делать заказ, чтобы в нужное время иметь достаточное количество товара на складе. Следовательно, нам необходимо найти тот уровень запасов, при котором делается новый заказ. Этот уровень называется точкой восстановления R. Пусть L – время выполнения заказа. Тогда R = величина спроса в единицу времени, умноженная на время выполнения заказа = . Другие характеристики системы определяются также, как и в модели1.1. Модель иллюстрируется рис. 6.3.

рис. 6.3

Пример 1. Андрей Удачливый является торговым агентом компании TOYOTA и занимается продажей последней модели этой марки автомобиля. Годовой спрос оценивается в 4000 ед. Цена каждого автомобиля равна 90 тыс. руб., а годовые издержки хранения составляют 10% от цены самого автомобиля. Андрей произвел анализ издержек заказа и понял, что средние издержки заказа составляют 25 тыс. руб. на заказ. Время выполнения заказа равно восьми дням. В течение этого времени ежедневный спрос на автомобили равен 20.

-  Чему равен оптимальный размер заказа?

-  Чему равна точка восстановления?

-  Каковы совокупные издержки?

-  Каково оптимальное количество заказов в год?

-  Каково оптимальное время между двумя заказами, ели предположить, что количество рабочих дней в году равно 200?

Исходные данные

величина спроса за год D = 4000;

издержки заказа K = 25;

издержки хранения h = ;

цена за единицу с = 90;

время выполнения заказа L = 8;

ежедневный спрос d = 20;

число рабочих дней T = 200.

Решение

оптимальный размер заказа ;

точка восстановления R = 160 – 149 = 11;

число заказов за год ;

совокупные издержки = совокупные издержки заказа + совокупные издержки хранения С = ;

стоимость продаж = 360000;

число дней между заказами t = 7,45.

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

рис. 6.4

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

P – упущенная прибыль за период, возникающая в результате дефицита одной единицы продукта.

Тогда:

оптимальный размер заказа ;

максимальный размер запаса ;

максимальный дефицит .

Модель 1.4 производства и распределения. В предыдущей модели мы допускали, что пополнение запаса происходит единовременно. Но в некоторых случаях, особенно в промышленном производстве, для комплектования партии товаров требуется значительное время и производство товаров для пополнения запасов происходит одновременно с удовлетворением спроса. Такой случай показан на рис. 6.5.

рис. 6.5

Спрос и производство являются частью цикла восстановления запасов.

Пусть u - уровень производства в единицу времени;

K – фиксированные издержки хранения.

Тогда:

совокупные издержки хранения =

;

средний уровень запасов = (максимальный уровень запасов)/2;

максимальный уровень запасов = ;

время выполнения заказа ;

издержки заказа = ;

оптимальный размер заказа ;

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

МОДЕЛИ СЕТЕВОГО ПЛАНИРОВАНИЯ И УПРАВЛЕНИЯ

6.1. Назначение и области применения сетевого планирования и управления

Сетевым планированием и управлением (СПУ) называется графоаналитический метод планирования и управления процессами создания технических систем и сложных объектов (научных исследований, проектирования, монтажа, подготовки производства, при выполнении маркетинговых исследований, ремонте и модернизации технологического оборудования, разработке бизнес-планов производства новых товаров, подготовке и расстановке различных категорий персонала и т. п.)

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

Система СПУ позволяет:

• формировать календарный план реализации некоторого ком­плекса работ;

• выявлять и мобилизовывать резервы времени, трудовые, материальные и денежные ресурсы;

• осуществлять управление комплексом работ по принципу "ведущего звена" с прогнозированием и предупреждением воз­можных срывов в ходе работ;

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

Диапазон применения СПУ весьма широк: от задач, касающихся деятельности отдельных лиц, до проектов, в которых участвуют сотни организаций и десятки тысяч людей (например, разработка и созда­ние крупного территориально-промышленного комплекса).

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

Средством описания проектов (комплексов) является сетевая модель.

6.2. Сетевая модель и ее основные элементы

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

Главными элементами сетевой модели являются события и работы.

Термин работа используется в СПУ в широком смысле.

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

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

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

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