«И.Н. Мастяева Г.Я. Горбовцов О.Н. Семенихина ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ Москва, 2003 УДК 519.6 ББК 22.18 М 327 И.Н. Мастяева, Г.Я. Горбовцов, О.Н. Семенихина. ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ: Учебное пособие / ...»

Московский международный институт эконометрики,

информатики, финансов и права

И.Н. Мастяева

Г.Я. Горбовцов

О.Н. Семенихина

ИССЛЕДОВАНИЕ

ОПЕРАЦИЙ В ЭКОНОМИКЕ

Москва, 2003

УДК 519.6

ББК 22.18

М 327

И.Н. Мастяева, Г.Я. Горбовцов, О.Н. Семенихина.

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ: Учебное пособие / Московский международный институт эконометрики, информатики, финансов и права. М., 2003. с.113 Рекомендовано Учебно-методическим объединением по образованию в области статистики в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 061700 «Статистика» и другим экономическим специальностям.

© И.Н. Мастяева, © Г.Я. Горбовцов, © О.Н. Семенихина, © Московский международный институт эконометрики, информатики, финансов и права, 2003.

Содержание Программа курса «Исследование операций в экономике»

1. Моделирование в экономике

2. Теория двойственности в линейном программировании.

Двойственный симплекс- метод.

2.1. Определение и экономический смысл двойственной ЗЛП......... 2.2. Основные положения теории двойственности

2.3. Анализ решения ЗЛП с помощью теории двойственности........... 2.4. Анализ решения ЗЛП на основе отчётов MS EXCEL

2.5. Двойственный симплекс-метод (Р-метод)

3. Целочисленные модели исследования операций

3.1. Метод ветвей и границ решения целочисленных задач линейного программирования (ЦЗЛП)

3.2. Задача коммивояжера

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

Методы составления первоначальных опорных планов

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

Венгерский алгоритм

5. Нелинейные модели.

5.1. Методы одномерной оптимизации.

5.2. Методы безусловной оптимизации

5.3. Методы условной оптимизации

6. Литература

Программа курса «Исследование операций в экономике»

Тема 1. Моделирование в экономике. Определение экономикоматематической модели, ее свойства. Классификация моделей по различным признакам.

Тема 2. Теория двойственности в линейном программировании. Двойственный симплекс-метод. Определение и правила построения двойственных задач, их экономический смысл. Теоремы двойственности. Различные способы отыскания решения двойственной задачи по решению прямой. Экономический анализ линейных моделей на основе теории двойственности. Двойственный симплекс-метод. Рматрица, псевдоплан, условия перехода от одного псевдоплана к другому. Алгоритм двойственного симплекс-метода.

Тема 3. Целочисленные модели исследования операций.

Примеры задач целочисленного линейного программирования. Метод ветвей и границ решения задачи целочисленного линейного программирования: идея и алгоритм. Постановка задачи коммивояжера.

Применение метода ветвей и границ для решения задачи коммивояжера.

Тема 4. Экономические задачи, сводящиеся к транспортным моделям. Транспортная задача (ТЗ) линейного программирования.

Математическая модель. Закрытая и открытая модели ТЗ. Опорный план ТЗ. Методы построения первоначальных опорных планов. Метод потенциалов решения ТЗ, его обоснование и алгоритм. ТЗ с запрещенными перевозками. Задача оптимального распределения оборудования. Формирование оптимального штата фирмы. Задача календарного планирования. Задача о назначениях, венгерский метод ее решения. Оптимальное исследование рынка. Оптимальное использование рабочих агентов.

Тема 5. Нелинейные модели исследования операций. Постановка задачи нелинейного программирования (ЗНП). Одномерная оптимизация. Алгоритм Свенна поиска отрезка, содержащего точку максимума. Метод золотого сечения решения задачи одномерной оптимизации. Безусловная оптимизация. Метод скорейшего подъема (спуска). Условная оптимизация. Метод Зойтендейка.

В общем виде модель можно определить как условный образ (упрощенное изображение) реального объекта (процесса), который создается для более глубокого изучения действительности. Метод исследования, базирующийся на разработке и использовании моделей, называется моделированием. Необходимость моделирования обусловлена сложностью, а порой и невозможностью прямого изучения реального объекта (процесса). Значительно доступнее создавать и изучать прообразы реальных объектов (процессов), т.е. модели.

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

По степени агрегирования объектов моделирования различают модели:

- микроэкономические;

- одно-, двухсекторные (одно-, двухпродуктовые);

- многосекторные (многопродуктовые);

- макроэкономические;

- глобальные.

По учету фактора времени различают модели:

- статические;

- динамические.

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

По цели создания и применения различают модели:

- балансовые;

- эконометрические;

- оптимизационные;

- сетевые;

- систем массового обслуживания;

- имитационные (экспертные).

В балансовых моделях отражается требование соответствия наличия ресурсов и их использования.

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

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

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

Модели систем массового обслуживания создаются для минимизации затрат времени на ожидание в очереди и времени простоев каналов обслуживания.

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

По учету фактора неопределенности различают модели:

- детерминированные (с однозначно определенными результатами);

- стохастические (с различными вероятностными результатами).

По типу математического аппарата различают модели:

- линейного и нелинейного программирования;

- корреляционно-регрессионные;

- матричные;

- сетевые;

- теории игр;

- теории массового обслуживания и т.д.

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

Максимальный объем Требуется выбрать совокупность проектов, которой соответствует максимум суммарной прибыли.

2. Совет директоров фирмы изучает предложения по наращиванию производственных мощностей на трех принадлежащих фирме предприятиях. Для расширения всех трех предприятий фирма выделяет средства в объеме 5 млн. руб. Каждое предприятие представляет на рассмотрение проекты, которые характеризуются величинами суммарных затрат (C) и доходов (R), связанных с реализацией каждого из проектов. Соответствующие данные приведены в таблице, в которую включены также проекты с нулевыми затратами. Это позволяет учесть возможность отказаться от расширения какого-либо предприятия.

Проект Предприятие 1 Предприятие 2 Предприятие инвестиций.

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

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

Материальные Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех.

4. Некоторая фирма переводит свой главный завод на производство определенного вида изделий, которые будут выпускаться в течение четырех месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет 1) избытка произведенных в прошлом месяце изделий, сохраняющихся для реализации в будущем;

2) производства изделий в течение текущего месяца;

3) избытка производства изделий в более поздние месяцы в счет невыполненных заказов.

Затраты на одно изделие в каждый месяц составляют 4 долл. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 долл. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом 2 долл. в месяц. Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий.

В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

5. Известен рыночный спрос на определенное изделие в количестве 180 штук. Это изделие может быть изготовлено двумя предприятиями по различным технологиям. При производстве x1 изделий первым предприятием его затраты составят (4x1 + x12) руб., а при изготовлении x2 изделий вторым предприятием они составят (8x2 + x22) руб.

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

6. На двух предприятиях холдинга необходимо изготовить изделий некоторой продукции. Затраты, связанные с производством x изделий на первом предприятии, равны 4x12 руб., а затраты, обусловленные изготовлением x2 изделий на втором предприятии, составляют (20x2 + 6x22) руб.

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

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

8. Имеется в наличии b = 5 единиц одного ресурса, который в начале планового периода необходимо распределить между тремя предприятиями. Известны аk – количество единиц ресурса, идущего на изготовление единицы продукции k-м предприятием (k = 1,2,3), а2=а3=1, а1=2 и gk(yk) – доход от выпуска yk единиц продукции k-м предприятием.

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

9. Требуется разместить n производственных агрегатов на n различных производственных участках. Количество материалов, транспортируемых между агрегатами i и j, равно dij; удельные затраты на транспортировку материалов с участка p на участок q составляют cqp.

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

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

Сформулировать задачу целочисленного программирования.

2. Теория двойственности в линейном программировании.

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

2.1. Определение и экономический смысл двойственной ЗЛП.

Пусть прямая задача записана в каноническом виде:

Задачей, двойственной к ЗЛП (2.1)-(2.3), называется следующая ЗЛП Из приведенного определения следует, что двойственная ЗЛП строится по следующим правилам:

1) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи ( y 1, ..., y m ) равно числу ограничений прямой задачи.

2) Каждой переменной прямой задачи соответствует ограничение двойственной задачи, т.е. число ограничений двойственной задачи равно числу переменных прямой задачи.

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

4) Вектор C целевой функции прямой задачи становится вектором правой части ограничений двойственной задачи, а вектор b правой части прямой задачи - вектором целевой функции двойственной задачи.

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

Пример 2.1 Пусть прямая задача записана в виде основной ЗЛП:

Приведем задачу (2.9) к канонической форме:

Тогда двойственная задача (ДЗ) будет иметь вид:

Пример 2.2.

Прямая задача в каноническом виде Двойственная задача Ограничение y1 + 0 y2 0, т.е. y1 0 является более жестким, чем условие неограниченности у1 в знаке, поэтому двойственная задача может быть записана в следующем виде:

Отбрасывая избыточные ограничения, получаем:

Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У2 и У3 можно отбросить. Окончательно получаем:

Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

2.2. Основные положения теории двойственности двойственной ЗЛП, тогда двойственной ЗЛП и f ( x ) = g ( y ), тогда x, y - решения соответственно прямой и двойственной задач.

Теорема 3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

Теорема 4. Планы x, y соответственно прямой и двойственной ЗЛП являются оптимальными тогда и только тогда, когда Условия (2.14) называются условиями дополнительной нежесткости.

Замечание 1. Для основной ЗЛП и двойственной к ней ЗЛП условия нежесткости имеют вид:

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

Получение оптимального плана двойственной задачи на Пример 2.5. Рассмотрим задачу:

Ее решение x = (3 / 2; 0), minf ( x ) = 3. Найдем решение задачи, двойственной к (2.17), используя теорему 4. Запишем двойственную к (2.17) задачу:

Применяем соотношение (2.16). Так как х1*=3/2 > 0, то 3у1*+4у2*+у3*=2. Далее, так как 3х1*+х2*=9/2+0 > 3, то у1*=0, и так как х1*+2х2*=3/2+0 < 3, то у3*=0. Итак, имеем:

т.е. вектор y = (0; 1/ 2; 0) является решением задачи (2.18) на соответствует утверждению теоремы 3.

Пример 2.6. Найти решение прямой и двойственной задачи.

решать графически (рис.2.1) Как видно из рис.2.1, область допустимых решений - планов двойственной ЗЛП - Q представляет собой отрезок АВ, лежащий на прямой Y1 +2 Y2 = 5, так как первое ограничение задается в виде равенства. Передвигая линию уровня функции 10 Y1 +8 Y2 = const в направлении, противоположном вектору b =(10,8), получаем точку А, в которой достигается минимум функции g ( y ). Находим координаты точки А, которая является пересечением двух прямых:

Ипользуя теорему 4, находим решение исходной задачи. Так как Y >0 и Y 2 4), то X 3 =0. Решая систему (2.19), получаем:

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

Пусть прямая задача имеет вид основной ЗЛП Двойственная к ней ЗЛП имеет вид Предположим, что ЗЛП (2.20) имеет решение. Решения обеих задач могут быть записаны в виде :

матрица, обратная для базисной подматрицы BS. Матрица BS1 подматрица K (S ) - расположена на месте единичной подматрицы в исходной матрице K ( 0). Кроме того, можно показать, что откуда следует, что i -я компонента y i решения двойственной ЗЛП есть (n + i)-я симплекс-разность матрицы K (S ), определяющей оптимальный план исходной ЗЛП, а j-я симплекс-разность матрицы K (S ) ( j = 1, n ) равна разности между левой и правой частью ограничений двойственной ЗЛП:

Пример 2.7. Решить следующую ЗЛП:

Найти решение задачи двойственной к ЗЛП (2.24).

Так как расширенная матрица системы линейных уравнений (2.24) является К-матрицей, то ЗЛП (2.24) можно решить симплекс-методом. Результаты решения приведены в таблице.

На первой итерации получен оптимальный план ЗЛП (2.24).

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

Находим решение ЗЛП (2.25) по формуле или (2.22):

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

Виды анализа, выполняемого на основе математической модели, приведены на рис. 2.2.

Поясним некоторые вопросы. На этапе постановки задачи производится анализ с целью ответить на вопросы: «Что будет, если…?»

и (или) «Что надо, …, чтобы …?». Анализ с целью ответа на первый вопрос называется вариантным анализом, на второй – решениями по заказу.

Вариантный анализ бывает следующих видов:

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

Под структурным анализом будем понимать решение задачи оптимизации при различной структуре ограничений;

Многокритериальный анализ – это решение задачи по разным целевым функциям;

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

Во вторую группу – решения по заказу – входят задачи, целью которых является решение задачи оптимизации при заданных значениях:

переменных, левых частей ограничений, целевой функции.

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

Пример 2.8. Фабрика выпускает продукцию двух видов: П1 и П.Продукция обоих видов поступает в оптовую продажу. Для производства этой продукции используются три исходных продукта – А, В, С. максимально возможные суточные запасы этих продуктов составляют 6, 8 и 5 т соответственно. Расходы продуктов (сырья) А, В, С на 1 тыс. изделий П1 и П2 приведены в таблице.

Исходный Расход исходных продуктов Максимально Изучение рынка сбыта показало, что суточный спрос на изделия П2 не превышает спроса на изделия П1 более чем на 1 тыс. шт. Кроме того, установлено, что спрос на изделия П2 не превышает 2 тыс. шт. в сутки.

Оптовая цена 1 тыс.шт. изделий П1 равна 3 тыс. руб., 1 тыс. шт. П - 2 тыс. руб. Какое количество изделий (в тыс. шт.) должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Математическая модель этой задачи (в канонической форме) f (x) = 3Х1 +2 Х2 +0 S1 +0 S2 +0 S3 +0 S4 +0 S5 max Исходная и оптимальная симплекс-таблицы решения задачи Двойственная к ней имеет вид Оптимальными планами этих задач являются соответственно векторы На основании второй теоремы двойственности Из этой формулы следует, что двойственная переменная yi является коэффициентом при bi и, значит, показывает, как изменится целевая функция при изменении i -го продукта (ресурса) на 1. В литературе двойственные переменные принято называть двойственными оценками или теневыми ценами.

Анализируя вектор Y, придем к таким выводам. При увеличении запаса продукта А на 1т доход от реализации продукции увеличится на 1/3 тысяч рублей, а при увеличении запаса продукции В на 1 т доход увеличится на 4/3 тысячи рублей. Изменение же запаса С или изменение в соотношениях спроса не приводят к изменению дохода. Продукты А и В при этом являются дефицитными, а продукт С - не дефицитным.

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

S3* = 3/5 т (резерв для продукта С); S4* = 3 т (резерв в разности спроса) и S5* = 2/3 т (резерв спроса на продукцию П2). Очевидно, что если бы запас продукта С был бы равен не 5, а 6 т, то резерв был бы равен не 3, а 4 т. при этом не произошло бы увеличения значения целевой функции.

Следовательно, для третьего ограничения исходной задачи соответствующая двойственная переменная У3* = 0. Аналогично, У4* = 0, У5* = 0, что и подтверждается вектором Y.

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

переменных. В нашей задаче обе основных переменных Х1* и Х2* вошли в оптимальный план, поэтому дополнительные переменные У6* и У7* равны нулю. Это следует из теоремы IV (о дополнительной нежесткости). Если бы какая-то из основных переменных исходной задачи оказалась равной нулю (данная продукция нерентабельна), то положительное значение соответствующей дополнительной переменной двойственной задачи указало бы, насколько уменьшится целевая функция при принудительном выпуске единицы данной продукции.

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

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

Полученный план X останется оптимальным при условии ( j2) 0; j = 1,7, то есть Решая эту систему неравенств, получим, что Это условие определяет пределы изменения С1, при которых сохраняется структура оптимального плана. Если от пределов изменения приращения С1 перейти к пределам изменения самой величины С1, то получим Таким образом, при изменении С1 в пределах будет по-прежнему выгодно выпускать продукцию П1. При этом значение целевой функции будет Если выполнить аналогичные преобразования с С2, то получим - пределы изменения С2, при которых будет выгодно выпускать продукцию П2. Полученные пределы изменения Сj – это, кроме того, пределы справедливости дополнительных двойственных оценок.

Рассмотрим влияние на полученное решение изменения запасов продуктов (ресурсов). Пусть запас исходного продукта А равен (6 + А). Вектор свободных членов b = X N имеет вид: (0) Тогда в последней симплекс-таблице (см. на преобразование вектора a 3 ) вектор свободных членов примет вид Решение X N = b будет допустимым, если все элементы вектора Перейдя к пределам изменения А, получим Найденные пределы показывают границы, в которых может изменяться запас продукта А, чтобы номенклатура выпускаемой продукции (структура оптимального плана) осталась без изменений. А это означает, что при изменении запаса продукта А в найденных пределах оптимальным, то есть обеспечивающим наибольшую прибыль, является выпуск и продукции П1, и продукции П2, только в других количествах. Продукции П1 необходимо будет выпускать в количестве продукции П2 – в количестве при этом доход будет Следовательно, если увеличить запас продукта А на 1 т ( А = 1), то для обеспечения максимизации прибыли выпуск продукции П целесообразно уменьшить до X 1 = 3 тонн, а выпуск продукции П2 – увеличить до X 2 = 13 тонн. Доход от реализации продукции станет равным Полученные пределы изменения правых частей уравнений исходной задачи это и есть пределы справедливости двойственных оценок.

2.4. Анализ решения ЗЛП на основе отчётов MS EXCEL Рассмотрим следующую ЗЛП:

Начнём с отчёта результатов. Приведём его вид:

Единственное, что здесь следует прокомментировать, это статус ресурсов. Т.к. все ограничения на ресурсы являются связанными, то это говорит о том, что все ресурсы были использованы. Другими словами, все ресурсы являются дефицитными.

Рассмотрим отчёт по устойчивости:

Нормированная стоимость (часто, редуцированная стоимость, от английского: cost reduction – уменьшение затрат) представляет собой дополнительные двойственные переменные. Они показывают, насколько по модулю уменьшится целевая функция при принудительном выпуске единицы данной продукции. В нашем примере нормированная стоимость по продукту А не равна нулю. Следовательно, если мы будем принудительно выпускать единицу продукта А, то целевая функция уменьшится на 0,062. Другими словами, выпуск продукта А является нерентабельным (неприбыльным).

Допустимое увеличение показывает, насколько максимально можно увеличить коэффициент целевой функции (цену продукта), чтобы структура оптимального плана осталась прежней. Допустимое уменьшение, наоборот, показывает, насколько можно максимально уменьшить коэффициент ЦФ, чтобы осталась прежней структура оптимального плана. Например, в нашей задаче, чтобы выпуск продукта А оставался нерентабельным, максимально допустимое увеличение его цены составляет приблизительно 0.06. Допустимое же уменьшение представляет собой огромное число. Это понятно, т.к., ещё больше уменьшив цену нерентабельного продукта, сделать его рентабельным невозможно.

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

Например, если мы увеличим запас ресурса I на единицу, то ЦФ возрастёт на 2,628 (ресурс I является самым приоритетным). Допустимое увеличение и уменьшение показывают границы, в которых могут изменяться ресурсы, чтобы структура оптимального решения, т.е.

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

Рассмотрим последний отчёт – отчёт по пределам:

В отчёте указаны значения ЦФ при выпуске данного типа продукции на нижнем и верхнем пределах. Так, значение ЦФ 6971, соответствует тому, что продукт С не выпускается.

Отчёты Excel обеспечивают всей необходимой информацией для проведения полного анализа линейной модели.

Решить с помощью MS Excel следующие задачи (варианты 1-5, 6Для приготовления четырех видов продукции (A, B, C, D) используют три вида сырья. Ресурсы сырья, норма его расхода на единицу продукции и цена продукции заданы в соответствующей таблице.

Определите план выпуска продукции из условия максимизации его стоимости.

Определите статус, ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.

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

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

Производство какой продукции нерентабельно?

На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

На сколько можно снизить запас каждого из ресурсов, чтобы это не привело к уменьшению прибыли?

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

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

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

продукции, чтобы сделать На сколько нужно снизить затраты каждого вида сырья на единицу производство нерентабельного изделия рентабельным?

На сколько нужно изменить запас каждого из дефицитных ресурсов, чтобы прибыль возросла на 20%?

Z=500, в =(2000,1500,2000) Z=300, в в =(1500,2000, 2000) Z=700, c =(2000,2880,1500) Z=450, в =(2000,1500,700) Z=500, в =(1000,2500,500) 6-10.Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в2 ед. вещества В и в3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.

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

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

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

Содержание какого из питательных веществ превышает заданный минимальный уровень и на сколько?

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

На сколько уменьшится стоимость рациона и используемое количество кормов при снижении минимального уровня потребления питательного вещества В до Z ед.

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

Возможно ли сделать выгодным использование корма, не вошедшего в рацион.

На сколько увеличится стоимость рациона при принудительном включении в рацион 1 кг нерентабельного вида корма.

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

B =(400,180,200); Z= B =(400,180,200); Z= (руб) B =(400,180,200); Z= (руб) B =(400,180,200); Z= 10.

(руб) B =(400,180,200); Z= Пример 2.9. Рассмотрим следующую ЗЛП:

Приведем рассматриваемую ЗЛП к каноническому виду Рассмотрим расширенную матрицу системы линейных уравнений (2.29):

Матрица P ( 0) содержит единичную подматрицу порядка 3 и, следовательно, определяет базисное решение системы уравнений, причем C N =( 0,0,0). Так как элементы ( n + = 6 )-го столбца матрицы системы P ( 0) не являются неотрицательными, то она не является К-матрицей ЗЛП. Вычислим симплекс-разности матрицы P ( 0) :

Так как все симплекс-разности матрицы P ( 0) являются неотрицательными, то базисное решение X N = (-3; -6; 3) не (0) являющееся планом ЗЛП, является «лучшим», чем оптимальный план.

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

Определение. Р-матрицей КЗЛП будем называть расширенную матрицу системы линейных уравнений, равносильной исходной системе, содержащую единичную подматрицу порядка m на месте n первых столбцов, все симплекс разности которой неотрицательны.

Очевидно, что всякая Р-матрица ЗЛП определяет некоторое базисное решение системы уравнений (2.29) (см.пример 2.9) Определение. Базисное решение системы линейных уравнений (2.29), определяемое Р-матрицей, называется псевдопланом ЗЛП.

псевдоплан Условия перехода от матрицы P (S ) к матрице P ( S +1) составляют содержание теоремы 1.

Теорема 1. Пусть bl(S ) < 0 и в l -й строке матрицы P (S ) есть хотя бы один отрицательный элемент. Тогда одного шага метода ЖорданаГаусса можно построить новую Р-матрицу P ( S +1), выбрав направляющий элемент из условия Замечание 1. Если в матрице P нет bl( S ) < 0, то определяемый ею псевдоплан является решением ЗЛП.

Теорема 2. Пусть bl(S ) < 0 и в l-й строке матрицы P (S ) нет ни одного отрицательного элемента. Тогда множество планов Р ЗЛП (2.28) пусто.

Замечание 2. При переходе от матрицы P (S ) к матрице P ( S +1) целевая функция изменяется в соответствии с формулой откуда следует, что так как bl < 0 и alK < 0. Из неравенства (2.32) следует, что при переходе от одного псевдоплана к другому значение целевой функции f (x) не возрастает.

Будем считать, что известна исходная Р-матрица P ( 0) задачи линейного программирования, определяющая исходный псевдоплан В методе последовательного уточнения оценок последовательно строят Р-матрицы программирования, пока не получат Р-матрицу задачи линейного программирования, определяющую ее оптимальный план.

Рассмотрим алгоритм S-й итерации метода последовательного уточнения оценок. В начале S-й итерации имеем Р-матрицу P ( S 1) задачи линейного программирования, определяющую псевдоплан Шаг 1. Найдем номер l из условия то псевдоплан является оптимальным опорным планом, а есть оптимальное значение линейной формы f (x), иначе переходим к шагу 3.

то задача линейного программирования не имеет решения ( множество планов Р пусто), иначе переходим к шагу 4.

Шаг 4. Вычисляем для столбцов a j матрицы P ( S 1) ( j Ni( S 1), i = 1, 2, …,m) симплекс-разности ( jS 1) и находим номер К из условия Направляющий элемент на S-й итерации метода есть элемент alK 1).

Шаг 6. Производим один шаг метода Жордана-Гаусса с направляющим элементом alK 1). Вычисляем элементы Р-матрицы P (S ) методом Жордана-Гаусса. Присваиваем переменной алгоритма S значение S+1 и переходим к шагу 1.

Решим задачу из примера 2.9. Результаты решения приведены в симплекс-таблице.

Так как компоненты псевдоплана X N =( 3/2, 3/2, 3/2) являются неотрицательными, то X N является оптимальным опорным планом ЗЛП (2.28). Итак, Пример 2.10. Решим ЗЛП:

Приведем рассматриваемую ЗЛП к каноническому виду Расширенная матрица системы линейных уравнений (3.42) не являются Р-матрицей рассматриваемой ЗЛП, так как Следовательно, к решению ЗЛП (3.41) не применим Р-метод.

Пример 2.11.

Решение. Приведем задачу к каноническому виду Так как расширенная матрица системы линейных уравнений рассматриваемой задачи является Рматрицей ( (10) = 6 >0; (20) = 3 >0 ), то задачу можно решить Р-методом.

Решение задачи ведем в симплексной таблице.

Так как bl(1) = b1(1) = -4 < 0, а все a1(1j) 0, то множество планов ЗЛП (2.35) является пустым множеством.

Предприятию необходимо выпустить по плану продукции А1 - единиц, А2 - 300, А3 - 450. Каждый вид изделия может производиться на двух машинах. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Ресурс времени каждой машины приведен справа от таблицы. Записать модель исследуемой операции в форме, допускающей использование Р-метода.

3. Целочисленные модели исследования операций.

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

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

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

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

Методы решения задач целочисленного программирования можно классифицировать как (1) методы отсечений и (2) комбинаторные методы.

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

Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами.

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

3.1. Метод ветвей и границ решения целочисленных задач линейного программирования (ЦЗЛП) Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи с ослабленными ограничениями. При таком подходе из.

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

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

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

Согласно общей идее метода, сначала решается задача с ослабленными ограничениями (задача линейного программирования). Пусть хr — целочисленная переменная, значение xr* которой в оптимальном решении ослабленной задачи является дробным. Интервал не содержит допустимых целочисленных компонент решения.

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

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

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

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

Рассмотрим задачу целочисленного линейного программирования (ЗЦЛП ) :

Найти вектор x E n, максимизирующий линейную форму и удовлетворяющий условиям:

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

В начале любой S-й итерации метода ветвей и границ необходимо иметь:

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

2. Нижнюю границу оптимального значения линейной формы задачи (3.1) - (3.3), (3.5) Z0(s). На первой итерации в качестве Z0(1) можно взять значение функции f ( x) в любой целочисленной точке x, лежащей внутри области (3.2) - (3.5). Если такую точку указать трудно, то можно положить Z0(1) =, но это приводит к значительному увеличению числа итераций.

Алгоритм S-й итерации метода ветвей и границ.

Пусть в результате S итераций метода получили список из Z задач:

1,2,...,Z и имеем Z0(s).

Шаг 1. Выбираем из списка ЗЛП одну задачу для решения, задачу R (1 R Z) и решаем ее.

Шаг 2. Если задача R имеет решение x R ( s), то переходим к шагу 3. В противном случае - исключаем задачу R из списка и, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1. При S = 0, то есть на первой итерации, делаем вывод, что исходная задача (3.1)-(3.4) не имеет решения и процесс решения заканчивается.

Шаг 3. Если f ( x R ) > Z0(s), то переходим к шагу 4. В противном случае - задачу R исключаем из списка и, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1.

Шаг 4. Если не все компоненты вектора x R ( s) удовлетворяют условиям целочисленности (3.4), то переходим к шагу 5. В противном случае - задачу R из списка исключаем, план x R ( s) запоминаем и, полагая Z0(s+1)= f ( x R ( s ) ), возвращаемся к шагу 1. При S = 0 вектор x является решением и исходной задачи и процесс решения заканчивается.

Шаг 5. Задачу R выбрасываем из списка, включая в него две новые задачи линейного программирования - задачу (Z+1) и задачу (Z+2).

Далее, полагая Z0(s+1)=Z0(s), возвращаемся к шагу 1. Процесс разбиения задачи R на две новые ЗЛП осуществляется следующим образом: Пусть x j - дробная компонента в полученном оптимальном плане x R и [ x j ] ее целая часть. Тогда задача Z+1 имеет вид:

при условиях Процесс решения продолжаем до тех пор, пока не будут решены все задачи линейного программирования из списка. Тогда решением задачи (3.1)-(3.5) будет Z0(s) на последней итерации.

Пример. Решить ЗЦЛП В качестве Z0(1) возьмем f ( x) в точке x =(0,0), то есть Z0(1)=0.

Итерация 1. Имеем:

1) В списке задач линейного программирования одна задача задача 1 - (3.6)-(3.7),(3.9),(3.10).

2) Нижняя граница Z0(1)=0.

Шаг 1. Выбираем задачу 1, решаем ее, получим оптимальный план x =(1,5 ; 3,5), f ( x ) = 6,5.

Шаг 2. Так как задача 1 имеет конечное решение, то переходим к шагу 3.

Шаг 3. Так как f ( x ) = 6,5 > Z0(1), то переходим к шагу 4.

Шаг 4. Не все компоненты вектора x удовлетворяют условию целочисленности, поэтому переходим к шагу 5.

Шаг 5. Задачу 1 из списка выбрасываем, включая в него две новые задачи - задачу 2 и задачу 3. Разбиение задачи 1 производим по переменной х1:

Полагаем Z0(2) = Z0(1) = 0, возвращаемся к шагу 1.

Итерация 2. 1) Список ЗЛП включает 2, 3.

Шаг 1. Выбираем из списка одну задачу - задачу 2. Решаем ее, оптимальный план x = (1,4), f ( x ) = 6.

Шаг 2. Задача 2 имеет конечное решение, переходим к шагу 3.

Шаг 3. Сравниваем f ( x ) > Z0(2) = 0, следовательно, переходим к шагу 4.

Шаг 4. Все компоненты вектора x удовлетворяют условию целочисленности, поэтому задачу 2 из списка исключаем, план x запоминаем и, полагая Z0 = f ( x ) = 6, возвращаемся к шагу 1.

Итерация 3.

Шаг 1. Выбираем из списка ЗЛП задачу 3, решаем ее, получим оптимальный план x = (2, 7 / 3).

Шаг 2. Задача 3 имеет конечное решение, следовательно, переходим к шагу 3.

переходим к шагу 4.

Шаг 4. Компоненты вектора x не удовлетворяют условию целочисленности, следовательно, задачу 3 из списка выбрасываем и переходим к шагу 5.

Шаг 5. Вместо задачи 3 включаем в список две задачи - 4 и 5.

Разбиение задачи 3 производим по переменной х2:

Полагая Z0(4) = Z0(3) = 6, возвращаемся к шагу 1.

Итерация 4. Выбираем из списка ЗЛП задачу 5. Она не имеет решения, следовательно, выбрасываем ее из списка. Полагая Z0(5) = Z0(4), возвращаемся к шагу 1.

Итерация 5. Имеем: 1) Список ЗЛП - задача 5.

Шаг 1. Выбираем задачу 4. Решая ее, получаем оптимальный план x = (15 / 7, 2).

Шаг 2. Задача 4 имеет конечное решение x = (15 / 7, 2) и f ( x ) = 6, переходим к шагу 3.

Шаг 3. Так как f ( x ) > Z0(6) = 6, то переходим к шагу 4.

Шаг 4. Компоненты плана x не целочисленные, следовательно, задачу 4 из списка выбрасываем и, полагая Z0(5) = Z0(6), переходим к шагу Шаг 5. Задачу 4 выбрасываем из списка, а вместо нее включаем в него две новые ЗЛП, производя разбиение задачи 4 по переменной х1:

Итерация 6. Имеем 1) Список ЗЛП включает задачи 6 и 7.

Шаг 1. Выбираем из списка задачу 6 и решая ее, находим оптимальный план x = ( 2, 2). Так как компоненты плана целочисленные и f ( x ) = 6 =Z0(6), то задачу 6 из списка выбрасываем, а план x запоминаем.

Полагая Z0(7) = Z0(6) = 6 возвращаемся к шагу 1.

Итерация 7. Имеем: 1) Список ЗЛП - одна задача 7.

Шаг 1. Решаем задачу 7 и получаем оптимальный план x = (3, 0).

Шаг 2. Компоненты плана x целочисленные и значение функции f ( x ) = Z0 = 6. Задачу 7 из списка выбрасываем, план x запоминаем.

Все задачи линейного программирования, входящие в список, решены. При этом были найдены три целочисленных оптимальных исходной задачи является f ( x ) = 6; x = {(3,0); (2,2); (1,4)}.

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

Пример. В цехе предприятия решено установить дополнительное оборудование, для размещения которого выделено 19.3 м2-площади. На приобретение оборудования предприятие может израсходовать 10 тыс.

у.е., при этом оно может купить оборудование двух видов. Комплект оборудования 1 вида стоит 1000 у.е., а II вида—3000 у.е. Приобретение одного комплекта оборудования 1 вида позволяет увеличить выпуск продукции в смену на 2 ед., а одного комплекта оборудования II вида — на 3 ед. Зная, что для установки одного комплекта оборудования 1 вида требуется 2 м2 площади, а оборудования II вида — 1 м2 площади, определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение. Составим математическую модель задачи. Предположим, что предприятие приобретет х1 комплектов оборудования 1 вида и х комплектов оборудования II вида. Тогда переменные х1 и х2 должны удовлетворять следующим неравенствам:

Если предприятие приобретет указанное количество оборудования, то общее увеличение выпуска продукции составит По своему экономическому содержанию переменные х1 и х2 могут принимать лишь целые неотрицательные значения, т. е, Таким образом, задача (3.11)-(3.14) представляет собой задачу ЦЛП.

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

Имеется n городов, занумерованных числами 1,2,...,n. Для любой пары городов (i,j) задано расстояние (время, путевые расходы) C(i,j) между ними. Поэтому в общем случае C(i,j) C(j,i). Коммивояжер, выезжая из какого-либо города, должен посетить все города по одному разу и вернуться в исходный город. Необходимо определить такую последовательность объезда городов, при которой длина маршрута была бы минимальной.

Другая интерпретация этой задачи связана с минимизацией времени переналадок при обработке на одном станке партии из n различных деталей. Здесь C(i,j) - время переналадки при переходе от обработки детали i к обработке детали j. Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.

Для записи постановки задачи в терминах целочисленного линейного программирования определим булевы переменные следующим образом: xij = 1, если коммивояжер переезжает и i-го города в j-й; xij = 0, в противном случае. Тогда задача заключается в отыскании значений переменных xij удовлетворяющих следующим соотношениям:

при условиях xij = {0,1}, u i 0, целые, i=1,...,m, j=1,...,n (3.19) Ограничения (3.18) требуют, чтобы маршрут образовывал контур.

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

x = {(i1,i2), (i2,i3),…,(in-1,in), (in,i1)}.

Каждый допустимый маршрут представляет собой цикл, проходя по которому коммивояжер посещает каждый город ровно один раз и возвращается в исходный город. Каждая упорядоченная пара (i,j) является дугой маршрута. Длина F(x) маршрута x равна сумме соответствующих элементов C(i,j). Заметим, что множество всех допустимых маршрутов X содержит (n-1)! элементов.

Обозначим через C =(Cij) матрицу расстояний. Чтобы запретить переезды вида (i,i) положим C(i,i) = + (i=1,…,n).

Пусть Pi = min{Сij}, j= (1,...,n), Q j = min{Сij Pi }, i= (1,...,n), Тогда для любого маршрута x = {(i1i 2), (i 2 i 3),...,(i n 1i n), (i n i1)} X Неравенство (3.20) показывает, что d(X) является оценкой снизу для множества X. Кроме того, после редукции длины всех маршрутов уменьшаются на одну и ту же величину d(X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, На каждом шаге из числа кандидатов на ветвление выбирается множество X с наименьшей оценкой. Оно разветвляется на два подмножества множества, содержащих некоторую выбранную на данном шаге дугу (r,s),подмножество X 2 - из всех маршрутов множества X, не содержащих дугу (r,s).

Ребро дерева, соединяющее вершины X и X 1, помечается (r,s), а Пусть - редуцированная матрица, соответствующая вершине X. Опишем способ выбора дуги (r,s). Он основан на стремлении сделать оценку d ( X 1) поменьше, а оценку d ( X 2) - побольше, для того, чтобы увеличить вероятность выбора для дальнейшего ветвления множества X 1. Стремление к уменьшению d ( X 1) приводит к выбору такой дуги (µ,), для которой Стремление же увеличить d ( X 2) приводит к выбору среди дуг, удовлетворяющих условию (3.21) той дуги, для которой значение функции максимально, т.е.

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

Положим Искомая редуцированная матрица C 2 получается из C 2 с помощью описанной выше процедуры редуцирования. Сумма констант редуцирования равна при этом (r, s), а величина является оценкой снизу для целевой функции F(x) на множестве Рассмотрим теперь множество X 1. Все маршруты из этого множества содержат дугу (r,s). Найдем максимальный связанный путь, который принадлежит всем маршрутам множества X и содержит дугу (r,s). Пусть этот путь начинается в городе m и заканчивается в городе t (может быть, m=r или t=s, или то и другое одновременно).Чтобы запретить подцикл, начинающийся и заканчивающийся в m, положим c1 (t, m) = +. Остальные элементы матрицы C1 полагаем равными соответствующую городу r и столбец, соответствующий городу s, в матрицу C1 не включаем, поскольку все маршруты из X 1 содержат дугу (r,s).

Редуцированная матрица расстояний C 1 для вершины X получается из матрицы C1 с помощью операции редуцирования. При этом оценка снизу для функции F(x) на множестве X 1 вычисляется по формуле где - сумма констант редуцирования.

Формирование списка кандидатов на ветвление.

После вычисления каждой из оценок d ( X i ) (i=1,2) следует проверить, не состоит ли множество X i из единственного маршрута.

Если в каждой строке и в каждом столбце матрицы оказалось лишь единственный маршрут, длина которого равна d ( X i ). В этом случае верхняя граница Z 0 (наименьшее из уже вычисленных значений F(x) полагается равной минимуму из предыдущего значения т.е.

текущего значения Z 0, то множество X i включается в число кандидатов на ветвление. Остановка производится, если наименьшая из оценок снизу кандидатов на ветвление не меньше текущего значения Z0.

Пример. Решить методом ветвей и границ задачу коммивояжера с матрицей Возьмем в качестве произвольного допустимого маршрута x0 = {(1,2),(2,3),(3,4),(4,5),(5,1)}. Тогда F( x0 ) = 10+10+20+15+10 = 65 - текущее значение Z 0 - (верхняя граница длин всех маршрутов).

Нижняя граница d(X) = 10+1+8+10+8+9+12=58. Данное значение является нижней границей длин всех маршрутов. Заметим, что в идеальном случае поиск решения заключался бы в выборе ровно одного нулевого элемента в каждой строке и каждом столбце. Другими словами, если бы такой маршрут нулевой длины мог бы быть найден, то длина оптимального маршрута равнялась бы 58. Исходя из верхней и нижней границ можно заключить, что 58 F ( x *) 65.

Выберем дугу (r,s) с помощью вычисления значений функции (µ,).

(1,2)=0, (2,1)=0, (3,1)=0, (4,2)=4, (1,5)=1, (2,3)=5, (3,4)=2, (5,2)=2.

Следовательно, (r,s) = (2,3). Осуществим разбиение (ветвление).

Правое подмножество X 2 будет содержать все маршруты, которые исключают дугу (2,3). Поэтому C 2 (2,3) = +.

следующим образом:

Левое подмножество будет содержать маршруты, которые всегда включают дугу (2,3), и поэтому вторая строка и третий столбец в матрицу C1 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить c1 (3,2) = +, чтобы запретить подцикл {(2,3),(3,2)}. В результате получим матрицу Оценка снизу для левого подмножества В списке кандидатов на ветвление множества d ( X 1 ) < d ( X 2 ), следовательно, будем производить ветвление множества Выберем дугу (r, s) с помощью значений функции (µ,) для матрицы C1.

(1,2) = 0, (1,5) = 2, (3,1) = 2, (3,4) = 3, (4,2) = 4, (5,2) = 2.

Следовательно, (r,s) = 4, (r,s) = (4,2).

Правая подматрица:

Оценка снизу для правого подмножества:

Левая подматрица:

всегда включают дугу (4,2), и поэтому четвертая строка и второй столбец в матрицу C3 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить c3 (3,4) = +, чтобы запретить подцикл {(4,2),(2,3),(3,4)}. В результате получим матрицу В списке кандидатов на ветвление множества Минимальная нижняя оценка оказалась у множества следовательно, для дальнейшего разбиения выбираем множество Определим дугу (r,s) с помощью значений функции (µ,) для матрицы C 4.

(1,2) = 0, (1,5) = 1, (3,1) = 0, (3,4) = 3, (4,1) = 1, (5,2) = 2.

Следовательно, (r,s) = 3, (r,s) = (3,4).

Оценка снизу для правого подмножества:

Следовательно, множество всегда включают дугу (3,4), и поэтому третья строка и четвертый столбец в матрицу C5 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить c (4,2) = +, чтобы запретить подцикл {(2,3),(3,4), (4,2)}, однако это условие оказалось уже выполненным. В результате получим матрицу Оценка снизу для левого подмножества:

В списке кандидатов на ветвление множества Минимальная нижняя оценка оказалась у множества следовательно, для дальнейшего разбиения выбираем Определим дугу (r,s) с помощью значений функции (µ,) для матрицы C. (1,2)=0, (1,5)=1, (4,1)=3, (5,2)=2.

Следовательно, (r,s) = 3, (r,s) = (4,1).

Правая подматрица:

Оценка снизу для правого подмножества:

Следовательно, множество Левая подматрица:

Левое подмножество будет содержать маршруты, которые всегда включают дугу (4,1), и поэтому четвертая строка и первый столбец в матрицу C7 не включаются. В результате будем иметь матрицу на единицу меньшего размера. Далее необходимо положить c7 (1,2) = +, чтобы запретить подцикл {(2,3),(3,4),(4,1),(1,2)}.

Оценка снизу для левого подмножества:

В списке кандидатов на ветвление множества Множество содержит единственный маршрут с минимальной нижней оценкой, поэтому задача решена.x1={(1,5)(5,2)(2,3), (3,4), (4,1)} = x* Представим процесс решения в виде дерева.

коммивояжера:

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

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

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

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

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

4.1. Транспортная задача линейного программирования сосредоточенный у m поставщиков Аi в количестве аi(i=1..m) единиц соответственно, необходимо доставить n потребителям Вj в количестве bj(j=1..n) единиц. Известна стоимость сij перевозки единицы груза от i-го поставщика к j-му потребителю.

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

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

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

а) все грузы должны быть перевезены, т.е.

б) все потребности должны быть удовлетворены, т.е.

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

Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е выполняется условие (4.5), называется закрытой моделью; в противном случае - открытой. Для открытой модели может быть два случая:

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

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

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Вn+1, потребность которого В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Аm+1, запасы которого Как стоимость перевозки единицы груза до фиктивного потребителя, так и стоимость перевозки груза от фиктивного поставщика полагаются равными нулю, так как груз в обоих случаях не перевозится.

Транспортная задача имеет n+m уравнений с mn неизвестными.

Матрицу Х=(хij)m,n, удовлетворяющую условиям (4.2)-(4.4), называют планом перевозок транспортной задачи (хij - перевозками).

Определение. План Х*, при котором целевая функция (4.1) обращается в минимум, называется оптимальным.

Теорема 4.1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие баланса План транспортной задачи называется опорным, если положительным перевозкам соответствует система линейно независимых векторов Pij (i=1..m, j=1..n), где Pij - векторы при переменных хij (i=1..m, j=1..n) в матрице системы ограничений (4.2)Теорема 4.2. Существует план, содержащий не более m+n- положительных перевозок, при этом система векторов Pij, соответствующая таким перевозкам (хij > 0), линейно-независима.

Таким образом, опорный план транспортной задачи содержит m+nположительных перевозок. Дадим другое определение опорного плана.

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

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

Схема метода: 1) Полагают верхний левый элемент матрицы Х Возможны три случая:

а) если a1 < b1, то х11=а1 и всю первую строку, начиная со второго элемента, заполняют нулями.

б) если a1 > b1, то х11 = b1, а все оставшиеся элементы первого столбца заполняют нулями.

в) если a1 = b1, то х11 = а1 = b1, и все оставшиеся элементы первых столбца и строки заполняют нулями.

На этом один шаг метода заканчивается.

2) Пусть проделано k шагов, (k µ ) -й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это элемент xµ ( + µ = k + ).

Тогда полагают xµ = min(a (k), b (k) ), где элемента. В противном случае заполняют нулями оставшуюся часть µ го столбца.

Метод минимального элемента позволяет построить начальный опорный план транспортной задачи и является вариантом метода северозападного угла, учитывающим специфику матрицы С=(сij)m,n. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.

Схема метода: элементы матрицы С нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0.

Пусть элементом с минимальным порядковым номером оказался элемент хij0.

Тогда полагают хij0=min(ai, bj) Возможны три случая:

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

б) если min(ai, bj) = bj, то оставшуюся часть j-го столбца заполняют нулями.

в) если аi=bj, то оставшуюся часть строки и столбца заполняют нулями.

Далее этот процесс повторяют с незаполненной частью матрицы.

Пусть элементом с k-м порядковым номером оказался x (k).µ Возможны три случая:

а) a (k) < b (k), тогда xµ = a и оставшуюся часть строки заполняют нулями;

б) a (k) > b (k), тогда xµ = b (k) и остаток столбца µ заполняют нулями;

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

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

Исходная задача Обозначим двойственные переменные для каждого ограничения вида (4.7) через Ui (i=1,...,m) и вида (4.8)- Vj (j=1,...,n), тогда двойственная задача имеет вид Переменные задачи двойственной к транспортнoй Ui и Vj называют потенциалами.

Теорема 4.3. Для оптимальности плана X=(Xij)mn ТЗ необходимо и достаточно существования чисел (потенциалов) V1, V2,..., Vn и U1, U2,..., Um таких, что U i + V j C j для i=1,...,m, j=1,...,n, Из теоремы следует: для того чтобы опорный план был оптимальным, необходимо выполнение следующих условий:

а) для каждой занятой клетки (отличного от нуля элемента матрицы Х) сумма потенциалов должна быть равна стоимости перевозки единицы груза б) для каждой незанятой клетки (Xij=0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие невырожденного опорного плана. Такой план содержит m+n-1 занятых клеток, поэтому для него можно составить систему из m+n-1 линейнонезависимых уравнений вида (4.12) с неизвестными Ui и Vj. Уравнений на одно меньше, чем переменных, поэтому система является неопределенной и одному неизвестному (обычно U1) придают нулевое значение. После этого остальные потенциалы определяются однозначно.

Проверка выполнения оптимальности для незанятых клеток.

Просматриваем строки и для каждой незанятой клетки проверяем выполнения условия (4.13), т.е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток U i + Vj C ij, то по теореме 4.3 проверяемый план является оптимальным. Если для некоторых клеток Ui+Vj>Cij, то план является неоптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (Ui+Vj)-Cij>0.

Выбор клетки, в которую необходимо послать перевозку.

Загрузке подлежит в первую очередь клетка, которой соответствует max((Ui+Vj)-Cij).

Построение цикла и определение величины Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком “+”, незанятую клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. Занятых клеток стало m+n, поэтому появляется цикл, все вершины которого за исключением клетки, отмеченной знаком “+”, находятся в занятых клетках, причем этот цикл единственный.

Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком “+”, поочередно проставляем знаки ”-” и “+”. Затем находим 0 =min Xij, где Xij -перевозки, стоящие в вершинах цикла, отмеченной знаком “-”.

Величина 0 определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение 0 записываем в незанятую клетку, отмеченную знаком “+”. Двигаясь по циклу, вычитаем 0 из объемов перевозок, расположенных в клетках, которые отмечены знаком “-”, и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком “+”. Если 0 соответствует несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m+n-1.

Проверка нового плана на оптимальность.

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

Пример 4.1. Решить ТЗ:

Решение. Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

Предварительный этап: Находим исходный опорный план X° методом «минимального элемента ».

Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:

Итерация 1. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток ( хij>0).

Для этого, например, полагаем U1= 0 ( записываем U1= 0 слева в табл. 4.2).

Далее, исходя из занятых клеток (1, 2) и (1, 3), находим V2= = 4 - 0 = 4, V3= 6 - 0 = 6 (записываем сверху в таблице ). На основе базисной клетки (2, 3) получаем U2=2 - 6 =-4, затем V1= 1-(-4) = 5; U =3 - 4= -1; V4=2.

Далее вычисляем сумму потенциалов для каждой из свободных клеток и записываем их в верхнем левом углу. Так как для клеток (3,1) и (3,3) критерий оптимальности (условие B) не выполняется:

то полученный опорный план не оптимальный. Так как то в любую из клеток, например, в (3,1), проставляем некоторое число 1.

Для того, чтобы не нарушился баланс в 3-ей строке, вычитаем 1 из величины перевозки, стоящей в клетке (3, 2), прибавляем к Х12= 100, вычитаем от Х13, прибавляем к Х23 и вычитаем от Х21, т.е. составляем цикл :

(3,1)->(3,2)->(1,2)->(1,3)->(2,3)->(2,1)->(3,1).

Знаки + и - в клетках чередуются.

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

Новый опорный план приведен в таблице 4. Итерация 2. Проверяем полученный план Х(1) на оптимальность.

Находим систему потенциалов. Они записаны в таблице слева и сверху, вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки). Так как то план Х(1) не является оптимальным. Для построения нового опорного плана проставляем величину 2 в клетку (1,4) и составляем цикл:

(1,4)->(3,4)>(3,1)->(2,1)->(2,3)->(1,3)->(1,4).

Определяем значение 2 =50, при этом две клетки (1,3) и (3, 4) обращаются в нулевые. Следовательно, план Х(2) будет вырожденным.

Для дальнейшего решения необходимо оставить нуль в одной из клеток и считать ее за базисную. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т.е. в клетке (3,4). Новый опорный план приведен в таблице 4. Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:

поэтому полученный план является оптимальным:

Пример 4.2. Решить задачу:

Решение. Объем ресурсов: 80+60+60=200 превышает общие потребности: 30+70+60=160 на 40 ед., следовательно, ТЗ является задачей открытого типа. Вводим дополнительный (балансовый пункт) потребления с объемом потребностей b 4 = 40 и полагаем c14 = c 24 = c 34 = 0.

В результате получаем ТЗ закрытого типа.

Предварительный этап. Находим исходный опорный план x ( 0) методом ‘‘минимального элемента’’ (см. таблицу 4.5).

образовалось замкнутого маршрута (цикла). В нашем примере c 14 = c 34 = 0, но занять клетку (1,4) нельзя, так как образуется цикл:

Поэтому ставим ‘‘0’’ в клетку (3,4) Итерация 1. Проверяем план x ( 0) на оптимальность. Положив u 1 = 0, находим потенциалы (см. таблицу). Далее находим сумму потенциалов для свободных клеток (они записаны в левом верхнем углу клетки). Так как то полученный опорный план x 0 неоптимальный. Для клеток (1,4) и (3,1) оценки одинаковы 14 = 2 0 = 2 и 31 = 5 3 = 2, поэтому выбираем любую, например, (1,4). Проставляем в эту клетку 1 и составляем цикл, чередуя знаки ‘‘+’’ и ’’-‘‘; получим 1 = 10. Новый опорный план представлен в таблице (4.6).

табл. 4.6 ). Сумма потенциалов для небазисных клеток записана в левом верхнем углу. Критерий оптимальности не выполняется для клетки (3,1):

Проставим в эту клетку 2 и составим замкнутую цепочку, в результате получаем 2 = 0.Опорный план x ( 2 ) представлен в таблице 4.7.

Итерация 3. Найдя систему потенциалов, убеждаемся в оптимальности плана x ( 2 ) (см. таблицу 4.7).

x = (0, 70, 0, 30, 0, 0, 0, 0, 60). Так как четвертый потребитель фиктивный, то 10 ед. груза останутся у первого поставщика, 30 ед. - у второго.

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

1. При некоторых реальных условиях перевозки груза из определенного пункта Ai в пункт назначения B j не могут быть осуществлены. Для определения оптимальных планов таких задач предполагают, что стоимость перевозки единицы груза из пункта Ai в пункт B j является сколь угодно большой величиной М и при этом условии известными методами находят решение транспортной задачи.

Такой подход к нахождению решения ТЗ называется запрещением перевозок.

2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из Ai в B j требуется обязательно перевезти ij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки Ai и столбца B j, записывают указанное число ij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой транспортной задачи находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Иногда требуется найти решение ТЗ, при котором из Ai в B j должно быть перевезено не менее заданного количества груза ij. Для определения оптимального плана такой задачи считают, что запасы Ai и потребности B j меньше фактических на ij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.

Пример 4.3.

Методом потенциалов решить следующую ТЗ:

между указанными пунктами запрещены.

Решение. Проверяем условие баланса:

80+320+150=550=250+100+150 +50.

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

В противном случае получаем решение исходной ТЗ.

Предварительный этап. Составляем методом ‘‘минимального элемента’’ исходный опорный план x 0 - таблица 4. Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность ( см. таблицу 4.8) т.е. план x ( 0) не является оптимальным. Проставляем в эту клетку 1 и составляем замкнутый маршрут. Получаем 1 = 20. Опорный план x 1 приведен в таблице 4. Итерация 2. Проверяем план x 1 на оптимальность (таблица 4.9.) Так как для всех свободных клеток:

то план x - оптимальный и не содержит положительных перевозок по запрещенным маршрутам.

Минимальные транспортные расходы составляют 3000.

Замечание: При целых ai (i=1,...,m) и b j (j=1,...,n), в силу специфики ограничений ТЗ любое базисное допустимое решение является целочисленным.

Решить транспортную задачу.

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

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

Оборудование m различных видов нужно распределить между n рабочими участками. Производительность единицы оборудования i-го вида на j-м рабочем участке равна pij;; i = 1,…,m; j = 1,…,n. Потребность j-го участка в оборудовании составляет bj, j = 1,…,n. Запас оборудования i-го вида равен ai, i = 1,…,m. Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна.

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

Обозначим через xij число единиц оборудования i-го вида, выделенное на j-й рабочий участок, i = 1,…,m; j = 1,…,n.

Математическая модель задачи имеет следующий вид:

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

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

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

Формирование оптимального штата фирмы.

Фирма набирает штат сотрудников. Она располагает n группами различных должностей по bj вакантных единиц в каждой группе, j = 1,…,n. Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по аi кандидатов в каждой группе, i = 1,…,m. Для каждого кандидата из i-ой группы требуются определенные затраты сij на обучение для занятия j-ой должности, i=1,…,m; j=1,…,n. (В частности, некоторые cij = 0, т.е.

кандидат полностью соответствует должности, или cij =, т.е. кандидат вообще не может занять данную должность.) Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.

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

Математическая модель записывается в виде Задача календарного планирования производства.

Рассмотрим задачу календарного планирования производства на N последовательных этапах. Спрос изменяется во времени, но детерминирован. Спрос можно удовлетворить либо путем изменения уровня запаса при постоянном объеме производства, либо за счет изменения объема производства при постоянном уровне запаса, либо путем изменения и уровня запаса, и выпуска. Изменения объема производства можно добиться, проводя сверхурочные работы, а изменения уровня запаса можно обеспечить за счет создания постоянного положительного запаса, либо за счет неудовлетворенного спроса.

Нужно отыскать календарный план производства на N этапов, минимизирующий суммарные затраты. В модели предполагаются нулевые затраты на оформление заказа для любого этапа. В общем случае допускается дефицит при условии, что весь задолженный спрос должен быть удовлетворен к концу этапа N. Эти условия можно записать в виде транспортной задачи.

Введем следующие обозначения для этапа i; i= 1,2,...,N:

c i - производственные затраты на единицу продукции при обычном режиме работы, d i - производственные затраты на единицу продукции при работе в сверхурочное время ( d i > c i ), h i - затраты на хранение единицы продукции, переходящей из этапа i в этап i+1, p i - потери от дефицита на единицу продукции, требуемой на этапе i, но поставляемой на этапе i+1, a ri - производственная мощность (в единицах продукции) при обычном режиме работы, a ti - производственная мощность (в единицах продукции) при работе в сверхурочное время, b i - спрос (в единицах продукции).

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

Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.

Матрица полных затрат для эквивалентной транспортной задачи приведена в следующей таблице:

Дополнительный столбец используется для балансировки транспортной задачи, т.е. S = ai b j. Затраты на единицу продукции в дополнительном столбце равны нулю. Так как дефицит не допускается, то продукцию, выпускаемую на рассматриваемом этапе, нельзя использовать для удовлетворения спроса предыдущих этапов. В таблице это ограничение представлено заштрихованными ячейками, что, в сущности, эквивалентно очень большим затратам на единицу продукции.

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

Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i+1, i+2,..., N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1. Затем корректируются значения ai, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.

Производственные затраты на всех этапах одинаковы, т.е. ci = 2 и di = 3 при всех i. Издержки на хранение также постоянны на всех этапах и равны hi = 0,1 для любого i. Условия эквивалентной транспортной задачи приведены в таблице:

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

Упражнение:

а) Определите следующие величины:

объем производства на этапе 1 для этого же этапа – (120 единиц).

объем производства на этапе 1 для этапа 2 – (нулевой).

объем производства на этапе 1 для этапа 3 – (20 единиц).

объем производства при обычном режиме работы и в сверхурочное время на этапе 1 – (100 и 40 единиц соответственно).

запас, переходящий из этапа 1 в этап 3 – (20 единиц).

запас, переходящий из этапа 2 в этап 3 – (50 единиц).

запас, переходящий из этапа 3 в этап 4 – (нулевой).

б) Предположив, что на этапе 4 требуется 55 дополнительных единиц продукции, определите, каким образом эту продукцию нужно выпустить. (50 единиц в сверхурочное время на этапе 4 и 5 единиц в сверхурочное время на этапе 1).

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

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

Так, например, если pi – удельные потери от дефицита (т.е. на единицу продукции) в случае, когда продукция требуется на этапе i, а поставляется на этапе i+1, то удельные расходы, соответствующие {d N + p1 + p2 +... + pN 1} соответственно.

Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.

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

Удельные производственные затраты составляют 5 при обычном режиме работы и 10 при сверхурочной работе. Затраты на хранение и потери от дефицита равны 1 и 2 соответственно. Для трех этапов требуется 20, 35 и 15 единиц продукции соответственно. Исходные данные соответствующей транспортной модели приведены в таблице.

На этапе 2 сверхурочные работы не проводятся, так как соответствующая мощность равна нулю.

использованием описанного выше алгоритма. Суммарные затраты составляют (15 5 + 5 7 + 5 11 + 10 5 + 20 7 + 15 10 = 505) денежных единиц.

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

В результате использования метода минимальной стоимости сразу получим оптимальный план:

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

Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет 1) избытка произведенных в прошлом месяце изделий, сохраняющихся для реализации в будущем;

2) производства изделий в течение текущего месяца;

3) избытка производства изделий в более поздние месяцы в счет невыполненных заказов.

Затраты на одно изделие в каждый месяц составляют 4 долл. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 долл. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом 2 долл. в месяц.

Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно.

Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

Задачу можно сформулировать как транспортную задачу. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом.

Транспортная система Производственная система 1.Исходный пункт i 1.Период производства i 2.Пункт назначения j 2. Период потребления j 3.Предложение в пункте i 3 Объем производства за период j 4.Спрос в пункте j 4. Реализация за период j 5. Стоимость перевозки из 5. Стоимость производства и хранения за Таблица иллюстрирует структуру транспортной модели. Для рассматриваемой задачи стоимость «перевозки» изделия из периода i в период j выражается как стоимость производства в i-й период, i = j, стоимость производства в i-и период + стоимость задержки от i до j, cij= стоимость производства в i-й период + штраф за нарушение срока, Из определения cij следует, что затраты в период i при реализации продукции в тот же период i(i=j) оцениваются только стоимостью производства. Если в период i производится продукция, которая будет потребляться позже (ij} влечет за собой дополнительные расходы в виде штрафа. Например, с24 = 4+(0,5+0,5) = 5 долл., с41 = 4+(2+2+2) = 10 долл.

1.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 60, 30, 45, 25 между пятью видами работ, потребности в специалистах для каждого вида работ соответственно равны 20, 40, 25, 45, 30, а матрица характеризует эффективность использования специалиста на данной работе.

2. Выпуск продукции на трех заводах составляет 500, 700 и 600, причем затраты на производство единицы равны 9, 8 и соответственно. Потребности четырех потребителей на эту продукцию составляют 350, 200, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю:

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

3. Строительный песок добывается в трех карьерах с производительностью за день 46, 34 и 40 т. И затратами на добычу одной тонны 1, 2 и 3 руб. Соответственно; песок доставляется на четыре строительные площадки, потребность которых составляет 40, 35, 30, т. Транспортные расходы на перевозку одной тонны песка заданы матрицей:

Недостающее количество песка - 30 т. В день можно обеспечить двумя путями : увеличением производительности а) 1 - го карьера, что повлечет дополнительные затраты в 3 руб. На добычу 1 т.; б) 2 - го с дополнительными затратами в 2 руб. / т.

Определить оптимальный план закрепления строительных площадок за карьерами и оптимальный вариант расширения поставок песка.

4. Имеется три сорта бумаги в количествах 10, 8 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 8000, 6000, 15000 и 10000 экз. Расход бумаги на одну книгу составляет 0,6;

0,8; 0,4 и 0,5 кг, а себестоимость ( в коп.) печатания книги при использовании i - го сорта бумаги задается матрицей :

Определить оптимальное распределение бумажных ресурсов.

5. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 500, 700, 650 и 600 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300, 300 и 200 машин.

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

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

6.Решить задачу из примера 4.6 при условии, что затраты на производство единицы изделий составляют 4; 4,2; 4,1; 4 долларов в первый, второй, третий и четвертый месяцы соответственно.

7. Решить задачу из примера 4.6 при условии, что затраты на производство единицы изделий увеличиваются от месяца к месяцу на одну и ту же величину, равную 0,2 доллара.

8. Решить задачу из примера 4.6 при условии, что штрафы за каждое изделие, выпускаемое в счет невыполненных заказов, равны 2;

1,5 и 2 долларам во второй, третий и четвертый месяцы соответственно.