<<

стр. 11
(всего 31)

СОДЕРЖАНИЕ

>>

360°. По прогнозам специалистов, спрос на продукцию в течение следующих четырех лет
будет следующим.

Потребность (в тыс. единиц) по годам
1 2 3 4

309
Пластик, 90° 32 44 55 56
Пластик, 180° 15 16 17 18
Пластик, 360° 50 55 64 67
Бронза, 90° 7 8 9 10
Бронза, 180° 3 4 5 6
Бронза, 360° 11 12 15 18

На обеих производственных линиях можно выпускать любые из перечисленных
выше типов насадок. На каждом станке для производства бронзовых деталей должно
работать два оператора. Один станок способен выпускать 12 тысяч единиц продукции.
Машину для литья пластиковых разбрызгивателей должны обслуживать четыре
оператора, и ее мощность — 200 тысяч единиц продукции. Завод располагает тремя
станками для выпуска бронзовых устройств и одной машиной для отливки пластиковых
изделий. Каковы потребности предприятия в производственных мощностях на следующие
четыре года?
2. Предположим, что маркетинговый отдел компании AlwaysRain Irrigation, Inc.
намерен провести интенсивную рекламную кампанию, направленную на стимулирование
сбыта бронзовых разбрызгивателей, которые стоят несколько дороже пластиковых, но при
этом отличаются значительно большей прочностью. Прогнозируемый спрос на
следующие четыре года таков.

Потребность (в тыс. единиц) по годам
1 2 3 4
Пластик, 90° 32 44 55 56
Пластик, 180° 15 16 17 18
Пластик, 360° 50 55 64 67
Бронза, 90° 11 15 64 23
Бронза, 180° 6 5 18 9
Бронза, 360° 15 16 17 20

Повлечет ли эта рекламная кампания изменение производственных мощностей
завода?
3. В преддверии широкомасштабной рекламной кампании компания AlwaysRain
Irrigation, Inc. приобрела еще один станок для выпуска бронзовых изделий. Обеспечит ли
эта мера необходимое увеличение производственной мощности?
4. Предположим, что операторы прошли специальную подготовку и могут работать
на любом из двух имеющихся видов оборудования. В настоящее время в штате компании
работает 10 таких рабочих. В преддверии рекламной кампании, описанной в задаче 2,
управленческий персонал решил приобрести еще два станка для производства бронзовых
устройств. Как это повлияет на потребности компании в рабочей силе?
5. Компания Expando, Inc. рассматривает возможность строительства еще одной
фабрики, которая будет выпускать новое изделие, дополняющее ассортимент фирмы. В
настоящее время компания оценивает две возможности. Первая заключается в открытии
небольшого предприятия, строительство которого обойдется фирме в 6 миллионов
долларов. Если спрос на новую продукцию будет невелик, компания ожидает получить
совместно с новой небольшой фабрикой 10 миллионов долларов чистого
дисконтированного дохода. С другой стороны, при значительном спросе фирма
рассчитывает получить 12 миллионов долларов чистого дисконтированного дохода.
Вторая возможность заключается в строительстве большой новой фабрики, на которую

310
придется затратить 9 миллионов долларов. Если спрос на новую продукцию будет
незначительным, по оценке специалистов, компания сможет получить совместно с
доходом этой новой фабрики 10 миллионов долларов чистого дисконтированного дохода.
При большом спросе сумма ожидаемых дисконтированных доходов составит 14
миллионов долларов. В любом случае вероятность того, что спрос будет велик,
оценивается в 40%, а вероятность небольшого спроса — 60%. Если компания откажется
от строительства новой фабрики, она не сможет рассчитывать на получение
дополнительного дохода, поскольку имеющиеся предприятия выпускать эту продукцию
не смогут. Постройте дерево решений и помогите компании Expando принять
оптимальное решение.


Основная библиография

Nils Arne Bakke and Ronald Hellberg, "The Challenges of Capacity Planning",
International Journal of Production Economics, 31-30 (1993), p. 243-264.
R.D. Jack Hammesfahr, James A. Pope and Aliraza Arda-lan. "Strategic Planning for
Production Capacity", International Journal of Operations and Production Management, May
1993, p. 41—53.
John Haywood-Farmer and Jean Nollet, Service Plus: Effective Services Management
(Boucherville, Quebec, Canada: G. Morin Publisher Ltd., 1991).
Robert Johnston, Stuart Chambers, Christine Harland, Alan Harrison and Nigel Slack,
Cases in Operations Management (England: Pitman, 1993).
Hugh F. Martin, "Mass Customization at Personal Lines Insurance Center", Planning
Review, July—August 1993, p. 27, 56.
Christopher Meyer, First Cycle Time: How to Align Purpose, Strategy and Structure for
Speed (New York: Free Press, 1993).
Craig Giffi, Aleda V. Roth and Gregory M. Seals (eds.), Competing in World-Class
Manufacturing: National Center for Manufacturing Sciences (Homewood, IL.: Business One
Irwin, 1990).
B. Pine II. Mass Customization: The New Frontier in Business Competition (Boston:
Harvard Business School Press, 1993).




311
ДОПОЛНЕНИЕ К ГЛАВЕ 7 Линейное программирование
В этой главе...

Модель линейного программирования
Графическое линейное программирование
Симплексный метод
Транспортный метод
Резюме

Ключевые термины
Анализ устойчивости (Sensitivity Analysis)
Вырождение (Degeneracy)
Графическое линейное программирование (Graphical Linear Programming)
Линейное программирование (Linear Programming)
Метод рычага (Pivot Method)
Поиск решения (Solver)
Симплексный метод (Simplex Method)
Теневая цена (Shadow Price)
Транспортный метод (Transportation Method)
Уравнения ограничений (Constraint Equations)
Целевая функция (Objective Function)

Ресурсы WWW
Airlines Online (http://axrlines.com)




312
Типичное применение методов линейного программирования в операционном
менеджменте1
1
Методы в данной врезке объединены в две основные группы так, как они описаны в этом дополнении к
главе 7. (Графический метод в данный перечень не включен, поскольку он ограничен задачами с двумя
переменными.)

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

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

Примеры
Сбор и распределение крови Американским Красным Крестом
Донорская служба Американского Красного Креста (American Red Cross — ARC) работает в
нескольких регионах. Каждое отделение отвечает за сбор, тестирование и распределение
донорской крови в своей зоне. Так, например, среднеатлантическое подразделение Американского
Красного Креста работает в большей части штата Вирджиния и на северо-востоке Северной
Каролины. Как-то специалисты предложили проект изменения расположения донорских пунктов в
среднеатлантическом регионе, и службу ARC заинтересовала экономическая целесообразность и
эффект данного мероприятия. Для того чтобы быстро определить, как будущие перемены
повлияют на существующий график сбора и распределения крови, использовали модели
линейного программирования. В результате проведенного анализа ARC приняла решение
повременить с переразмещением своих пунктов и вместо этого сделать все возможное для
оптимизации имеющихся мощностей.
Источник. Derya A. Jacobs, Murat N. Silan and Barry A. Clemson, "An Analysis of Alternative

313
Locations and Service Areas of American Red Cross Blood Facilities", Interfaces, May-June 1996, p. 40-
50.

Оценка степени согласованности
Трое ученых использовали метод линейного программирования для оценки слаженности
игры игроков бейсбольной лиги. Модель основывалась на вычислении весовых коэффициентов и
применялась для получения объективных показателей слаженности на основе субъективных
оценок согласованности действий игроков. Сравнение результатов анализа с
классификационными требованиями позволило подбирать игроков в команду. Такое применение
линейного программирования в равной степени подходит и для оценки согласованности работы
служащих менеджерами различных предприятий.
Источник. Christopher Zappe, William Webster and Ira Horowitz, "Using Linear Programming to
Determine Post-Facto Consistency in Performance Evaluations of Major League Baseball Players",
Interfaces, November-December 1993, p. 107-113.

Оценка лесных ресурсов
Когда правительство Новой Зеландии приступило к приватизации государственных лесных
угодий, для определения правильной продажной цены потребовалось оценить ожидаемые потоки
денежных средств от их эксплуатации. С помощью линейного программирования была
разработана модель лесных угодий, позволившая определить восстанавливаемые участки
лесозаготовок и распределение стволов в 14 зонах с горизонтом планирования на 40 и 70 лет.
Рассчитанные показатели ожидаемых денежных потоков от этих операций учитывались при
назначении стартовых цен и налогообложении участков леса. Кроме того, потенциальные
покупатели смогли воспользоваться результатами моделирования для разработки своей стратегии
торгов.
Источник. Bruce R. Manley and John A. Threadgill, "LP Used for valuation and Planning of New
Zealand Plantation Forests", Interfaces, November-December 1991, p. 66-79.

А теперь приготовьтесь! В этом дополнении к главе 7 мы обсудим основы одного из
самых мощных инструментов, применяемых в сфере управления бизнесом, — линейного
программирования.
Понятие линейного программирования (Linear Programming — LP) включает
несколько взаимосвязанных математических методов, которые используются для
оптимального распределения ограниченных ресурсов предприятия между его
конкурирующими потребностями. Наиболее широко линейное программирование
используется в методах, объединенных единым названием "математические методы
оптимизации", и, как вы убедились, прочтя врезку "Типичное применение методов
линейного программирования в операционном менеджменте", оказывается незаменимым
при решении очень многих задач и в этой области. В данном дополнении мы
сосредоточимся на обсуждении симплексного метода, с помощью которого решаются
любые задачи линейного программирования, а также на описании графического и
транспортного методов, которые очень эффективны при решении конкретных
специфических задач. Мы не только продемонстрируем, каким образом методы линейного
программирования приводят аналитика к оптимальному решению поставленной задачи,
но и обсудим понятие "теневых оценок" и другую "бесплатную информацию", которую
получает специалист, применяя симплексный метод.
Для решения задачи методом линейного программирования необходимо, чтобы
описанная в ней ситуация отвечала пяти основным условиям. Во-первых, она должна быть
связана с ограниченными ресурсами (т.е. ограниченное количество рабочих,
оборудования, финансов и материалов и т.п.), в противном случае этой задачи просто бы
не существовало. Во-вторых, необходимо сформулировать точную цель (максимизация
прибыли или минимизация затрат). В-третьих, задача должна характеризоваться
линейностью (например, если на изготовление детали требуется три часа, то на
изготовление двух будет затрачено шесть часов, на выпуск трех — девять и т.д.). В-
четвертых, задача должна характеризоваться однородностью (изделия, изготовленные на
314
станке, идентичны; все часы, в течение которых рабочий выполняет ту или иную
операцию, используются им с одинаковой продуктивностью и т.д.). Пятое условие
заключается в делимости: метод линейного программирования строится на допущении,
что результаты и ресурсы можно разделять на доли. Если такое деление невозможно
(например, полет половины самолета или наем на работу одной четвертой служащего),
аналитику лучше воспользоваться специальной модификацией линейного
программирования — дискретным (или целочисленным) программированием.
Методы линейного программирования могут применяться, если поставлена только
одна цель: максимизировать (например, прибыль) или минимизировать (например,
издержки). Когда целей несколько, используется целевое программирование. Если же
задача эффективнее всего решается поэтапно или по временным интервалам, аналитику
следует воспользоваться методом динамического программирования. В еще более
сложных задачах при решении могут потребоваться другие варианты данного метода,
например нелинейное, или квадратическое программирование.


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

Формально выражаясь, задача линейного программирования связана с оптимизацией
процесса, в ходе которого отбираются неотрицательные искомые переменные X1, Х2, ...,
Х3, используемые затем для максимизации (или минимизации) целевой функции в
следующей форме.
Максимизировать (минимизировать) целевую функцию
Z=C1X1 + C2X2 + ...+ CnXn,
при условии ограничений на количество ресурсов, выраженных в таком виде:
А1zX1+А12Х2 + ... + А1nХn< В1
A21Х1 + А22Х2 + ...+ A2nXn < В2
Ат1Х1+Ат2Х2 + ... + АтпХn<Вт
где Сn, Атn и Вт — заданные постоянные величины.
В зависимости от типа задачи ограничения могут указываться также с
использованием знака равенства (=) или знака "больше или равно" (?).


Графическое линейное программирование

Несмотря на то, что графическое линейное программирование (Graphical Linear
Programming) применяется только для решения задач с двумя искомыми переменными
(или в случае с трехмерными графиками — тремя), этот метод позволяет быстро понять
основную суть линейного программирования и иллюстрирует, что происходит при
использовании симплексного метода, описанного дальше в этой главе.
Порядок решения задач графическим методом описывается ниже в контексте задачи,
связанной с деятельностью компании Puck and Pawn, специализированной на
производстве хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании
прибыль в размере 2 долл., а каждый шахматный набор — 4 долл. На изготовление одной
клюшки требуется четыре часа работы на участке А и два часа на участке В. Шахматный
набор изготавливается с затратами шести часов работы на участке A, шести часов на
участке В и одного часа на участке С. Доступная производственная мощность (Capacity
Available), выраженная в рабочих часах, участка А составляет максимум 120 часов в день;
участка В — 72 часа, а участка С— 10 часов.
Вопрос: сколько клюшек и шахматных наборов должна выпускать в день компания,
чтобы получать максимальную прибыль?
1. Сформулируйте задачу с использованием математических символов. Если

315
обозначить количество хоккейных клюшек через H, а количество шахматных наборов —
G, то целевую функцию (Objective Function) для достижения максимальной прибыли
можно выразить следующим образом.
Максимизировать Z = $2H + $4G;
при условии следующих ограничений по мощностям:
(1) 4Н + 6G < 120 (ограничение по участку А);
(2) 2H + 6G < 72 (ограничение по участку В);
(3) 1G < 10 (ограничение по участку C); и при условии, что Н, G > 0.
Такая формулировка удовлетворяет всем пяти условиям, предъявляемым к задачам
линейного программирования, описанным ниже.
1. Речь идет об ограниченных ресурсах (конечное число рабочих часов по каждому
из участков).
2. Точно сформулирована целевая функция (известны значения каждой переменной
и цель задачи).
3. Все уравнения носят линейный характер (в них отсутствуют экспоненты и
комбинационные составляющие).
4. Ресурсы однородны (для их оценки использована одна и та же единица измерения,
т.е. рабочее время).
5. Искомые переменные — делимые и неотрицательные значения (можно
изготовлять и части хоккейной клюшки или шахматного набора; однако не забывайте, что
если такой подход нежелателен, то следует воспользоваться методом целочисленного
программирования).
2. Построите график уравнений ограничений. Уравнения ограничений легко
отображаются на графике при присвоении одной из переменных нулевого значения и
нахождении значения другой на соответствующей оси координат. (Нецелые части в
неравенствах ограничений на данном этапе игнорируются.) Так, для уравнения
ограничений по участку А при R = 0, G = 20, а при G = 0, Н = 30. Для уравнения
ограничений по участку В при Н = 0 имеем G= 12, а при G= 0, Н= 36. Для уравнения
ограничений по участку С G= 10 при любых значениях Н. Соответствующие прямые
показаны на рис. 7д.1.




Рис. 7д. 1. Графическое решение задачи о хоккейных клюшках и шахматных наборах

H G Пояснение
0 120/6=20 Пересечение ограничения (1) с осью G
120/4=30 0 Пересечение ограничения (1) с осью Н
0 72/6=12 Пересечение ограничения (2) с осью G
72/2=36 0 Пересечение ограничения (2) с осью Н

316
0 10 Пересечение ограничения (3) с осью G
Пересечение линии равной прибыли (целевой функции),
0 32/4=8
соответствующей $32, с осью G
32/2=16 0 Пересечение линии равной прибыли, соответствующей $32, с осью Н
0 64/4=16 Пересечение линии равной прибыли, соответствующей $64, с осью G
64/2=32 0 Пересечение линии равной прибыли, соответствующей $64, с осью Н

3. Определите допустимую область. Направление знака неравенства в каждом
ограничении определяет область, в которой следует искать допустимое решение. В
данном случае все неравенства носят характер "меньше или равно", что означает, что
недопустимо искать любую комбинацию изделий, расположенную на графике справа и
сверху от линий ограничений. Область допустимых решений на графике рис. 7д. 1
закрашена серым и имеет форму выпуклого многоугольника. Такой многоугольник
бывает выпуклым только при условии, что прямая линия, соединяющая любые две точки
в нем, остается в его пределах. При невыполнении данного условия задача либо
неправильно сформулирована, либо не подлежит решению методом линейного
программирования.
4. Постройте график целевой функции. Целевая функция отображается на графике
следующим образом. Задайте какую-то произвольную величину общей прибыли и
найдите отрезки на осях координат, отсекаемые целевой функцией, как это было сделано
для уравнений ограничений. Целевую функцию в данном контексте часто называют
линией равной прибыли, или линией равносильного вклада, поскольку она отображает все
возможные комбинации двух видов продукции для заданной прибыли. Так, например, на
штриховой прямой, на графике ближе всех расположенной к началу координат, мы можем
определить все возможные комбинации хоккейных клюшек и шахматных наборов,
которые дадут прибыль в 32 долл., выбрав для этого любую точку на прямой и найдя
соответствующие количества каждого из производимых изделий по ее координатам. Так,
для точки а комбинация, которая принесет компании прибыль в 32 долл., будет 10
клюшек и 3 набора. Этот результат можно проверить подстановкой полученных с
помощью графика значений Н — 10, G = 3 в уравнение целевой функции:
($2 х 10) + ($4 х 3) = $20 + $12 = $32.
5. Найдите оптимальную точку. Можно математически доказать, что оптимальная
комбинация искомых переменных всегда находится в крайней (угловой) точке выпуклого
многоугольника. На графике рис. 7д.1 таких точек четыре (исключая точку начала оси
координат), и для определения того, какая из них оптимальная, существует два способа.
Первый заключается в алгебраическом поиске решений для разных вершин
многоугольника и оты-
скании среди них вершины с максимальной прибылью. Такой метод предполагает
одновременное решение уравнений для разных пар пересекающихся прямых и
подстановку полученных параметров переменных в целевую функцию. Так, например,
вычисления для пересечения линий 2Н +6(7= 72 и G = 10 будут следующими. Поставив G
= 10 в 2Н + 6G = 72, получаем
2Н+ (6х 10) = 72.
Следовательно, 2H= 12, а Н= 6. Подставив в целевую функцию значения H=6 и G =
10, получаем
прибыль = $2# + $4G = ($2 х 6) + ($4 х 10) =
$12 + $40 = $52.
Этот метод можно немного видоизменить, взяв параметры Н и G непосредственно из
графика и подставляя их в целевую функцию, как это делалось в процессе предыдущих
вычислений. Недостаток данного подхода: при решении задач с большим количеством
ограничительных уравнений возможных точек для оценки бывает очень много, и
процедура математического тестирования каждой из них становится просто

317
неэффективной.
Второй метод, который обычно предпочитают специалисты, заключается в
непосредственном поиске оптимальной точки на линии равной прибыли. Эта процедура
состоит в том, что на графике проводится прямая, параллельная любой произвольно
выбранной исходной прямой равной прибыли, но наиболее удаленной от начала
координат графика в пределах области допустимых значений. (В задачах на минимизацию
затрат прямая равной прибыли должна проходить через точку, самую близкую к началу
координат.) На рис. 7д.1 крайнюю (угловую) точку пересекает штриховая линия,
соответствующая уравнению $2H+ $4G= $64. Обратите внимание, что исходная
произвольно выбранная прямая равной прибыли обязательна, поскольку она отображает
угол наклона целевой функции для конкретной задачи2.
2
Угол наклона целевой функции определяется коэффициентом, который в данном примере равен —
2. Обозначив прибыль через Р, имеем P=$2H+$4G;$2H=P-$4G, H=pl2-2G. Из этого следует, что значение
коэффициента наклона равно — 2.

Это очень важно, так как при другой целевой функции (например, попробуйте
подставить в значение прибыли 3Н+ 3G) наиболее удаленной от начала оси координат
может быть другая точка. При условии, что уравнение $2H+$4G=$64 является
оптимальным, значение каждой переменной, указывающее, какое количество изделий
следует производить, можно определить по графику для оптимальной точки: 24
хоккейные клюшки и 4 шахматных набора. Любые другие комбинации дадут компании
меньшую прибыль.



Симплексный метод

Симплексный метод (Simplex Method) представляет алгебраическую процедуру, в
результате которой аналитик, последовательно выполняя ряд повторяющихся операций,
прогрессивно приближается к оптимальному решению3. Теоретически данным методом
можно решать задачи, включающие любое количество переменных и ограничений, но
если в них, например, больше четырех переменных или ограничений, то вычисления
лучше проводить на компьютере. И все же для того, чтобы знать, как составляются
уравнения, которые надо вводить в компьютерную программу, и уметь эффективно
использовать итоги, полученные в результате работы в этой программе, предлагаем вам
выполнить всю процедуру использования симплексного метода без помощи
компьютерной техники.
3
Термин "симплексный" произошел отнюдь не от английского слова simple (простой, простая). Он
заимствован из n-мерной геометрии.


Шесть этапов симплексного метода

Симплексный метод включает в себя ряд отдельных этапов. Все они подробно
описаны и подытожены в конце данного раздела. Для наглядной демонстрации процедуры
поиска решения симплексным методом воспользуемся все той же задачей определения
оптимальных объемов производства хоккейных клюшек и наборов шахмат.
Этап 1. Сформулируйте задачу. Вспомните, что, если цель состоит в максимизации
прибыли, то мы имеем такие условия задачи.
Максимизировать Z = $2H + $4G;
при условии, что

318
4# + 6G < 120 (ограничение по участку А);
2Н + 6G < 72 (ограничение по участку В);
1G < 10 (ограничение по участку С);
Н,С>0 (требование отсутствия отрицательных значений).
Этап 2. Составьте исходную таблицу со свободными переменными. При
использовании симплексного метода необходимо выполнить две следующие серьезные
корректировки задачи:
• ввести свободные переменные и
• построить таблицу решений.
Введение свободных переменных. В каждое уравнение ограничения вводятся
свободные переменные. Свободная переменная (Slack Variable), которая на практике
может рассматриваться как неиспользуемый ресурс, с математической точки зрения
представляет собой значение, необходимое для уравнивания двух частей
ограничительного уравнения. Иными словами, она предназначена для преобразования
неравенства в равенство. Для рассматриваемой нами задачи потребуется ввести три
свободные переменные: S1 — для первого уравнения ограничений, S2 — для второго и 5,
— для третьего.
В результате наши уравнения примут следующий вид:
4H+6G+1S1= 120; 2H+6G+ 1S2= 72; 1G + 1S3 = 10 .
Чтобы в каждом уравнении ограничений были представлены все свободные
переменные, все они включаются в уравнения с множителями, равными нулю. В
результате такой корректировки получаем следующую систему уравнений:
4H + 6G + IS1 +0S2 + 0S3 = 120; 2H+6G+ 0S1 +\S2 + 0S3 = 72; 0H+1G + 0S01+052 +
1S3,= 10.
Обратите внимание, что в третье уравнение введена переменная Н с нулевым
множителем. В целевую функцию также добавляются свободные переменные, но
поскольку они никак не влияют на прибыль, их множители равны $0:
Z= $2H + $4G + 05, +0S1 + 0S3.
Построение исходной таблицы. Исходная таблица (табл. 7д.1) представляет
удобный способ подготовки задачи к решению с применением симплексного метода.
В данной таблице представлены.
1. Свободные переменные поэтапного решения.
2. Прибыль, соответствующая решению.
3. Переменная (если таковая существует), которая при вводе в решение больше
других увеличивает прибыль.
4. Показатель приведения переменных в решении (при вводе одной единицы каждой
переменной). Этот показатель называется коэффициентом замещения.
5. Стоимость добавленной единицы ресурса (например, часа), которую называют
теневой ценой.
Первые четыре характеристики мы обсудим сейчас, в ходе описания табл. 7д.1, а о
последней поговорим подробнее дальше в этом дополнении к главе.
В верхней строке табл. 7д.1 содержатся значения Сj (вклад в общую прибыль,
соответствующий выпуску одной единицы каждого вида продукции). В этой строке
приведены множители переменных целевой функции. Они остаются неизменными во всех
последующих расчетных таблицах. В первом столбце, озаглавленном Сj для удобства
приведены значения прибыли на единицу переменных, включенных в решение на каждом
этапе решения задачи.

Таблица 7д.1. Исходная таблица для задачи о производстве хоккейных клюшек и шахматных
наборов

Сj -й столбец Сj -я строка Количество Участок
$2 $4 $0 $0 $0

319
Совокупное
Н G S1 S2 S3
решение
$0 S1 4 6 1 0 0 120 А
$0 S2 2 6 0 1 0 72 В
$0 S3 0 1 0 0 1 10< С
Zj $0 $0 $0 $0 $0 $0
$4
Cj-Zj $2 $0 $0 $0
Т

Переменные, выбранные для первой таблицы, перечислены в столбце "Совокупное
решение". Как видно, на первом шаге решения рассматриваются только свободные
переменные с нулевыми коэффициентами прибыли, что и отображено в столбце Сj табл.
7д.1.
Переменные уравнений ограничений приведены в столбцах справа от столбца,
озаглавленного "Совокупное решение", и для каждой переменной указаны конкретные
коэффициенты при них для всех уравнений ограничений; т.е. 4, 6, 1, 0 и 0 — это
коэффициенты для участка А; 2, 6, 0, 1 и 0 — для участка В, а 0, 1, 0, 0 и 1 — для участка
С.
На основе этих показателей можно определить коэффициенты замещения. Так,
например, в третьем столбце под переменной Н перечислены цифры 4, 2 и 0. Для каждой
единицы продукции Н, вводимой в решение, из доступных ресурсов потребуется извлечь
четыре единицы S1 две единицы S2 и нуль единиц S3 Значения в столбце "Количество"
показывают, сколько единиц каждого ресурса есть в наличии на каждом участке. В
исходной таблице воспроизводится правая часть каждого уравнения ограничений.
Значения Zj во второй строке снизу (за исключением значения в столбце "Количество")
отражают размер валовой прибыли, от которой отказывается компания при введении в
решение одной единицы соответствующей переменной, обозначенной нижним индексом j.
Значение Zj, указанное в колонке "Количество", — это общая прибыль для данного
решения. В исходном решении симплексной задачи все значения Zj нулевые, поскольку
реальной продукции не производится (все участки простаивают), а следовательно, и
никакая валовая прибыль при замещении переменных потеряна не будет.
В нижней строке таблицы содержатся показатели чистой прибыли на единицу
продукции, полученные в результате введения в решение одной единицы конкретной
переменной. Эта строка обозначена в таблице Сj — Zj. Процедура вычисления значений Zj
и Cj — Zj отображена в табл. 7д.2.
Исходное решение нашей задачи содержится уже непосредственно в табл. 7д.1:
компания производит 120 единиц S1, 72 единицы S2 и 10 единиц S3. Общая прибыль для
этого решения $0, следовательно, никакие мощности еще не распределялись и никакой
реальной продукции не производилось.
Этап 3. Определите, какую переменную следует включить в решение. Получить
лучшее решение задачи можно в том случае, если разность Cj — Zj будет положительной.
Как уже отмечалось выше, в ней приводится чистая прибыль, получаемая при добавлении
одной единицы переменной из соответствующего столбца к решению. В данном примере
мы можем выбирать из двух положительных значений: $2 для переменной H и $4 для
переменной G. Поскольку наша цель заключается в максимизации прибыли, логично
выбрать для включения в решение переменную, которая даст наибольшие результаты, т.е.
в нашем случае G. В табл. 7д.1 столбец для этой переменной помечен маленькой стрелкой,
расположенной под ним. (Для достижения каждого улучшенного решения одновременно
можно добавлять только одну переменную.)

Таблица 7д.2. Вычисления показателей Zj и Сj – Zj

320
CjH CjG CjS1 CjS2 CjS3 C jX Количество
$0x4=0 $0x6=0 $0x1=0 $0x0=0 $0x0=0 $0x120=0
+ + + + + +
$0x2=0 $0x6=0 $0x0=0 $0x1=0 $0x0=0 $0x72=0
+ + + + + +
$0x0=0 $0x1=0 $0x0=0 $0x0=0 $0x1=0 $0x10=0
ZH=$0 ZG=$0 ZSI=$0 ZS2=$0 ZS3=$0 ZQ=$0
Вычисление
Сj - Zj
CH-ZH=$2-
CS1- ZS1=$0-0=$0
0=$2
CG-ZG=$4-
CS2- ZS2=$0-0=$0
0=$4
CS3- ZS3=$0-0=$0

Этап 4. Определите, какую переменную следует заменить. В решение
рациональнее ввести переменную G, следующим шагом будет выбор переменной,
подлежащей замене. Для этого разделим каждое значение столбца "Количество" на
соответствующее ему значение в столбце G и выберем переменную, которая даст
наименьшее положительное значение. Именно она и будет замещена.
Для строки S1: 120/6 = 20.
Для строки S2: 72/6 = 12.
Для строки S3: 10/1 = 10.
Поскольку наименьшим значением является 10, нам следует заместить переменную
S3. В табл. 7д.1 строка для этой переменной помечена маленькой стрелкой,
расположенной в правой части таблицы. Это максимальное значение G, которое может
быть включено в решение. Другими словами, выпуск более чем 10 единиц G превысит
имеющиеся в наличии производственные мощности участка С. Этот результат можно
проверить математически, рассмотрев ограничение G ? 10, или визуально, исследовав
графическое отображение задачи, показанное на рис. 7д.1. Из этого графика также видно,
что 20 и 12 — это значения G для двух других ограничений, и если ограничение С ? 10
удалить, то в решение можно было бы дополнительно ввести 2 единицы G.
Этап 5. Вычислите новые значения строки для вводимой переменной. Для
введения в решение переменной G требуется замещение всей строки S3. Значения G для
замещения строки получают делением каждого текущего значения S3 на значение в
столбце G, соответствующее данной строке. Это значение называют элементом
пересечения (Intersectional Element), поскольку оно находится на пересечении строки и
столбца. Эту перекрестную взаимосвязь выделяют из остальной таблицы, после чего
выполняют все необходимые операции деления, как показано в табл. 7д.З.

Таблица 7д.З. Вычисление новых значений строки для вводимой переменной

G
6
6
S3 0 1 0 0 1 10 0/1 =0, 1/1 =1,0/1 =0,
0/1 =0, 1/1 =1, 10/1 = 10
$4

321
Этап 6. Проверьте остальные строки. Новые значения третьей строки (теперь
относящиеся к переменной G) таковы: 0, 1, 0, 0, 1 и 10. В нашем случае они совпадают со
старыми показателями третьей строки таблицы.
Введение в задачу новой переменной влияет на значения остальных переменных, и
для обновления таблицы необходимо провести второй тур вычислений. В нашем случае
мы хотим определить, как влияет введение переменной G на строки S1 и S2. Такие расчеты
выполняются с использованием метода, получившего название метода рычага (Pivot
Method), либо алгебраической подстановкой. Первый метод представляет собой больше
механическую процедуру и широко используется на практике, а второй чаще применяется
для объяснения логики процесса обновления. Процедура использования метода рычага
для получения новых значений S1 и S2 отображена в табл. 7д.4. (По сути, данный метод
заключается в вычитании умноженных на 6 значений строки 3 из строк S1 и S2).
Коррекция таблицы алгебраической подстановкой заключается в подстановке всего
уравнения для вводимой строки во все остальные строки и решение его для всех
измененных значений переменной каждой строки. Процедура, представленная в табл.
7д.5, показывает, что решение задачи линейного программирования симплексным
методом по сути сводится к решению системы уравнений.
Выделив множители у переменных для новой строки S1 из табл. 7д.5, получаем такие
же значения, как и при использования метода рычага: 4, 0, 1, 0, –6, 60.
Результаты вычислений на этапах с третьего по шестой вместе с вычислениями Zjи
Cj — Zj отображены в табл. 7д.6. Воспользовавшись терминологией, принятой в
математическом программировании, можно сказать, что мы закончили первую итерацию
поиска решения задачи.
Оценивая полученное решение, следует обратить особое внимание на два момента:
прибыль составляет 40 долл., но важнее то, что возможно дальнейшее улучшение этого
показателя, поскольку в строке Сj —Zj мы имеем положительное значение.
Вторая итерация. Поскольку переменная Н имеет наибольший показатель Cj— Zj=
2, она и будет вводиться. Заменяемой переменной будет S2, так как при делении значений
из столбца "Количество" на соответствующие им значения из столбца Н она получит
наименьшее значение:
S1 = 60/4 = 14; S2 = 12/2 = 6; S3 = 10/0 = ?.
Таким образом, в строку Я будут введены следующие значения:
2/2=1, 0/2 = 0, 0/2 = 0, 1/2 = 1/2, -6/2 = -3, 12/2 = 6.
Откорректированная в табл. 7д.7 строка S1.
0, 0, 1, -2, 6, 36.
Откорректированная в табл. 7д.7 строка С:
0, 1,0,0, 1, 10.
Воспользовавшись результатами табл. 7д.7, построим третью табл. 7д.8.
Анализируя табл. 7д.8, мы видим, что, введя максимальное значение S3 (что
технически вполне осуществимо), можно достичь дальнейшего улучшения. Из расчетов в
нижней части табл. 7д.8 получаем, что вследствие ограничения по показателю S1
максимальное значение S3, которое можно будет ввести в решение, составляет шесть
единиц. Заменив показатель S1 показателем S3 и проведя корректировку, составляем табл.
7д.9.
Поскольку строка Cj — Zj содержит только отрицательные значения, дальнейшее
улучшение невозможно, следовательно, в результате трех итераций мы достигли
оптимального решения (Н = 24, G = 4). Во врезке "Краткое изложение этапов
симплексного метода: задача на максимизацию прибыли" вашему вниманию представлено
краткое изложение всех пройденных нами этапов.
Задача минимизации затрат. В примере с компанией Риск and Pawn мы имели
дело с задачей максимизации. Процедура, выполняемая при решении задач

322
минимизации, практически идентична. Различие заключается лишь в том, что ставится
противоположная цель и потенциальное улучшение отображается отрицательным
значением Сj — Zj. Следовательно, вначале в решение будет вводиться переменная с
наибольшим отрицательным значением столбец для этой переменной помечен маленькой
стрелкой, расположенной под ним. (Для достижения каждого улучшенного решения
одновременно можно добавлять только одну переменную.)
Cj — Zj. Однако при решении задачи данного вида необходимо ввести
дополнительные переменные, так как задачи минимизации включают с себя ограничения
типа "больше или равно", которые должны обрабатываться иначе, чем ограничения
"меньше или равно", характерные для задач максимизации. К особенностям
использования ограничений типа "больше или равно" и "меньше или равно" мы еще
вернемся в этом дополнении к главе.

Таблица 7д.4. Метод рычага

Соответст
Элемент Элемент
вующий
Старая Соответствующий Старая
пересечени пересечени
Обновленна Обновленна
строка - X элемент новой - строка - X элемент -
я старой я строка S1 я старой я строка S2
новой
S1 строки G S2
строки S1 строки S2
строки G
4 - (6 X 0) = 4 2 - (6 X 0) = 2
6 - (6 X 1) = 0 6 - (6 X 1) = 0
1 - (6 X 0) = 1 0 - (6 X 0) = 0
0 - (6 X 0) = 0 1 - (6 X 0) = 1
0 - (6 X 1) = -6 0 - (6 X 1) = -6
120 - (6 10) = 60 72 - (6 X 10) = 12

Таблица 7д.5. Алгебраическая подстановка

Нахождение новых значений для S1
1. Запишите исходную строку для S1 с добавленными к ней свободными переменными (из
первой таблицы):
4H + 6G + 1S, + 0S2 + 0S3 = 120.
2. Запишите вводимую строку как ограничение с добавленными свободными переменными
(это значения, вычисленные в табл. 7д.З):
0H+G + 0S1+ 0S2+1S3 = 10.
3. Перестройте вводимую строку с учетом вводимой переменной G:
10 -S3.
4. Подставьте (10 - S3) для переменной G в первое уравнение (старая строка для S1) и
решите полученное уравнение для каждого коэффициента переменной:
4Н + 6(10- S3) + 1S1, = 120
4H + 60-6S3+1S1 = 120
4H+1S1-6S3 = 120-60
4Н + 1S1 - 6S3 = 60
или
4Н + 0G + 1S1 + 0S2 - 6S3 = 60.


Таблица 7д.6. Вторая таблица для задачи о производстве хоккейных клюшек и шахматных
наборов

Сj Совокупное Количество
$2 S4 $0 $0 $0


323
решение S1
Н G s2 s3
$0 4 0 1 0 -6 60
S1
$0 2 0 0 1 -6 12<-
S2
$4 0 1 0 0 1 10
G
$0 $0 $0 $40
Zj $4 $4
$2
$0 $0 $0 $-4
Cj-Zj
Т

Этап 4. Определите, какую переменную следует заменить. В решение
рациональнее ввести переменную G, следующим шагом будет выбор переменной,
подлежащей замене. Для этого разделим каждое значение столбца "Количество" на
соответствующее ему значение в столбце G и выберем переменную, которая даст
наименьшее положительное значение. Именно она и будет замещена.
Для строки S1: 120/6 = 20.
Для строки S2: 72/6 = 12.
Для строки S3: 10/1 = 10.
Поскольку наименьшим значением является 10, нам следует заместить переменную
S3. В табл. 7д.1 строка для этой переменной помечена маленькой стрелкой,
расположенной в правой части таблицы. Это максимальное значение G, которое может
быть включено в решение. Другими словами, выпуск более чем 10 единиц G превысит
имеющиеся в наличии производственные мощности участка С. Этот результат можно
проверить математически, рассмотрев ограничение G ? 10, или визуально, исследовав
графическое отображение задачи, показанное на рис. 7д.1. Из этого графика также видно,
что 20 и 12 — это значения G для двух других ограничений, и если ограничение G ? 10
удалить, то в решение можно было бы дополнительно ввести 2 единицы G.
Этап 5. Вычислите новые значения строки для вводимой переменной. Для
введения в решение переменной G требуется замещение всей строки S3. Значения G для
замещения строки получают делением каждого текущего значения 5, на значение в
столбце G, соответствующее данной строке. Это значение называют элементом
пересечения (Intersectional Element), поскольку оно находится на пересечении строки и
столбца. Эту перекрестную взаимосвязь выделяют из остальной таблицы, после чего
выполняют все необходимые операции деления, как показано в табл. 7д.З.

Таблица 7д.З. Вычисление новых значений строки для вводимой переменной

G
6
'
6
S3 0 1 0 0 1 10 0/1 =0, 1/1 =1,0/1 =0,
0/1 =0, 1/1 =1, 10/1 = 10
$4

Этап 6. Проверьте остальные строки. Новые значения третьей строки (теперь
относящиеся к переменной G) таковы: 0, 1, 0, 0, 1 и 10. В нашем случае они совпадают со
старыми показателями третьей строки таблицы.
Введение в задачу новой переменной влияет на значения остальных переменных, и
для обновления таблицы необходимо провести второй тур вычислений. В нашем случае
мы хотим определить, как влияет введение переменной G на строки S1 и S2. Такие расчеты
выполняются с исполь-
зованием метода, получившего название метода рычага (Pivot Method), либо
324
алгебраической подстановкой. Первый метод представляет собой больше механическую
процедуру и широко используется на практике, а второй чаще применяется для
объяснения логики процесса обновления. Процедура использования метода рычага для
получения новых значений S1 и S2 отображена в табл. 7д.4. (По сути, данный метод
заключается в вычитании умноженных на 6 значений строки 3 из строк S1 и S2.)
Коррекция таблицы алгебраической подстановкой заключается в подстановке всего
уравнения для вводимой строки во все остальные строки и решение его для всех
измененных значений переменной каждой строки. Процедура, представленная в табл.
7д.5, показывает, что решение задачи линейного программирования симплексным
методом по сути сводится к решению системы уравнений.
Выделив множители у переменных для новой строки S1 из табл. 7д.5, получаем такие
же значения, как и при использования метода рычага: 4, 0, 1, 0, —6, 60.
Результаты вычислений на этапах с третьего по шестой вместе с вычислениями Zj и
Cj — Zj отображены в табл. 7д.6. Воспользовавшись терминологией, принятой в
математическом программировании, можно сказать, что мы закончили первую итерацию
поиска решения задачи.
Оценивая полученное решение, следует обратить особое внимание на два момента:
прибыль составляет 40 долл., но важнее то, что возможно дальнейшее улучшение этого
показателя, поскольку в строке Cj —Zj мы имеем положительное значение.
Вторая итерация. Поскольку переменная Н имеет наибольший показатель Cj— Zj=
2, она и будет вводиться. Заменяемой переменной будет S2, так как при делении значений
из столбца "Количество" на соответствующие им значения из столбца Н она получит
наименьшее значение:
S1 = 60/4 = 14;
S2 = 12/2 = 6;
S3 = 10/0 = &.
Таким образом, в строку Н будут введены следующие значения:
2/2=1, 0/2 = 0, 0/2 = 0, 1/2 = 1/2, -6/2 = -3, 12/2 = 6.
Откорректированная в табл. 7д.7 строка S1:
0, 0, 1, -2, 6, 36.
Откорректированная в табл. 7д.7 строка G:
0, 1, 0, 0, 1, 10.
Воспользовавшись результатами табл. 7д.7, построим третью табл. 7д.8.
Анализируя табл. 7д.8, мы видим, что, введя максимальное значение S3 (что
технически вполне осуществимо), можно достичь дальнейшего улучшения. Из расчетов в
нижней части табл. 7д.8 получаем, что вследствие ограничения по показателю S1
максимальное значение S3, которое можно будет ввести в решение, составляет шесть
единиц. Заменив показатель S1 показателем S3 и проведя корректировку, составляем табл.
7д.9.
Поскольку строка Cj — Zj содержит только отрицательные значения, дальнейшее
улучшение невозможно, следовательно, в результате трех итераций мы достигли
оптимального решения (Н— 24, G= 4). Во врезке "Краткое изложение этапов
симплексного метода: задача на максимизацию прибыли" вашему вниманию представлено
краткое изложение всех пройденных нами этапов.
Задача минимизации затрат. В примере с компанией Риск and Pawn мы имели
дело с задачей максимизации. Процедура, выполняемая при решении задач
минимизации, практически идентична. Различие заключается лишь в том, что ставится
противоположная цель и потенциальное улучшение отображается отрицательным
значением Сj — Zj Следовательно, вначале в решение будет вводиться переменная с
наибольшим отрицательным значением
Cj — Zj. Однако при решении задачи данного вида необходимо ввести
дополнительные переменные, так как задачи минимизации включают с себя ограничения

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

Таблица 7д.4. Метод рычага

Соответству Соответству
Элемент Элемент Обновле
Старая Обновленн Старая
ющий ющий
пересечения пересечения нная
строка ая строка строка
- X - X =
элемент элемент
старой старой строка
S1 S, S2
новой новой
строки S, строки S2 S2
строки G строки G
4 - (6 X 0) = 4 2 - (6 X 0) = 2
6 - (6 X 1) = 0 6 - (6 X 1) = 0
1 - (6 X 0) = 1 0 - (6 X 0) = 0
0 - (6 X 0) = 0 1 - (6 X 0) = 1
0 - (6 X 1) = -6 0 - (6 X 1) = -6
120 - (6 10) = 60 72 - (6 X 10) = 12


Таблица 7д.5. Алгебраическая подстановка

Нахождение новых значений для S1
1. Запишите исходную строку для S1 с добавленными к ней свободными переменными (из
первой таблицы):
4H + 6G+1S1+ 0S2 + 0S3= 120.
2. Запишите вводимую строку как ограничение с добавленными свободными
переменными (это значения, вычисленные в табл. 7д.З):
0H+G + 0S1 + 0S2+1S3=10.
3. Перестройте вводимую строку с учетом вводимой переменной G:
10-S3.
4. Подставьте (10 - Sз) для переменной G в первое уравнение (старая строка для S1) и
решите полученное уравнение для каждого коэффициента переменной:
4Н + 6(10- S3) + 1S1 = 120
4Н + 60-6S3+1S1 = 120
4H+1S1-6S3= 120-60
4Н + 1S1 - 6S3 = 60
или
4H + 0G + 1S1 + 0S2-6S3 = 60.

Таблица 7д.6. Вторая таблица для задачи о производстве хоккейных клюшек и шахматных
наборов

Совокупное
$2 S4 $0 $0 $0
решение
Сj Количество
Н G S1 s2 s3
$0 S1 4 0 1 0 -6 60
$0 S2 2 0 0 1 -6 12<
$4 G 0 1 0 0 1 10
Zj $0 $4 $0 $0 $4 $40


326
$2
Cj-Zj $0 $0 $0 $-4
Т

Таблица 7д.7. Корректировка строк S1 и G

Элемент Элемент
Старая Соответствующий Новая Старая Соответствующий
Обновленная
пересечения X элемент новой пересечения X элемент новой
строка - строка строка -
строка G
старой старой
s, строки Н S, G строки Н
S G
4 - (4 X 1) = 0 0 - (0 X 1) = 0
0 - (4 X 0) = 0 1 - (0 X 0) = 1
1 - (4 X 0) = 1 0 - (0 X 0) = 0
0 - (4 X 1/2) = -2 0 - (0 X 1/2) = 0
-6 - (4 X -3) = 6 1 - (0 X -3) = 1
60 - (4 6) = 36 10 - (0 X 6) = 10


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

Совокупное
$2 $4 $0 $0 $0
решение
Сj Количество
Н G S1 S2 S3
$0 0 0 1 6 36<
S1 -2
$2 1 0 0 1/2 -3 6
Н
$4 0 1 0 0 1 10
G
$2 $4 $0 $1 $-2 $52
Zj
$2
$0 $0 $0 $-1
Cj-Zj
т
36/6 = 6 6/-3 = -2 (отрицательное значение) 10/1 = 10
Поскольку в данной задаче три уравнения ограничений, в решении должно быть три
переменные с неотрицательными значениями и отрицательное значение нельзя вводить в решение.

Таблица 7д.9. Четвертая таблица для задачи о производстве хоккейных клюшек и
шахматных наборов (оптимальное решение)

$2 54 $0 $0 $0
Совокупное
Сj Количество
решение Н G S1 S2 S3
$0 S3 0 0 1/6 -1/3 1 6
$2 н 1 0 1/2 -1/2 0 24
$4 G 0 1 -1/6 1/3 0 4
Zj $2 $4 $1/3 $1/3 $0 $64
$0
Cj-Zj $0 $-1/3 $-1/3 $0
Т



Определение пути поиска решения при симплексном методе

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

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

Краткое изложение этапов симплексного метода: задача на максимизацию прибыли

1. Сформулируйте задачу: определите целевую функцию и наметьте ограничения.
2. Постройте исходную таблицу со свободными переменными в совокупном решении и
вычислите строки Zj и Cj — Zj.
3. Определите, какую переменную следует ввести в решение (наибольшее значение Сj — Zj).
4. Определите, какую переменную следует заменить (по наименьшему положительному
коэффициенту, получаемому делением значений столбца "Количество" на соответствующее ему
значение из столбца, выбранного на этапе 3).
5. Вычислите новые значения строки для ввода переменной и вставьте в таблицу новую
строку (строка, подлежащая замене, плюс элемент пересечения).
6. Откорректируйте остальные строки и введите их в новую таблицу; вычислите новые
значения для строк Zj и Cj — Zj (показатели исходных строк, минус элемент пересечения из
исходной строки, умноженный на соответствующий ему элемент из новой строки). Если в
результате вы не получаете ни одного положительного значения Сj — Zj, значит, данное решение
будет оптимальным. Если же такое значение есть, повторите этапы с 3 по 6.

Обратимся к графику на рис. 7д.2, составленному для обсуждаемого нами примера
поиска решения симплексным методом, начиная с исходной точки а (прибыль равна
нулю).




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

В ходе первой итерации в точке b было введено 10 единиц С (прибыль составила
$40). В ходе второй итерации в точке с было введено 6 единиц Н (прибыль составила $52).
Третья итерация привела задачу к окончательному оптимальному решению в точке d
(прибыль составила $64). Обратите внимание, что в ходе этой процедуры мы не
вычисляли показатели прибыли для всех точек, имеющихся в задаче. Если же это сделать
и заглянуть дальше — на основе вычислений Cj — Zj чтобы узнать, возможно ли
дальнейшее улучшение в результате перемещения в точку с, то мы убедимся, что данное
изменение уже не приведет ни к каким улучшениям. Эти две характеристики — оценка
угловых точек и оценка дальнейших возможностей улучшений — и составляют основу
симплексного метода.

328
Еще одно свойство симплексного метода состоит в том, что в нем не предусмотрено
достижение оптимальной точки по кратчайшему маршруту вокруг допустимой области.
На графике видно, что если бы процедура решения следовала по пути а>е>d,
оптимальное решение можно было бы получить в результате всего двух, а не трех
итераций.
Мы не следовали этим маршрутом потому, что прибыль на один шахматный набор
была выше прибыли на одну клюшку, вследствие чего симплексный метод указал, что в
ходе первой итерации следует вводить не переменную Н, а переменную G, что в свою
очередь определило направление последующих итераций к точкам c и d. Обратите
внимание: в силу того, что пространство решения имеет форму выпуклого
многоугольника (как говорилось раньше), прибыль не может повыситься, понизиться и
затем опять повыситься.


Анализ чувствительности решения и теневые цены

Внимательно анализируя последнюю (оптимальную) симплексную таблицу (см.
табл. 7д.9), можно получить немало дополнительных сведений. Кроме конкретного
решения, она предоставляет ценную информацию об использовании ресурсов, об
интервале, в котором оптимальное решение остается неизменным, а также об интервале, в
котором коэффициенты целевой функции не изменяют оптимального решения. В
частности, она позволяет ответить на такие вопросы: следует ли вашей фирме приобретать
дополнительные ресурсы? Если — да, то какую цену вы готовы заплатить? Сколько
единиц ресурсов следует приобрести по этой цене? Подобные вопросы можно задавать и
относительно продажи ресурсов: даже если данный ресурс используется в настоящее
время для выпуска продукции фирмы, не будет ли выгоднее отказаться от дальнейшего
производства и продать его по определенной цене? Находить правильные ответы на такие
вопросы очень важно, и симплексный метод позволяет это делать. Причем эти ответы
дополняют оптимальное решение, вычисленное в соответствии с целевой функцией в
табл. 7д.9.
Кроме перечисленных выше вопросов, можно задать и такой вопрос: если мы
изменим прибыль на единицу продукции (изменив коэффициент целевой функции), не
приведет ли это к изменению оптимального решения? Отыскивая на него ответ, мы имеем
дело с анализом чувствительности (Sensitivity Analysis), который заключается в
определении того, насколько изменится решение в результате некоторых изменений
целевой функции, или наоборот, как изменение решения повлияет на целевую функцию.
Вернемся к табл. 7д.9. Значения Cj — Zj, связанные со свободными переменными,
называют теневыми ценами (Shadow Prices), безубыточными ценами, предельными
значениями или приростными значениями. Обратите внимание, теневые цены для S1 и S2
составляли $1/3 (или 33 цента) каждая, а для S3 — $0. При любом превышении этой цены
управленческий персонал будет стремиться к продаже ресурсов, а при понижении ниже
этого уровня — приобрести их. А теперь предлагаем вам еще раз рассмотреть, как
решается эта задача, на этот раз с применением доступной компьютерной техники.


Решение задач линейного программирования в MS Excel

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

329
решения) запускается из меню Tools (Сервис), после чего появляется диалоговое окно,
запрашивающее информацию, необходимую для ее работы.
Вначале нужно поставить задачу, указав целевую ячейку (или целевую функцию),
изменяемые ячейки (искомые переменные) и ячейки ограничений. На рис. 7д.З
изображена электронная таблица с информацией, которая необходима для решения
данной задачи.
Поле Target Cell (Установить целевую ячейку) (в нашем случае ячейка D5) содержит
формулу, умножающую количество произведенных клюшек и шахматных наборов на
соответствующую им прибыль; значения, указанные в поле Changing Cells (Изменяя
ячейки), соответствуют искомым переменным задачи. В поле Subject to Constraints
(Ограничения) указаны ячейки для введения конкретных ограничений на решение.
Обратите внимание, что в диалоговом окне Solver (Поиск решения) необходимо указать,
что наши значения для решения должны быть больше или равны нулю.
На рис. 7д.З не показано диалоговое окно Options (Параметры), но если его вывести
на экран, то появится поле, в котором можно указать, что данная задача является
линейной, что позволяет значительно ускорить процесс ее решения. В этом окне, которое
управляет механизмом поиска решения используемым программой Solver (Поиск
решения), можно выбрать и многие другие варианты. Данная программа способна решать
задачи с использованием различных стратегий поиска, отличных от симплексного метода.




Рис. 7д. 3. Поиск решения задачи (Solver) в программе Microsoft Excel

После введения информации в это диалоговое окно можно нажать кнопку Solve
(Выполнить) и решить задачу. При этом мы получим несколько разных отчетов. Наиболее
интересными отчетами для нашей задачи являются Answer Report (Отчет по результатам)
и Sensitivity Report (Отчет по устойчивости), примеры которых приведены на рис. 7д.4.
Answer Report (Отчет по результатам) включает окончательные ответы по общей
прибыли (64 долл.) и по количествам производимой продукции (24 хоккейные клюшки и 4
шахматных набора). В разделе Constraints (Ограничения) этого отчета отображено
состояние каждого ресурса, из которого видно, что компанией будут загружены все

330
станки участков А и В, а станки участка С простоят 6 часов.
Sensitivity Report (Отчет по устойчивости) делится на две части. Первая часть
озаглавлена "Изменяемые ячейки" и соответствует коэффициентам целевой функции.
Прибыль на единицу продукции для клюшек может увеличиться либо уменьшиться на
0,67 долл. (т.е. может находиться между 2,67 и 1,33 долл.), не оказывая при этом влияния
на решение. Точно так же прибыль на единицу шахматных наборов может быть между 6 и
3 долл., и решение при этом также не изменится. В случае с участком А ограничение
увеличится до 144 (120 + 24) или уменьшится до 84 единиц, что даст в результате
повышение либо снижение целевой функции на 0,33 долл. соответственно. Ограничение
для участка В увеличится до 90 единиц или уменьшится до 60 с тем же изменением
целевой функции в 0,33 долл.
Что касается участка С, то ограничение может увеличиваться до бесконечности (IE +
30 — это на рис. 7д.4 мудреная запись очень большого числа, принятая в Excel) или
уменьшиться на 4 единицы, не изменяя при этом целевую функцию.


Транспортный метод

Транспортный метод (Transportation Method) представляет собой упрощенный
специфический вариант симплексного метода. Он получил такое название потому, что
широко применяется для решения задач, связанных с транспортировкой продукции из
разных источников в несколько пунктов назначения. Задачи такого типа обычно
преследуют одну из двух возможных целей: минимизация затрат по доставке n-го
количества единиц продукции в m-е число пунктов назначения и максимизация прибыли
от транспортировки n-ro количества единиц продукции в т пунктов назначения. Решение
транспортных задач, как правило, выполняется в три стадии, которые мы обсудим на
простом примере.




331
Рис. 7д.4. Отчеты Microsoft Excel Solver

Предположим, компания Риск and Pawn владеет четырьмя фабриками, продукция с
которых поступает на четыре склада, и управленческий персонал хочет составить график
доставки шахматных наборов с минимальными затратами на основе показателей
ежемесячного объема выпускаемой продукции. Объем поставок фабрик, потребности
складов и издержки по транспортировке каждой упаковки шахмат отображены в табл.
7д.10.

Стадия I. Построение транспортной матрицы

332
Транспортная матрица для нашего примера изображена на рис. 7д.5.
В крайнем правом столбце отображаются объемы поставок каждой фабрики, а в
нижней строке — потребности каждого склада. Затраты на транспортировку единицы
продукции указаны в маленьких прямоугольниках в каждой ячейке. На этом этапе важно
убедиться, что общие объемы поставок совпадают с общими потребностями. В нашем
примере оба этих показателя равны 46 единицам, однако нередки ситуации, когда один из
них превышает другой. В таких случаях для того, чтобы применить транспортный метод,
в задачу включают фиктивный склад или фабрику. Эта процедура заключается во вставке
дополнительной строки (для добавления фабрики) или еще одного столбца (для
добавления склада). Объем поставок или потребности дополнительного фиктивного
склада или фабрики — это разница между суммарными показателями строк и столбцов.
Так, например, изменим условия рассматриваемой нами задачи и укажем общую
потребность в продукции в размере 36 единиц. В этом случае нам придется добавить в
таблицу новый столбец, в котором указывается потребность фиктивного склада в размере
10 единиц, что в результате даст необходимые 46 наборов. Показатели затрат в каждой
ячейке фиктивной строки будут в этом случае нулевыми, т.е. отправленные сюда единицы
не дают никаких издержек на транспортировку. Теоретически данная корректировка
является эквивалентом симплексной процедуры вставки в неравенства ограничений
свободной переменной с тем, чтобы преобразовать его в уравнение, и, так же как при
симплексном методе, затраты фиктивного подразделения представляются в целевой
функции с нулевым значением.
Данную задачу также можно решить с помощью компьютерной программы
Microsoft Excel. На рис. 7д.6 показано, как нужно поставить задачу в MS Excel. Строки
1—6 используются для указания затрат, поставок фабрик и потребностей складов.
Решение (Changing cells, Изменяемые ячейки) выводится в диапазоне ячеек В8—Е11.
Затраты вычисляются в строках 15—19. Общие затраты указаны в ячейке F19. В
следующем разделе мы продолжим описание способа решения данной задачи без
применения компьютерной техники.

Стадия II. Исходное распределение

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




Рис. 7д.5. Транспортная матрица для задачи транспортировки шахматных наборов


Таблица 7д.10. Данные для задачи транспортировки шахматных наборов

333
Затраты на транспортировку единицы продукции (в долл.)
Объем На склад На склад На склад На склад
Фабрика Склад Потребность С фабрики
поставок Е F G Н
А 15 E 10 А 25 35 36 60
В 6 F" 12 В 55 30 45 38
С 14 G 15 С 40 50 26 65
D 11 Н 9 D 60 40 66 27




Рис. 7д. 6. Решение транспортной задачи с помощью программы MS Excel

Распределение методом северо-западной ячейки

Метод северо-западной ячейки, как следует из его названия, состоит в том, что
распределение начинается с верхнего левого угла матрицы и в ячейках первой строки
указываются как можно большие значения4. Затем данная процедура повторяется для
второй, третьей строки и т.д., пока все потребности не будут распределены по строкам и
столбцам. На рис. 7д.7 показан пример такого распределения. (Первой заполняется ячейка
с координатами А-Е, второй — A-F, третьей — B-F и т.д.)
4
В каждой ячейке указывается наибольшее возможное количество единиц. В результате не должно
получиться более чем т + п-\ заполненных ячеек, где т — количество строк, n — количество столбцов.

334
Анализируя распределение потребностей на рис. 7д.7, можно увидеть, что при
использовании этого метода некоторые ячейки с высокими издержками оказываются
заполненными, а другие ячейки с низкими затратами остаются пустыми. Этого и
следовало ожидать, поскольку данный метод не учитывает издержки транспортировки, в
результате чего и упрощается алгоритм распределения.

Распределение методом наименьших затрат

В соответствии с данным методом как можно большее значение проставляется в
ячейке с наименьшими затратами. Связи при этом могут нарушаться произвольно. Строки
и столбцы, распределенные полностью, во внимание не принимаются, и процесс
распределения продолжается. Заканчивается данная процедура после того, как все
потребности будут распределены по строкам и столбцам. Распределение по данному
методу иллюстрируется на рис. 7д.8. (Первыми указываются значения в ячейке с
координатами А-Е, затем в C-G, далее в D-H, в В-F и т.д.)

Распределение методом приближений Фогеля

Метод приближений Фогеля (Vogel's Approximation Method — VAM) также основан
на распределении потребностей с учетом затрат на транспортировку. Процесс
распределения осуществляется в пять следующих этапов.
Этап 1. В каждой строке и в каждом столбце, включая фиктивные, определите
разницу между двумя наименьшими значениями затрат на транспортировку в ячейках
каждой строки и каждого столбца.
Этап 2. Определите столбец или строку с наибольшей разницей.
Этап 3. Вставьте наибольшее возможное значение единиц в ячейке с наименьшими
затратами в строке или столбце с самой большой разницей, выбранной на этапе 2.
Этап 4. Прекратите процесс, если удовлетворены все потребности строк и столбцов.
В противном случае переходите к следующему этапу.
Этап 5. Пересчитайте разницу между оставшимися незаполненными двумя ячейками
с наименьшими затратами в каждой строке и в каждом столбце. При вычислении
дальнейшей разницы не следует учитывать строки и столбцы с нулевыми показателями
потребности или поставок. Вернитесь к этапу 2.
Метод приближений Фогеля обычно позволяет получить оптимальное или близкое к
оптимальному исходное решение. Одно из исследований показало, что данный метод дает
оптимальное решение для 80% задач. (Наши студенты утверждают, что остальные 20% —
это как раз те задачи, которые попадаются им на экзаменах.) На рис. 7д.9
проиллюстрировано применение метода Фогеля для решения рассматриваемой нами
задачи. (Первыми указаны значения в ячейке А-Е, затем в C-G, далее в D-H, в D-F И Т.Д.)
Обратите внимание, что это исходное решение совпадает с оптимальным, которое
получено в результате всех возможных улучшений исходного размещения, выполненного
методом верхней левой ячейки (сравните дальше с рис. 7д.12).

Стадия III. Получение оптимального решения

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


335
Метод последовательных шагов

Одним из распространенных методов оценки ячеек является метод
последовательных шагов, или метод "подводных камней". Это название появилось в
первых описаниях метода, в которых незаполненные ячейки сравнивались с водой, а
заполненные — с камнями, по аналогии с переходом через ручей с камня на камень. Мы
применим этот метод к поиску решения для исходного размещения, выполненного
методом северо-западной ячейки и приведенного для нашей задачи на рис. 7д,8.
Этап 1. Выберите любую пустую ячейку и укажите замкнутый путь, ведущий к ней.
Этот путь состоит из горизонтальных и вертикальных линий, которые ведут от пус той
ячейки через другие обратно к ней же5. В замкнутом пути может быть только одна пустая
ячейка, которую мы и рассматриваем. Повороты пути на 90° могут производиться только
в ближайших (к пустой) заполненных ячейках. На рис. 7д. 10 показаны два замкнутых
пути. Замкнутый путь а необходим для оценки пустой ячейки В-Е; замкнутый путь b
нужен для оценки пустой ячейки А-Н.
5
Если распределение было сделано правильно, в матрице содержится только один замкнутый путь для
каждой ячейки.




Общие затраты = 10($25) + 5($35) + 6($30) + 1($50) + 13(526) + 2($66) + 9($27) = $1,368

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




Общие затраты = 10($25) + 14($26) + 9(S27) + 6($30) + 5($35) + 1($40) + 1 ($66) = $1,318

Рис. 7д.8. Распределение методом наименьших затрат




336
Total cost = 10($25) + 14($26) + 9($27) + 2($40) + 1($36) + 4($35) + 6($30) = $1,293
Рис. 7д. 9. Распределение методом приближений Фогеля
Этап 2. Переместите одну единицу из заполненной ячейки в угле замкнутого пути в
пустую ячейку и измените оставшиеся заполненные ячейки в других углах в соответствии
с выполненным перемещением6. Изменение заключается в добавлении и вычитании
единиц из заполненных ячеек способом, при котором не нарушаются указанные общие
ограничения в отношении поставок и потребностей. Для этого необходимо, чтобы из
каждой строки или столбца, в ячейки которых была добавлена или вычтена единица,
обязательно вычиталась или добавлялась одна единица, но из других ячеек, лежащих на
пути. Таким образом, для пути а потребуются следующие добавления и вычитания.
6
Для проверки возможности перемещения можно добавить не одну, а больше единиц. Однако, поскольку
рассматриваемая нами задача носит линейный характер, если возможно смещение на одну единицу, то будет
возможным смещение и на большее число единиц, и наоборот.

Прибавьте одну единицу в ячейке В-Е (пустая ячейка).
Вычтите одну единицу из ячейки B-F.
Прибавьте одну единицу в ячейке A-F.
Вычтите одну единицу из ячейки А-Е.
Для более длинного пути b потребуется следующее.
Прибавьте одну единицу в ячейке А-Н (пустая ячейка).
Вычтите одну единицу из ячейки D-H. Прибавьте одну единицу в ячейке D-G.
Вычтите одну единицу из ячейки C-G. Прибавьте одну единицу в ячейке C-F. Вычтите
одну единицу из ячейки A-F.
Этап 3. Определите, желательно ли данное перемещение. Это легко выполняется с
помощью
• суммирования значений затрат в ячейке, к которой была добавлена единица;
• суммирования значений затрат в ячейке, из которой была вычтена единица;
• получения разницы между этими двумя суммами, благодаря чему можно
определить, сократились ли как-нибудь затраты.
Если затраты в результате перемещений сократились, следует переместить как
можно больше единиц из оцененной заполненной ячейки в пустую. Если же затраты
повысились, никаких перемещений делать не стоит, а пустую ячейку надо перечеркнуть
или пометить каким-либо иным способом, чтобы показать, что ее уже оценивали.
(Обычно для обозначения ячейки, которая прошла оценку в ходе решения задач
минимизации затрат и была признана нежелательной для перемещения, пользуются
большим знаком "плюс". В этих же случаях при решении задач максимизации прибыли
используют большой знак "минус".) Для ячейки В-Е такие плюсы и минусы будут

337
расположены следующим образом:

+ -
$55 (В-Е) $30 (B-F)
35 (A-F) 25 (A-F)
$90 $55

Для ячейки A-F эти знаки будут расставлены так:

-
+
$60(А-Н) $27(D-H)
66 (D-G) 26 (C-G)
50 (C-F) 35 (A-F)
$176 $88

Таким образом, в обоих случаях очевидно, что перемещений в любую пустую ячейку
делать не следует, так как получаемые разности положительны.
Этап 4. Повторяйте этапы 1—3 до тех пор, пока не будут оценены все пустые
ячейки. Чтобы проиллюстрировать технику выполнения перемещения, рассмотрите
ячейку D-F и короткий замкнутый путь, ведущий к ней: C-F, C-G и D-G Плюсы и минусы
в данном случае будут расставлены следующим образом:

+ -
$40 (D-F) $50 (C-F)
26 (C-G) 66 (D-G)
$66 $116

Поскольку в данном случае вы имеем экономию в размере 50 долл. при доставке по
пути D-F, в эту ячейку следует переместить как можно больше единиц. При этом, однако,
в данном конкретном случае максимально можно переместить только одну единицу,
поскольку максимальное количество единиц, которое можно добавить к
любой ячейке, не должно превышать число, указанное в ячейке с наименьшим
значением, из которого будет проводиться вычитание. Невыполнение этого правила
приведет к нарушению ограничений относительно поставок и потребностей задачи. В
нашем случае очевидно, что ограничивающей ячейкой является C-F, поскольку она
содержит всего одну единицу.
Измененная матрица, отображающая эффект данного перемещения и описанных
выше оценок, изображена на рис. 7д.11.
В результате применения метода последовательных шагов к остальным
незаполненным ячейкам и выполнения указанных перемещений мы приходим к
оптимальному решению.
В частности, незаполненная ячейка A-G на рис. 7д.11 имеет замкнутый путь D-G, D-
F и A-F. Плюсы и минусы будут расставлены так:

+
$36 (A-G) $35 (A-F)
40 (D-F) 66 (D-G)
$76 $101

Поскольку имеется экономия, равная 101 — 76 = 25 долл., мы перемещаем одну

338
единицу в ячейку A-G. На рис. 7д.12 изображена оптимальная матрица для минимальных
транспортных затрат в размере 1293 долл.
Чтобы удостовериться, что полученное распределение действительно является
оптимальным, нам вновь следует оценить каждую пустую ячейку и рассмотреть, желатель
но ли перемещение в нее. Если в каждой из проверенных ячеек окажется знак "плюс", то
задача решена и распределение оптимально.




Рис. 7д. 10. Метод последовательных шагов — определение замкнутого пути




Рис. 7d.11. Измененная транспортная матрица




Рис. 7д. 12. Оптимальное решение транспортной задачи




339
Рис. 7д. 13. Транспортная задача с явлением вырождения

Вырождение

Явление вырождения (Degeneracy) возникает в транспортных задачах, когда
количество заполненных ячеек меньше суммы количества строк и столбцов минус 1 (т.е.
т + п — 1). Вырождение может наблюдаться во время исходного распределения, когда
первое значение в строке или столбце удовлетворяет ограничениям как по строке, так и
по столбцу. Для оценки полученного решения в матрице необходимо определенным
образом скорректировать вырождение. Такая корректировка заключается во вставке
некоторого количества единиц ? в пустые ячейки так, чтобы можно было составить
замкнутый путь для оценки других пустых ячеек. Значение ? может быть бесконечно
малым числом и не оказывать влияния на решение. При этом обычная процедура
предусматривает, что некое значение ? используется точно так же, как реальное число, но
может быть размешено в любую пустую ячейку без соблюдения требований к
ограничениям по строкам и столбцам.
Оптимальное по минимальным затратам на транспортировку решение транспортной
задачи с явлением вырождения показано на рис. 7д.13. На этом рисунке видно, что, если
бы в матрицу не было включено значение ?, некоторые из ячеек оценить было бы
невозможно (включая ту, к которой это значение было добавлено).
После того, как в вводится в решение, это значение остается в нем до тех пор, пока
либо оно не исчезнет при вычитании, либо до получения окончательного решения.
Выбор ячейки, в которую следует вводить ?, принимается произвольно, но можно
сэкономить немало времени, если вставить это значение в ту ячейку, в которой его можно
использовать для оценки как можно большего количества ячеек, не перемещая его. Вы
можете убедиться, что на рис. 7д.13 значение в расположено именно в таком наиболее
выгодном месте.

Альтернативные оптимальные решения

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



Резюме

Данное дополнение было в основном посвящено различным процедурам решения

340
задач линейного программирования. Задачи такого типа, решаемые без применения
вычислительной техники, встречаются крайне редко. Кроме того, сегодня в нашем
распоряжении столько компьютеров и компьютерных программ, что решение их
"вручную" было бы просто неоправданной тратой времени8.
8
Существуют также программы, помогающие строить сами модели линейного программирования. Самая
известная из них, по всей вероятности, GAMS— General Aigebraic Modeling System (GAMS — General, San
Francisco, CA).


Задачи с решениями
Задача 1

В ходе производства два вида продукции X и Y проходят обработку на станках I и II.
У станка I есть 200 часов доступного времени, а у станка II — 400. Для обработки одной
единицы продукции X необходим один час работы на станке I и четыре часа на станке II.
Обработка продукции Y требует одного часа на станке I и одного — на станке II. Единица
продукции X дает прибыль в размере 10 долл., а единица продукции Y — 5 долл. Все эти
условия выражаются следующими уравнениями:
Х+ Y< 200 (станок I).
4Х+ Y<400 (станок II).
Максимизировать $10Х + $5Y.
Решите графическим методом задачу определения оптимального использования

<<

стр. 11
(всего 31)

СОДЕРЖАНИЕ

>>