Книги, научные публикации Pages:     | 1 | 2 | -- [ Страница 1 ] --

Московский международный институт эконометрики, информатики, финансов и права И.Н. Мастяева Г.Я. Горбовцов О.Н. Семенихина ИССЛЕДОВАНИЕ ОПЕРАЦИЙ В ЭКОНОМИКЕ Москва, 2003 УДК 519.6 ББК 22.18

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

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

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

2 Содержание Программа курса Исследование операций в экономике........................ 4 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. Моделирование в экономике В общем виде модель можно определить как условный образ (упрощенное изображение) реального объекта (процесса), который создается для более глубокого изучения действительности. Метод исследования, базирующийся на разработке и использовании моделей, называется моделированием. Необходимость моделирования обусловлена сложностью, а порой и невозможностью прямого изучения реального объекта (процесса). Значительно доступнее создавать и изучать прообразы реальных объектов (процессов), т.е. модели.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- сетевые;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

- матричные;

- сетевые;

- теории игр;

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

Домашнее задание 1.

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

Проект Распределение Прибыль капиталовложений год 1 год 2 год 1 5 1 8 2 4 7 10 3 3 9 2 4 7 4 1 5 8 6 10 Максимальный объем капиталовложений 25 25 Требуется выбрать совокупность проектов, которой соответствует максимум суммарной прибыли.

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

Проект Предприятие 1 Предприятие 2 Предприятие С1 R1 С2 R2 C3 R 1 0 0 0 0 0 2 1 5 2 8 1 3 2 6 3 9 - - 4 - - 4 12 - - Цель фирмы состоит в получении максимального дохода от инвестиций.

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

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

Показатели Варианты Наличие 1 2 3 Прибыль, д.е./ед. 65 80 90 210 - Материальные ресурсы 200 180 240 250 Трудовые ресурсы 10 15 22 28 Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трех.

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. Для производства двух видов изделий А и В используется три типа технологического оборудования. Известны затраты времени и других ресурсов на производство ед. изделия каждого вида (см. табл.) Тип Нормы времени Огр. по фонду времени оборудования А В Верхний предел Нижний предел I 2 8 26 - II 1 1 - Затраты на 2 3 производство Требуется определить, сколько изделий каждого вида необходимо изготовить, чтобы себестоимость одного изделия была минимальной.

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

g1(y1)=1,4y1 - 0,2y g2(y2)=2y g3(y3)=2y3 - 0,3y Требуется распределить имеющийся ресурс между предприятиями так, чтобы в конце планового периода получить максимальный доход.

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

удельные затраты на транспортировку материалов с участка p на участок q составляют cqp.

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

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

Станок Накладные Затраты на Производительность расходы производство (в единицах продукции) единицы продукции 1 100 10 2 300 2 3 200 5 Сформулировать задачу целочисленного программирования.

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

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

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

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

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

n (min) = max f ( x) c x (2.1) j j j = n = aijx bi, i = 1.. m (2.2) j j= x 0, j = 1.. n (2.3) j Задачей, двойственной к ЗЛП (2.1)-(2.3), называется следующая ЗЛП m = min (max) g(y) yibi (2.4) i= m (2.5) yiaij ( )cj, j=1..n i= yi не ограничены в знаке, i=1..m (2.6) Из приведенного определения следует, что двойственная ЗЛП строится по следующим правилам:

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

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

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

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

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

Прямая задача Двойственная задача max f (x) = (C, x) min g(y) = ( y,b) Ax = b yA C (2.7) P= Q= x 0 y - не ограничен в знаке = max g( y) ( y,b) min f ( x) = (C, x) Ax = b yA C (2.8) P= Q= x 0 y - не ограничен в знаке Пример 2.1 Пусть прямая задача записана в виде основной ЗЛП:

Max (c,x), Ax b (2.9) x Приведем задачу (2.9) к канонической форме:

+ max[( C, x) (0, )] S + = A x b S (2.10) x 0, S Тогда двойственная задача (ДЗ) будет иметь вид:

min(y,b) yA C (2.11) y 0.

Пример 2.2.

Прямая задача + + max(5x1 12x2 4x3) + + x1 2x2 x3 + = 2x1 - x2 3x3 x1,2,3 0.

Прямая задача в каноническом виде max ( + + + 5x1 12x2 4x3 0S1) + + + = x1 2x2 x3 S1 + = 2x1 - x2 3x3 x1,2,3 0.

S1 Двойственная задача min(10y1 + 8y2) y1 + 2y2 2y1 - y2 y1 + 3y2 y1 + 0y2 y1,2 - не ограничены в знаке.

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

min(10y1 + 8y2) y1 + 2y2 2y1 - y2 y1 + 3y2 y1 у2 - не ограничена в знаке.

Пример 2.3 Прямая задача min( 5X1 - 2X2 ) - X1 + X2 - 2 X1 + 3X2 X1,2 Прямая задача в канонической форме min( 5X1 - 2X2 + 0 S1 + 0 S2) - X1 + X2 - S1 = - 2 X1 + 3X2 + S2 = X 0, j = 1,2, S 0, j =1,2.

j j Двойственная задача max( - 3 У1 +5 У2 ) - У1 + 2 У2 У1 + 3 У2 - - У1 + 0 У2 0 У1 + У2 У1,2 не ограничены в знаке.

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

max( - 3 У1 +5 У2 ) - У1 + 2 У2 У1 + 3 У2 - У1 0, У2 Пример 2.4. Прямая задача max( 5X1 + 6X2 ) X1 + 2X2 - X1 + 5X2 4X1 + 7X2 X1 не ограничена в знаке, X2 Прямая задача в канонической форме ' ' max( 5 X1- -5 X1'+ 6X2 + 0 S1 + 0 S2) ' ' X1 - X1' + 2X2 = ' " - X1 + X1 + 5X2 - S1 = ' " 4 X1 - 4X1 + 7X2 + S2 = ' ' X1, X1' 0, X 0, S 0, j =1,2.

2 j Двойственная задача min( 5 У1 +3 У2 + 8 У3) У1 - 2 У2 + 4 У3 - У1 + У2 - 4 У3 - 2 У1 + 5 У2 +7 У3 0 У1 - У2 +0 У3 0 У1 + 0У2 + У3 У1,2,3 - не ограничены в знаке Заметим, что первое и второе ограничения двойственной задачи можно заменить одним ограничением в виде равенства, избыточные ограничения на У2 и У3 можно отбросить. Окончательно получаем:

min( 5 У1 +3 У2 + 8 У3) У1 - 2 У2 + 4 У3 = 2 У1 + 5 У2 +7 У3 У1 не ограничена в знаке У2 0, У3 Очевидно, что задача, двойственная к двойственной, совпадает с прямой.

2.2. Основные положения теории двойственности Прямая задача Двойственная задача max f (x) = (C, x) min g(y) = (y,b) A x = b yA C x 0 y - не ограничен в знаке Теорема 1. Пусть x, y - планы соответственно прямой и двойственной ЗЛП, тогда f (x) g(y) (2.12) * * Теорема 2. Пусть x, y - планы соответственно прямой и ** * * двойственной ЗЛП и f (x ) = g(y ), тогда x, y - решения соответственно прямой и двойственной задач.

Теорема 3. Если прямая (двойственная) ЗЛП имеет конечное решение, то и двойственная (прямая) ЗЛП имеет решение, причем max f (x) = min g( y) (2.13) Если прямая (двойственная) ЗЛП не имеет решения, то и двойственная (прямая) ЗЛП не имеет решения.

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

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

* * y (Ax - b) = (2.15) * * x ( y A - C) = Замечание 2. Если прямая ЗЛП записана не в канонической форме, то условия дополнительной нежесткости для этой ЗЛП и двойственной к ней ЗЛП могут быть записаны в следующем виде:

m если хj* > 0, то yi* = Cj a ij i= n если x* < bi, то yi* = 0, aij j j= n если yi* > 0, то x* = bi, (2.16) aij j j= m если yi* > Cj, то хj* = 0.

a ij i= Получение оптимального плана двойственной задачи на основании теоремы 4.

Пример 2.5. Рассмотрим задачу:

min(2x1 + 4x2 ) 3x1 + x2 4x1 + 3x2 6 (2.17) x1 + 2x2 x1,2 * Ее решение x = (3/ 2;

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

max(3y1 + 6y2 + 3y3) 3y1 + 4y2 + y3 (2.18) y1 + 3y2 + 2y3 y1,2 0, y3 Применяем соотношение (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. Итак, имеем:

3у1*+4у2*+у3*=2, у1*=у3*=0, * т.е. вектор y = (0;

1/ 2;

0) является решением задачи (2.18) на * основании теоремы 4. Вычислим g(y ) = 6 1/ 2 = 3 = f (x), что соответствует утверждению теоремы 3.

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

Прямая задача. Двойственная задача.

max f (x) = 5 Х1 +12Х2 +4 Х3 min g(y) =10Y1+8 Y Х1 +2 Х2 +3Х3 10 Y1 +2 Y2 = 5 (а) 2Х1 - Х2 +3Х3 = 8 2 Y1 - Y2 12 (б) Х2,3 0 Y1 + 3 Y2 4 (в) Y1 0 (г) Х1 - не ограничена в знаке У2 - не ограничена в знаке.

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

Y1 +2 Y2 = 2 Y1 - Y2 = 12, откуда Y1 =29/5;

Y2=-2/5 и g(Y ) =54.

Ипользуя теорему 4, находим решение исходной задачи. Так как Y1 >0 и Y2 <0, то оба ограничения прямой задачи имеют вид строгих равенств.

Х1 +2 Х2 +3Х3 = 10 (2.19) 2Х1 - Х2 +3Х3 = Так как третье ограничение двойственной задачи выполняется в виде строгого неравенства ( 29/5 - 6/5 = 24/5 > 4), то X =0. Решая систему (2.19), получаем:

X1 = 26/5;

X = 12/5;

X =0;

f( X ) = 54,8.

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

Пусть прямая задача имеет вид основной ЗЛП = max f (x) (C, x) Ax = b (2.20) x 0 0.

, b Двойственная к ней ЗЛП имеет вид min g(y) = (y,b) yA C (2.21) y 0.

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

( S ) - ( S ) - x = X = BS b ;

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

n yi - C, (S ) = ( y, a ) - C =aij j j = 1, n. (2.23) j j j j= Пример 2.7. Решить следующую ЗЛП:

max ( 4Х1 + Х2 + 2Х3 +3 Х4 ) Х1 + 2 Х2 +3Х3 - Х5 + Х7 = -3Х2 +3Х3 + Х4 +5Х5 + 4Х7 =40 (2.24) 4 Х2 + Х5 + Х6 - Х7 = X 0, j = 1,7.

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

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

4 1 2 4 0 0 N(s) CN(s) XN(s) (s) a1(s) a2(s) a3(s) a4(s) a5(s) a6(s) a7(s) 1 4 50 1 2 3 0 -1 0 1 4 3 10 0 -3 1 1 2 0 4 - 6 0 24 0 4 0 0 1 1 -1/2 0 -2 3 0 2 0 j(0) f(x)= 1 4 38 1 0 3 0 -3/2 -1/2 5/ 4 3 28 0 0 1 1 11/4 3/4 29/ 2 1 6 0 1 0 0 1/4 1/8 -1/ 0 0 13 0 5/2 1/2 63/ j(1) f(x)= На первой итерации получен оптимальный план ЗЛП (2.24).

(1) (1) N = (1, 4, 2);

X = (38, 28, 6), N X = ( 38, 6, 0, 28, 0, 0, 0);

f( X ) = 242.

Запишем задачу, двойственную к (2.24) min(50Y1+10Y2+24Y3) Y1 4 (2.25) 2 Y1 - 3 Y2 + 3 Y3 3 Y1 + Y2 + 4 Y3 Y2 3 (2.26) -Y1 +2 Y2 + Y3 Y3 Y1 + 4 Y2 - Y3 Y1-3 не ограничены в знаке. (2.27).

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

Находим решение ЗЛП (2.25) по формуле 1 - 1/ (1) y =C B1-1 = (4, 3, 1) 0 1 3 / 4 = (4, 3, 1/2), N 0 0 1/ или (2.22):

y = ((1) + C1, (1) + C4, (1) + C6)= (0+4, 0+3, +0) = (4, 3, 1/2) 1 4 g( y) = 504 + 103 + 24 = 2.3. Анализ решения ЗЛП с помощью теории двойственности Математическая модель является прекрасным средством получения ответов на широкий круг самых разнообразных вопросов, возникающих при принятии оптимальных решений.

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

Виды анализа При постановке задачи После получения оптимального решения Анализ решения Вариантный Решения анализ по заказу Анализ Параметрический устойчивости Анализ Структурный пределов Много критериальный При условных исходных данных Рис.2.2.

Поясним некоторые вопросы. На этапе постановки задачи производится анализ с целью ответить на вопросы: Что будет, еслиЕ? и (или) Что надо, Е, чтобы Е?. Анализ с целью ответа на первый вопрос называется вариантным анализом, на второй - решениями по заказу.

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

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

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

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

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

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

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

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

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

Исходный Расход исходных продуктов Максимально продукт на 1 тыс. изделий (т) возможный запас (т) П1 П А 1 2 В 2 1 С 1 0,8 Изучение рынка сбыта показало, что суточный спрос на изделия П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 Х1 + 2Х2 + S1 = 2Х1 + Х2 + S2 = Х1+0,8Х2 + S3 = -Х1 + Х2 + S4 = Х2 + S5 = Х1 0, Х2 0 Sj 0 ;

j=1Е5.

Исходная и оптимальная симплекс-таблицы решения задачи Двойственная к ней имеет вид g(y) = 6Y1 +8 Y2 +5 Y3 + Y4 +2 Y5 +0 Y6 +0 Y7 min Y1 +2 Y2 + Y3 - Y4 - Y6 = 2Y1 + Y2 + Y3 + Y4 + Y5 -0 Y7 = Yi 0;

i=1Е Оптимальными планами этих задач являются соответственно векторы 10 / 3 1/ 4 / 4/ 0 X = 0 и Y = 3/ 5 3 2 / 3 На основании второй теоремы двойственности max f (x) =min g( y), т.е.

m max f (x) = yi bi i= Из этой формулы следует, что двойственная переменная 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 и станет С1 = 3 + С Тогда в последней (оптимальной) таблице решения исходной задачи симплекс-разности будут иметь вид:

2 2 / -1/ 3 + C1 (2) =0;

(2) =0;

(2) = 0 -1/ 5 =1/3 -1/3 С1;

1 2 - 0, 2 / - 2 -1/ 2 / 3 + C1 (2) = 0 - 2 / 5 -0=4/3+2/3 С 0 0, 1/ (2) =0;

(2) =0 (2) = 5 6 Полученный план X останется оптимальным при 1/ -1/ 3C1 условии (2) 0;

j = 1,7, то есть j 4 / 3 + 2 / 3C1 Решая эту систему неравенств, получим, что -2 С1 Это условие определяет пределы изменения С1, при которых сохраняется структура оптимального плана. Если от пределов изменения приращения С1 перейти к пределам изменения самой величины С1, то получим min С1 = 3 - max С1 = 3 - 2=1.

max С1 = 3 + max С1 =3 +1= Таким образом, при изменении С1 в пределах 1 С1 будет по-прежнему выгодно выпускать продукцию П1. При этом значение целевой функции будет f ( X ) = 4/3*2 + 10/3 (3+ С1 ) = 38/3 + 10/3 С Если выполнить аналогичные преобразования с С2, то получим -1/2 С2 4, откуда 3/2 С2 - пределы изменения С2, при которых будет выгодно выпускать продукцию П2. Полученные пределы изменения Сj - это, кроме того, пределы справедливости дополнительных двойственных оценок.

Рассмотрим влияние на полученное решение изменения запасов продуктов (ресурсов). Пусть запас исходного продукта А равен (6 + (0) ( 0) А). Вектор свободных членов b = X имеет вид:

N 6 8 (0) b =5 + А 1 2 Тогда в последней симплекс-таблице (см. на преобразование (S ) вектора a ) вектор свободных членов примет вид 4/ 3 2/ 3 4/3 + 2/ -1/ 10/3 10/3 -1/ (2) b = 3/5 + -1/ 5 А= 3/5 -1/ -1 - 2/ 3 2/3 - 2/ - 2/ (2) ( 2 ) Решение X =b будет допустимым, если все элементы вектора N (2) b будут неотрицательны.

4/ 3 + 2/3 10/3 -1/3 3/ 5 -1/5 3 - - 2/3 2/ Откуда -2 А 1.

Перейдя к пределам изменения А, получим 4 A 7.

Найденные пределы показывают границы, в которых может изменяться запас продукта А, чтобы номенклатура выпускаемой продукции (структура оптимального плана) осталась без изменений. А это означает, что при изменении запаса продукта А в найденных пределах оптимальным, то есть обеспечивающим наибольшую прибыль, является выпуск и продукции П1, и продукции П2, только в других количествах. Продукции П1 необходимо будет выпускать в количестве X1 =10/3 -1/ А;

продукции П2 - в количестве X2 =4/3+2/3 А, при этом доход будет f ( X ) =38/3 + 1/3 А.

Следовательно, если увеличить запас продукта А на 1 т ( А = 1), то для обеспечения максимизации прибыли выпуск продукции П целесообразно уменьшить до X1 = 3 тонн, а выпуск продукции П2 - увеличить до X2 = 13 тонн. Доход от реализации продукции станет равным f ( X ) = 13 тыс.руб Полученные пределы изменения правых частей уравнений исходной задачи это и есть пределы справедливости двойственных оценок.

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

f (x) =7,5х1+3х2+6х3+12х4max 2х1+х2+0,5х3+4х4 х1+5х2+3х3 3х1+6х3+х4 x1,2,3,4 0.

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

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

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

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

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

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

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

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

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

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

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

Домашнее задание 2. 1.

Решить с помощью MS Excel следующие задачи (варианты 1-5, 6 10).

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

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

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

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

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

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

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

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

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

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

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

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

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

1.

Сырье Норма расходов Ресурсы A B C D в I 2 1 0,5 4 II 1 5 3 0 III 3 - 6 3 7,5 3 6 Цена ( c ) Z=500, в =(2000,1500,2000) 2.

Сырье Норма расходов Ресурсы A B C D в I 1 1 0,5 4 II 2 3 3 0 III 3 - 5 1 7,5 3 4 Цена ( c ) Z=300, в в =(1500,2000, 2000) 3.

Сырье Норма расходов Ресурсы A B C D в I 4,5 1 0,5 4 II 1 5 3 2,6 III - 10 6 1 10,5 3 6 Цена ( c ) Z=700, c =(2000,2880,1500) 4.

Сырье Норма расходов Ресурсы A B C D в I 2 1 3,5 4 II 1,5 5 3 7 III 3 2 6 1 9 3 5,6 Цена ( c ) Z=450, в =(2000,1500,700) 5.

Сырье Норма расходов Ресурсы A B C D в I 2 1 0,5 4 II 1 5 3 0 III 3 - 6 1 13 3 11 8, Цена ( c ) Z=500, в =(1000,2500,500) 6-10.Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в2 ед. вещества В и в3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.

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

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

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

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

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

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

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

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

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

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

6.

Количество единиц вещества, Вещество содержащегося в 1 кг корма каждого вида 1 2 3 A 10 5 7 B - 10 13 - C 20 7 12 Цена 1 кг корма 9 11 12 (руб) r B =(400,180,200);

Z= 7.

Количество единиц вещества, Вещество содержащегося в 1 кг корма каждого вида 1 2 3 A 12 5 8 B - 4 13 - C 22 7 17 4. Цена 1 кг корма 11 9 12 (руб) r B =(400,180,200);

Z= 8.

Количество единиц вещества, Вещество содержащегося в 1 кг корма каждого вида 1 2 3 A 10 - 7 4. B 20 14 15 C - 7 12 Цена 1 кг корма 9 11 12 (руб) r B =(400,180,200);

Z= 9.

Количество единиц вещества, Вещество содержащегося в 1 кг корма каждого вида 1 2 3 A 10.5 5 7 B - 10 13 C 20 - 12 Цена 1 кг корма 16 15 12 (руб) r B =(400,180,200);

Z= 10.

Количество единиц вещества, Вещество содержащегося в 1 кг корма каждого вида 1 2 3 A 10 5 7 B - 7 8 C 20 7 12 Цена 1 кг корма 9 11 12 (руб) r B =(400,180,200);

Z= 2.5. Двойственный симплекс-метод (Р-метод) Пример 2.9. Рассмотрим следующую ЗЛП:

min(2Х1 + 4Х2 ) 3 Х1 + Х2 4 Х1 + 3 Х2 6 (2.28) Х1 + 2 Х2 Х1,2 Приведем рассматриваемую ЗЛП к каноническому виду max (-2 Х1 -4 Х2 ) 3 Х1 + Х2 - S1 = 4 Х1 + 3 Х2 - S2 = Х1 + 2 Х2 - S3 = X 0, j = 1,2, S 0, j =1,3.

j j или max (-2 Х1 -4 Х2 ) - 3 Х1 - Х2 + S1 = - - 4 Х1 - 3 Х2 + S2 = - 6 (2.29) Х1 + 2 Х2+ S3 = X 0, j = 1,2, Si 0, i =1,3.

j Рассмотрим расширенную матрицу системы линейных уравнений (2.29):

- 3 -1 1 0 0 - P(0) = - 4 - 3 0 1 0 - 1 2 0 0 1 Матрица P(0) содержит единичную подматрицу порядка 3 и, следовательно, определяет базисное решение (0) ( 0) X = (-3;

-6;

3);

N = (3;

4;

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

(0) ( 0) j = 1, (0) = (C,a ) - Cj = -Cj 0, N j j Так как все симплекс-разности матрицы P(0) являются (0) неотрицательными, то базисное решение X = (-3;

-6;

3) не N являющееся планом ЗЛП, является лучшим, чем оптимальный план.

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

Определение P-матрицы ЗЛП.

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

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

Условия перехода от одной P-матрицы ЗЛП к другой.

Пусть известна Р-матрица P(S ) ЗЛП (2.28), определяющая псевдоплан (S ) (S ) ( S ) X =b ;

N.

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

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

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

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

Алгоритм Р-метода.

Будем считать, что известна исходная Р-матрица P(0) задачи линейного программирования, определяющая исходный псевдоплан (0) ( ( ( 0) X = (b1,b20),...,bm0) ), N (0) (0) ( ( N = (N1, N20),..., Nm0) ).

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

Рассмотрим алгоритм S-й итерации метода последовательного уточнения оценок. В начале S-й итерации имеем Р-матрицу P(S -1) задачи линейного программирования, определяющую псевдоплан (S -1) (S -1) ( S -1) X =b, N.

N l Шаг 1. Найдем номер l из условия bl(S -1) = min bi(S -1).

1im Шаг 2. Если bl(S -1) 0, то псевдоплан (S -1) (S -1) ( S -1) X = b, N N l является оптимальным опорным планом, а ( S -1) ( S -1) ( S -1) C f ( X ) = ( N, X ) N N есть оптимальное значение линейной формы f (x), иначе переходим к шагу 3.

Шаг 3. Если ( aljS -1) 0, j = 1, n, то задача линейного программирования не имеет решения ( множество планов Р пусто), иначе переходим к шагу 4.

(S -1) Шаг 4. Вычисляем для столбцов a матрицы P(S -1) ( j Ni(S -1), i = 1, j 2, Е,m) симплекс-разности (S -1) и находим номер К из условия j (S -1) (S -1) (S -1) ( K = = min j,aljS -1) < 0..

(S ( - alK -1) 1 jn aljS -1) (S Направляющий элемент на S-й итерации метода есть элемент alK -1).

(S ) Шаг 5. Вычисляем компоненты вектора N :

Ni(S ) = Ni(S -1), i = 1,m, i l, Nl(S ) = K.

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

Решение задач P-методом.

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

-2 -4 0 0 N(s) CN(s) XN(s) a1(s) a2(s) a3(s) a4(s) a5(s) 3 0 -3 -3 -1 1 0 4 0 -6 -4 -3 0 1 5 0 3 1 2 0 0 f = 0 2 4 0 0 j(0) 2/4 4/3 - - - (0) 3 0 3/2 0 5/4 1 3/4 1 -2 3/2 1 3/4 0 -1/4 5 0 3/2 0 5/4 0 1/4 f = -3 0 5/2 0 1/2 j(1) (1) Так как компоненты псевдоплана X =( 3/2, 3/2, 3/2) являются N (1) неотрицательными, то X является оптимальным опорным планом N ЗЛП (2.28). Итак, * X =( 3/2, 0, 3/2, 0, 3/2) и min f (x) =3.

Пример 2.10. Решим ЗЛП:

max f (x) = - Х1 + 2Х -2 Х1 + Х2 Х1 + 2 Х2 4 (2.33) Х1 + 4 Х2 Х1,2 Приведем рассматриваемую ЗЛП к каноническому виду max f (x) = (- Х1 + 2 Х2 ) - 2 Х1 + Х2 - S1 = Х1 + 2 Х2 + S2 = Х1 + 4 Х2 - S3 = X 0, j = 1,2, Si 0, i =1,3.

j или max f (x) = (- Х1 + 2 Х2 ) 2 Х1 - Х2 + S1 = - Х1 + 2 Х2 + S2 = 4 (2.34) - Х1 - 4 Х2 + S3 = - X 0, j = 1,2, Si 0, i =1,3.

j Расширенная матрица -1 1 0 0 - ~ A(0) = 1 2 0 1 0 -1 4 0 0 1 - системы линейных уравнений (3.42) не являются Р-матрицей рассматриваемой ЗЛП, так как - (0) =(0, 0, 0) 1 + 1 = 1 > 0, (0) =(0, 0, 0) 2 - 2 = -2 < 0.

1 -1 Следовательно, к решению ЗЛП (3.41) не применим Р-метод.

Пример 2.11.

min f (x) = ( 6 Х1 + 3Х2 ) -3 Х1 + Х2 2 Х1 - 3 Х2 2 (2.35) Х1,2 Решение. Приведем задачу к каноническому виду f (x) = (- 6 Х1 - 3 Х2 ) max 3 Х1 - Х2 + S1 = - - 2 Х1 + 3 Х2 + S2 = - X 0, j = 1,2, S 0, j =1,2.

j j Так как расширенная матрица -1 1 0 - P(0) = - 2 3 0 1 - системы линейных уравнений рассматриваемой задачи является Р матрицей ((0) = 6 >0;

(0) = 3 >0 ), то задачу можно решить Р-методом.

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

-6 -3 0 N(s) CN(s) XN(s) a1(s) a2(s) a3(s) a4(s) 3 0 -1 3 -1 1 4 0 -2 -2 3 0 6 3 0 j(0) f = 3 - - - (0) 3 0 -4 0 7/2 1 3/ 1 -6 1 1 -3/2 0 -1/ 0 12 0 j(1) f = - ( ( Так как bl(1) = b11) = -4 < 0, а все a11) 0, то множество планов ЗЛП j (2.35) является пустым множеством.

Домашнее задание 2.2.

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

2 6 9 3000 2 3 3 1500 2 8 8 1. 2. 3.

3 5 104000 4 11000 4 5 3 5 2 2000 2 2,5 3 950 3 6 2 4. 5. 6.

4 4 31700 4 2 11100 4 3 2,5 2 1500 2 1 2 1000 2 3 2,5 7. 8. 9.

1 4 3 800 3 11000 2 3 3 1 4 2,5 10.

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

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

Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Найти вектор x En, максимизирующий линейную форму n (3.1) f (x) = xj cj j= и удовлетворяющий условиям:

n x = bi, i = 1,m (3.2) aij j j= x 0 j = 1,n (3.3) j - целые ( p n) (3.4) x1, x2,..., xp Пусть, для каждой целочисленной переменной можно указать верхнюю и нижнюю границы, в пределах которых безусловно содержатся ее оптимальные значения, то есть j Vj xj W;

j=1..p (3.5) При этом в систему функциональных ограничений необходимо включить р неравенств (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) и решаем ее.

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

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

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

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

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

j n f ( x) = c x max j j j = при условиях n a xj = bi, i = 1..m ij j= V1 x1 W......................

(s) Vj xj [x ] j......................

Vp xp Wp x1, x2,...., xn Задача Z+2:

n f ( x) = c x max j j j = при условиях n a xj = bi, i = 1..m ij j= V1 x1 W......................

(s) [x ] +1 xj Wj j......................

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

Пример. Решить ЗЦЛП f (x) = 2x1 +x2 max (3.6) 7x1 + 3x2 x1 + x2 5 (3.7) x1,2 - целые (3.8) 0x13 (3.9) 0x25 (3.10) В качестве 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, решаем ее, получим оптимальный план (1) (1) x =(1,5 ;

3,5), f (x ) = 6,5.

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

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

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

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

задача f (x) = (2x1 + x2) max 7x1 + 3x2 x1 + x2 0 x1 0 x2, задача f (x) = (2x1 + x2 ) max 7x1 + 3x2 x1 + x2 2 x1 0 x2 Полагаем Z0(2) = Z0(1) = 0, возвращаемся к шагу 1.

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

2) Z0(2) = 0.

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

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

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

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

Итерация 3.

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

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

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

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

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

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

задача f (x) = (2x1 + x2) max 7x1 + 3x2 x1 + x2 2 x1 0 x2 задача f (x) = (2x1 + x2) max 7x1 + 3x2 x1 + x2 2 x1 3 x2 Полагая Z0(4) = Z0(3) = 6, возвращаемся к шагу 1.

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

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

2) Z0(5) = Z0(4) = 6.

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

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

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

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

Шаг 5. Задачу 4 выбрасываем из списка, а вместо нее включаем в него две новые ЗЛП, производя разбиение задачи 4 по переменной х1:

задача f (x) = (2x1 + x2 ) max 7x1 + 3x2 x1 + x2 3 x1 3;

x1 = 0 x2 задача f (x) = (2x1 + x2) max 7x1 + 3x2 x1 + x2 2 x1 2;

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

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

2) Z0(6) = 6.

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

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

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

2) Z0(7) = 6.

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

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

Все задачи линейного программирования, входящие в список, решены. При этом были найдены три целочисленных оптимальных (2) (6) (7) (2) (6) (7) плана x, x, x, причем f (x ) = f (x ) = f (x ) = 6. Решением ** исходной задачи является 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 должны удовлетворять следующим неравенствам:

2x1 + x2 19 / 3, (3.11) x + 3x2 10.

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

Домашнее задание 3.1.

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

+ + 1. max(3x1 3x2 ) 2. max(3x1 2x2 ) + + 4x1 5x2 20 3x1 7x2 + + x1 6x2 12 x1 x2 0 x1 5 0 x1 0 x2 4 0 x2 + + 3. max( x1 3x2) 4. max(4x1 x2 ) + 3x1 4x2 12 2x1 - 3x2 + + 3x1 2x2 6 4 x1 9x2 0 x1 4 0 x1 0 x2 2 0 x2 + + 5. max(3x1 x2) 6. max(x1 2x2 ) + + 4x1 3x2 18 x1 x2 + + x1 2x2 6 3x1 8x2 0 x1 5 0 x1 0 x2 3 0 x2 + 7. max(2x1 x2) 8. max(3x1 - 2x2 ) + + 5x1 2x2 30 2x1 3x2 + 3x1 8x2 48 x1 - 2x2 0 x1 6 0 x1 0 x2 6 0 x2 + + 9. max(3x1 2x2 ) 10. max(x1 2x2) + + 2x1 x2 6 5x1 9x2 4x1 + 3x2 6 x1 + 3x2 0 x1 3 0 x1 1 x2 20 x2 3.2. Задача коммивояжера Имеется 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 удовлетворяющих следующим соотношениям:

n n (3.15) cij xij min i= j= при условиях n 1 = 1, j = 1,...,m (въезд в город j ) (3.16) x ij i= n = 1, j=1,...,n (выезд из города i ) (3.17) x ij j= ui - u + n xij n -1 ( i j ) (3.18) j xij = {0,1}, ui 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=( )nxn матрицу расстояний. Чтобы Cij + запретить переезды вида (i,i) положим C(i,i) = (i=1,Е,n).

Пусть = min{, j= (1,...,n), = min{ - }, i= (1,...,n), Q Pi С С Pi ij} ij j Cij = Cij - - Q Pi j.

Тогда - редуцированная матрица.

C =(C ij)nxn Пусть n n d(X) = Q - сумма констант редуцирования.

Pi + j i=1 j= Тогда для любого маршрута x = {( ( i1i2), i2i3),...,(in - 1in), (ini1)} X F(X) = C(i1,i2) + C(i2,i3)+...+C(in,i1) = = C (i1,i2) + C (i2,i3)+...+C (in,i1) + d(X) d(X) (3.20) Неравенство (3.20) показывает, что d(X) является оценкой снизу для множества. Кроме того, после редукции длины всех маршрутов X уменьшаются на одну и ту же величину d(X) и, следовательно, оптимальный маршрут, найденный с использованием редуцированной матрицы, оптимален и для исходной задачи.

Ветвление.

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

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

1 Ребро дерева, соединяющее вершины и, помечается (r,s), а X X 1 ребро дерева, соединяющее и помечается (r, s).

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

X Стремление же увеличить d( ) приводит к выбору среди дуг, X удовлетворяющих условию (3.21) той дуги, для которой значение функции 1 (,) = (, ) + (,) min min C C : :

максимально, т.е.

(r,s) = {(,)}.

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

1 Построение редуцированных матриц и и вычисление C C 2 оценок снизу Положим (i, j), (i, j) (r, s), c (i, j) = c +, (i, j) = (r, s) Искомая редуцированная матрица получается из с C C помощью описанной выше процедуры редуцирования. Сумма констант редуцирования равна при этом (r, s), а величина 1 d( ) = d( ) + (r, s) X X является оценкой снизу для целевой функции F(x) на множестве.

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

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

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

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

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

Z0 = min {Z0, d( ) }.

X i 1 Если содержит более одного маршрута и d( ) меньше X X i i текущего значения Z0, то множество включается в число X i кандидатов на ветвление. Остановка производится, если наименьшая из оценок снизу кандидатов на ветвление не меньше текущего значения Z0.

Пример. Решить методом ветвей и границ задачу коммивояжера с матрицей 10 25 25 1 10 15 C= 8 9 20 14 10 24 10 8 25 Возьмем в качестве произвольного допустимого маршрута,,,, = {(12),(2,3),(34),(45),(51)}. Тогда F( ) = 10+10+20+15+10 = x x 0 65 - текущее значение Z0 - (верхняя граница длин всех маршрутов).

Получим редуцированную матрицу.

C 10 25 25 10 10 0 15 15 1 10 15 2 1 0 9 14 C= 8 9 20 10 8 0 1 12 4 0 14 14 10 24 15 10 8 25 27 2 0 17 0 0 9 12 0 6 3 0 0 2 0 1 0 2 C.

= 4 0 5 2 0 8 Нижняя граница 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,3). Поэтому C2(23) = +.

, 0 6 3 0 0 0 6 3 0 2 1 0 0 2 C2 = 0 1 0 2 0 0 1 0 4 0 5 5 0 4 0 5 2 0 8 7 0 2 0 8 0 0 5 0 0 1 3 0 2 =.

0 1 0 2 C 4 0 0 2 0 3 Оценка снизу для правого подмножества определяется X следующим образом:

d( = d( ) + (2,3) = 58 + 5 = 63 < X Z0.

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

C 5 2 0 Оценка снизу для левого подмножества d( ) = d( ) + = 58 + 0 = 58 < Z0.

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

C (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).

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

1 2 4 5 1 2 4 1 0 3 0 0 1 0 3 3 0 0 2 0 3 0 0 C4 = 4 4 5 4 0 1 = 4.

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

d( ) = d( ) + (4,2) = 58 + 4 = 62 < X X Z Левая подматрица:

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

C 5 2 7 2 0 5 5 0 0 3 d( ) = d( ) + = 58 + 5 = 63 < Z0.

X X В списке кандидатов на ветвление множества,,.

X X X 3 Минимальная нижняя оценка оказалась у множества, X следовательно, для дальнейшего разбиения выбираем множество.

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

C (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).

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

1 2 4 5 1 2 4 1 0 3 0 1 0 0 3 0 2 3 0 C6 = 4 0 1 4 0 1 = 6.

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

d( ) = d( ) + (3,4) = 62 + 3 = 65 = Z0.

X X 6 Следовательно, множество исключаем из списка.

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

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

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

d( ) = d( ) + = 62 + 0 = 62 < Z0.

X5 X В списке кандидатов на ветвление множества,,.

X X X 3 5 Минимальная нижняя оценка оказалась у множества X5, следовательно, для дальнейшего разбиения выбираем множество.

X Определим дугу (r,s) с помощью значений функции (,) для матрицы C5. (1,2)=0, (1,5)=1, (4,1)=3, (5,2)=2.

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

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

1 2 5 1 2 1 0 0 0 0 0 1 0 C8 = 4 1 1 0 4 0 =.

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

d( ) = d( ) + (4,1) = 62 + 3 = 65 = Z0.

X8 X Следовательно, множество исключаем из списка.

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

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

2 1 C7 = 5 0 = 7.

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

d( ) = d( ) + = 62 + 0 = 62 < Z0.

X X В списке кандидатов на ветвление множества,,.

X X X 3 7 Множество содержит единственный маршрут с минимальной X нижней оценкой, поэтому задача решена.x1={(15)(52)(2,3), (34), (41)} = x*,,,, Z0 = F( x*) = 10 + 8 + 10 + 20 + 14 = 62.

Представим процесс решения в виде дерева.

Домашнее задание 3.2.

Решить методом ветвей и границ следующую задачу коммивояжера:

1. 2.

31 15 19 8 55 19 25 11 2 19 22 31 7 35 37 26 58 21 25 43 53 57 16 10 50 39 22 5 50 49 39 9 38 39 24 38 24 24 33 5 14 27 9 32 9 34 26 6 3 36 33 48 60 53 3. 4.

16 13 35 41 52 39 45 2 51 19 29 31 26 18 30 20 33 40 57 51 44 51 7 54 16 55 22 5 40 32 14 16 19 36 25 18 33 41 28 3 53 29 8 8 12 19 54 24 10 41 16 47 31 14 5. 6.

41 27 54 46 5 21 40 28 60 42 11 32 58 21 58 11 39 22 36 5 33 22 33 22 12 23 14 46 24 59 49 59 25 47 51 20 48 58 11 44 47 47 43 18 42 26 50 35 19 27 44 49 50 29 7. 8.

6 56 35 48 29 22 26 56 38 34 46 46 55 26 34 12 51 37 29 31 32 13 42 45 33 44 47 26 34 12 17 7 39 7 16 57 38 35 40 13 47 35 56 40 58 60 25 59 36 31 9 20 36 31 9. 10.

4 39 22 10 47 14 40 33 16 58 56 18 4 35 48 34 4 11 34 29 17 57 18 57 85 24 38 52 4 22 15 37 30 50 44 9 41 44 25 11 32 18 42 24 31 11 6 19 2 58 1 38 31 19 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.

Стоимость всего плана выразится двойной суммой m n Z= xij cij i=1 j= Систему ограничений получаем из следующих условий задачи:

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

n = ai, i = 1..m xij j= б) все потребности должны быть удовлетворены, т.е.

m x = bj, j = 1..n ij i= Таким образом, математическая модель транспортной задачи имеет следующий вид: найти минимальное значение линейной функции m n Z= xij (4.1) cij i=1 j= при ограничениях n = ai, i = 1..m (4.2) xij j= m = bj, j = 1..n (4.3) xij i= xij 0, i = 1,Е,m;

j = 1,Е,n;

(4.4) В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.

m n =. (4.5) ai bj i=1 j= Транспортная задача, в которой суммарные запасы и потребности совпадают, т.е выполняется условие (4.5), называется закрытой моделью;

в противном случае - открытой. Для открытой модели может быть два случая:

а) Суммарные запасы превышают суммарные потребности m n > ai bj i=1 j= б) Суммарные потребности превышают суммарные запасы m n < ai bj i=1 j= Линейная функция одинакова в обоих случаях, изменяется только вид системы ограничений.

Найти минимальное значение линейной функции m n Z= xij cij i=1 j= При ограничениях n x ai, i = 1..m ij j= (случай УаФ) m x = bj, j = 1..n, xij ij i= n x = ai, i = 1..m ij j= (случай УбФ) m x bj, j = 1..n, xij ij i= Открытая модель решается приведением к закрытой модели.

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

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

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

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

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

Теорема 4.2. Существует план, содержащий не более m+n- положительных перевозок, при этом система векторов Pij, соответствующая таким перевозкам (хij > 0), линейно-независима.

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

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

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

Схема метода: 1) Полагают верхний левый элемент матрицы Х х11=min(a1,b1).

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

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

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

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

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

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

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

Тогда полагают x = min(a(k), b(k) ), где -1 - a(k) = a - и b(k) = b xj x i j=1 i= Если 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).

Тогда x(k) = min(a(k), b(k) ), где - (g) a(k) = a x g = 1..k - j j= - (u) b(k) = b x u = 1..k - i i= Возможны три случая:

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

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

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

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

Исходная задача m n min (4.6) C Xij ij i=1 j= n (4.7) X = ai i = 1,m ij j= m = b j = 1, n (4.8) Xij j i= Xij 0, i = 1,m, j = 1,n (4.9) Обозначим двойственные переменные для каждого ограничения вида (4.7) через Ui (i=1,...,m) и вида (4.8)- Vj (j=1,...,n), тогда двойственная задача имеет вид m n max Ui + Vj (4.10) ai b j i= j= Ui + Vj Cij, i = 1,m, j = 1,n (4.11) Переменные задачи двойственной к транспортнoй Ui и Vj называют потенциалами.

Теорема 4.3. Для оптимальности плана X=(Xij)mn ТЗ необходимо и достаточно существования чисел (потенциалов) V1, V2,..., Vn и U1, U2,..., Um таких, что Ui + Vj C для i=1,...,m, j=1,...,n, j Ui + Vj = C, если Xij>0.

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

а) для каждой занятой клетки (отличного от нуля элемента матрицы Х) сумма потенциалов должна быть равна стоимости перевозки единицы груза Ui + Vj = C ;

(4.12) j б) для каждой незанятой клетки (Xij=0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза Ui + Vj Cij (4.13) Таким образом, для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Для построения системы потенциалов используем условие Ui + Vj = C, Xij>0.

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

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

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

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

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

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

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

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

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

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

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

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

5 4 6 3 1 10 2 1 2 3 3 1 150 150 250 50 Решение. Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

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

Таблица 4. 5 4 100+ 6 100- 3 1 10 2 1 150- 150+ 2 3 50- 3 1 150 150 250 Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:

r = m + n - 1 = 2+4-1 = 6.

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

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

Таблица 4. Vj V1 = 5 V2= 4 V3 = 6 V4 = Ui U1 = 0 5 5 4 6 2 3 100+ 100- U2 = -4 1 0 10 2 -2 1 150- 150+ U3 = -1 4 2 3 5 3 1 50- 150 150 250 Далее, исходя из занятых клеток (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) не выполняется:

U3+ V1 = 4 > 2, U3+ V3 = 5 > 3, то полученный опорный план не оптимальный. Так как 31= U3+ V1- Cij = 2 = 33, то в любую из клеток, например, в (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. Таблица 4. Vj 5 4 6 Ui 0 5 5 4 6 4 150 -4 1 0 10 2 0 100 -3 2 1 3 3 3 50 Итерация 2. Проверяем полученный план Х(1) на оптимальность.

Находим систему потенциалов. Они записаны в таблице слева и сверху, вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки). Так как U1+ V4 = 4 > 3, то план Х(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. Таблица 4. Vj 4 4 5 Ui 0 4 5 4 5 6 150 -3 1 1 10 2 0 50 -2 2 2 3 3 3 100 Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:

Ui+ Vj Cij для Хij= 0;

i=1,m;

j=1,n;

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

... 150... * X = 50... 250... и f(x*)= 1500.

100.........

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

7 3 5 7 8 3 8 30 70 Решение. Объем ресурсов: 80+60+60=200 превышает общие потребности: 30+70+60=160 на 40 ед., следовательно, ТЗ является задачей открытого типа. Вводим дополнительный (балансовый пункт) потребления с объемом потребностей b4 = 40 и полагаем c14 = c24 = c34 = 0.

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

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

Таблица 4. vj 3 12 ui 7 4 4 10- 5 1 2 8 - 40 20+ 8 2 5 - Данный план является вырожденным, поэтому ставим СС0ТТ - перевозку в клетку с минимальным значением cij, но так, чтобы не образовалось замкнутого маршрута (цикла). В нашем примере c14 = c34 = 0, но занять клетку (1,4) нельзя, так как образуется цикл:

(1,4) (2,4) (2,1) (1,1) (1,4).

Поэтому ставим СС0ТТ в клетку (3,4) Итерация 1. Проверяем план x(0) на оптимальность. Положив u1 = 0, находим потенциалы (см. таблицу). Далее находим сумму потенциалов для свободных клеток (они записаны в левом верхнем углу клетки). Так как u1 + v4 = 2 > u3 + v1 = 5 > 8, то полученный опорный план x0 неоптимальный. Для клеток (1,4) и (3,1) оценки одинаковы 14 = 2 - 0 = 2 и 31 = 5 - 3 = 2, поэтому выбираем любую, например, (1,4). Проставляем в эту клетку 1 и составляем цикл, чередуя знаки СС+ТТ и ТТ-СС;

получим 1 = 10. Новый опорный план представлен в таблице (4.6).

Таблица 4. vj 5 3 2 uj 7 3 4 70 5 2 30- 30+ 5 3 8 2 2 60 0 Итерация 2.Находим систему потенциалов (см. слева и сверху табл. 4.6 ). Сумма потенциалов для небазисных клеток записана в левом верхнем углу. Критерий оптимальности не выполняется для клетки (3,1):

31 = 5 - 3 = 2 > 0.

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

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

Таблица 4. vj 5 3 4 ui 5 3 4 4 70 5 3 8 7 30 3 1 8 2 - - 0 Транспортные издержки составляют 480 и x* = (0, 70, 0, 30, 0, 0, 0, 0, 60). Так как четвертый потребитель фиктивный, то 10 ед. груза останутся у первого поставщика, 30 ед. - у второго.

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

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

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

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

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

Пример 4.3.

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

6 6 1 4 12 - 6 5 5 4 3 - 250 100 150 Прочерк между пунктами A2 и B2,A3 и B4 означает, что перевозки между указанными пунктами запрещены.

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

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

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

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

Предварительный этап. Составляем методом ССминимального элементаТТ исходный опорный план x0 - таблица 4. Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность ( см. таблицу 4.8) Таблица 4. v 10-M j 2 1 7-M u i 6 6 1 M 8 6 M- 250 20- 5 4 3 M 80+ 70 В клетке (2,3) имеем u2 + v3 = M - 2 + 1 > 6, т.е. план x(0) не является оптимальным. Проставляем в эту клетку1и составляем замкнутый маршрут. Получаем 1 = 20. Опорный план x1приведен в таблице 4. Итерация 2. Проверяем план x1на оптимальность (таблица 4.9.) Так как для всех свободных клеток:

ui + v cij, j то план x1 - оптимальный и не содержит положительных перевозок по запрещенным маршрутам.

Таблица 4.9.

v j v1 = 3 v2 = 2 v3 = v4 = u i 6 6 1 u1 = 0 8 M 6 u = 5 20 5 4 3 M u = 2 Минимальные транспортные расходы составляют 3000.

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

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

1. 6 5 4 - 500 2. 5 1 2 4 8 8 2 6 300 2 5 - 3 9 - 7 6 100 - 2 2 5 400 200 150 250 60 40 36 3. - 5 4 2 30 4. 5 6 1 4 2 5 - 3 50 8 - 6 5 3 2 - 5 120 5 4 3 - 40 30 20 10 250 100 150 5. 3 - - 6 140 6. 4 7 1 1 5 2 3 1 160 5 - 3 4 1 1 2 4 150 3 - 2 8 50 70 130 150 10 80 90 7. 3 - 2 1 200 8. 4 3 2 - 2 3 - 4 70 10 10 4 7 5 8 7 3 80 12 - 11 5 20 40 80 60 300 150 100 9. 4 1 2 3 100 10. 2 7 4 3 3 6 - 4 200 5 - 12 7 - 2 3 5 150 8 1 - 13 40 60 100 50 10 20 40 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.

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

m n P = pij xij max i=1 j= n xij = ai, i = 1,Е,m;

j= m x = bj. j = 1,Е,n;

ij i= m n = ;

ai bj i=1 j= xij 0, 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.) Тогда данная задача соответствует транспортной модели. В роли поставщиков выступают группы кандидатов, а в роли потребителей - группы должностей. В качестве тарифов на перевозки рассматриваются затраты на переобучение.

Математическая модель записывается в виде m n С = xij min cij i=1 j= n xij = ai, i = 1,Е,m;

j= m x = bj. j = 1,Е,n;

ij i= m n = ;

ai bj i=1 j= xij 0, i = 1,Е,m;

j = 1,Е,n.

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

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

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

Введем следующие обозначения для этапа i;

i= 1,2,...,N:

- производственные затраты на единицу продукции при обычном ci режиме работы, - производственные затраты на единицу продукции при работе в d i сверхурочное время ( > ci ), d i - затраты на хранение единицы продукции, переходящей из этапа hi i в этап i+1, pi - потери от дефицита на единицу продукции, требуемой на этапе i, но поставляемой на этапе i+1, - производственная мощность (в единицах продукции) при ari обычном режиме работы, - производственная мощность (в единицах продукции) при ati работе в сверхурочное время, - спрос (в единицах продукции).

bi Модель без дефицита.

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

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

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

спрос на этапе j избыток 1 2 3... N a R C 1 C1 + h1+... + h R1 C1 + h1 C1 + h1 + h N - aT d1 d1 + h T1 d + h1 +... + h d + h1 + h 1 2 N- a R R2 C + h2 +... + h C2 C2 + h N - aT T2 d + h +... + h d2 d2 + h2 2 2 - N......

RN a RN C N aTN TN d N b b b... b S 1 2 3 N Дополнительный столбец используется для балансировки транспортной задачи, т.е. S =. Затраты на единицу продукции ai bj i j в дополнительном столбце равны нулю. Так как дефицит не допускается, то продукцию, выпускаемую на рассматриваемом этапе, нельзя использовать для удовлетворения спроса предыдущих этапов. В таблице это ограничение представлено заштрихованными ячейками, что, в сущности, эквивалентно очень большим затратам на единицу продукции.

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

k k, k = 1,2,...,N.

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

Пример 4.4.

Период Мощность (в единицах Спрос bi I продукции) (в единицах aRi aTi продукции) 1 100 50 2 150 80 3 100 100 4 200 50 Всего 550 280 Производственные затраты на всех этапах одинаковы, т.е. ci = 2 и di = 3 при всех i. Издержки на хранение также постоянны на всех этапах и равны hi = 0,1 для любого i. Условия эквивалентной транспортной задачи приведены в таблице:

1 2 3 4 Избыток 2 2,1 2,2 2,3 0 R 100 - - - - 3 3,1 3,2 3,3 0 50;

30;

T 20 - 20 - 2 2,1 2,2 0 R 150 - - - 3 3,1 3,2 50 30 - - 80;

T R 3 2 2,1 0 100 - - T 3 3,1 0 100 - - R 2 0 200 - T 4 3 - 50 120 200 250 200 20 50 150 В оптимальности решения можно убедиться, воспользовавшись условием оптимальности алгоритма транспортной задачи. Заметим, что полученное оптимальное решение является вырожденным.

Упражнение:

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

объем производства на этапе 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, то удельные расходы, соответствующие (TN,1) ячейкам (RN,1 ) и, составляют: {cN + p1 + p2 +... + pN -1} и соответственно.

{dN + p1 + p2 +... + pN -1} Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.

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

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

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

1 2 3 Избыток 6 7 R 5 - - - 11 12 T1 10 5 - 5 5 6 R 7 10 - - 5 R 9 7 - - - T 14 12 10 5 - 10 - 20 35 15 В таблице приведено решение задачи, полученное с использованием описанного выше алгоритма. Суммарные затраты составляют (15 5 + 5 7 + 5 11+105 + 207 +1510= 505) денежных единиц.

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

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

1 2 3 Избы ток V1= -1 V2 = 0 V3 = -2 V4 = - 5 6 7 U1=6 R1 15 - - - 10 11 12 U2 = 11 T1 5 5 - 5 7 5 6 U3 = 5 R2 - 15 - - 9 7 5 0 U4 = 7 R3 - 5 15 14 12 10 U5 = 12 T3 - 10 - 5 20 35 15 Суммарные затраты в этом случае составят 15 5 + 510 + 511+15 5 + 57 +1012 +155 = 485 денежных единиц.

Пример 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 до j Таблица иллюстрирует структуру транспортной модели. Для рассматриваемой задачи стоимость перевозки изделия из периода i в период j выражается как стоимость производства в i-й период, i = j, стоимость производства в i-и период + стоимость задержки от i до j, cij= i < j, стоимость производства в i-й период + штраф за нарушение срока, i > j.

Из определения cij следует, что затраты в период i при реализации продукции в тот же период i(i=j) оцениваются только стоимостью производства. Если в период i производится продукция, которая будет потребляться позже (ij} влечет за собой дополнительные расходы в виде штрафа. Например, c11 = 4 долл., с24 = 4+(0,5+0,5) = 5 долл., с41 = 4+(2+2+2) = 10 долл.

Таблица 4. Домашнее задание 4.2.

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

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

3 4 6 C = 1 2 4 5 8 Определить оптимальный план прикрепления потребителей к заводам при условии минимизации суммарных затрат на производство и транспортировку.

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

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

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

б) 2 - го с дополнительными затратами в 2 руб. / т.

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

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

0,8;

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

24 16 32 C = 24 24 30 24 16 Определить оптимальное распределение бумажных ресурсов.

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

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

Дана матрица 40 20 60 10 10 80 30 40 C = 70 30 30 50 50 10 40 50 характеризующая транспортные расходы на доставку машины с i-й ав-тобазы в j-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.

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

4,2;

4,1;

4 долларов в первый, второй, третий и четвертый месяцы соответственно.

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

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

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

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

10. Решить задачу из примера 4.6 при условии, что стоимость хранения единицы изделий меняется от месяца к месяцу и составляет 0,4;

0,3 и 0,7 долларов для первого, второго и третьего месяцев соответственно.

4.3. Задача о назначениях Рассмотрим ситуацию, когда требуется распределить m работ (или исполнителей) по n станкам. Работа i (i=1,...,m), выполняемая на станке j cij (j=1,...,n), связана с затратами. Задача состоит в таком распределении работ по станкам (одна работа выполняется на одном станке), которое соответствует минимизации суммарных затрат.

Эту задачу можно рассматривать как частный случай транспортной задачи. Здесь работы представляют лисходные пункты, а станки - пункты назначения. Предложение в каждом исходном пункте равно 1, т.е. ai = 1 для всех i. Аналогично спрос в каждом пункте назначения равен 1, т.е. b = 1 для всех j. Стоимость перевозки (прикрепления) j cij работы i к станку j равна. Если какую-либо работу нельзя выполнять cij на некотором станке, то соответствующая стоимость берется равной очень большому числу. Матрица стоимостей C определяется следующим образом:

станки 1 2 Е n ai 1 c11 c12... c1n 2 c21 c22... c2n виды работ...

...............

c m cm2... cmn m bj 1 1 Е Прежде чем решать такую задачу необходимо ликвидировать дисбаланс, добавив фиктивные работы или станки в зависимости от начальных условий. Поэтому без потери общности можно положить m = n.

Пусть = 0, если j-я работа не выполняется на i-м станке, xij xij = 1, если j-я работа выполняется на i-м станке.

Таким образом, решение задачи может быть записано в виде двумерного массива. Допустимое решение называется X = xij назначением. Допустимое решение строится путем выбора ровно одного элемента в каждой строке матрицы и ровно одного элемента в X = xij каждом столбце этой матрицы. Для заданного значения n существует n!

допустимых решений.

Теперь задача будет формулироваться следующим образом:

n n F(X ) = cij xij min j = i = n = 1, i = 1,...,n x ij j = n = 1, j = 1,...,n x ij i= xij {0,1}.

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

Для иллюстрации задачи о назначениях рассмотрим таблицу с тремя работами и тремя станками.

Станки 1 2 Виды 1 5 7 работ 2 14 10 3 15 13 Специфическая структура задачи о назначениях позволяет использовать эффективный метод для ее решения.

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

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

5 7 9 5 0 2 4 (0) 2 С = 10 1210 4 0 2 4 0 (0) = C.

15 13 1613 2 0 2 (0) 0 0 Оптимальное назначение:

* * * * x11 = 1, x23 = 1, x32 = 1, остальные x = 0, ij * F(X ) =5 + 12 + 13 = 30.

К сожалению, не всегда удается определить решение так просто.

Венгерский алгоритм Шаг 1. (Редукция строк и столбцов).

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

Шаг 2. (Определение назначений).

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

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

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

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

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

Шаг 3. (Модификация редуцированной матрицы).

Для редуцированной матрицы стоимостей:

а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

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

Перейти к шагу 2.

Замечания.

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

2) Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.

Пример 4.7. Покажем работу венгерского алгоритма на примере задачи о назначениях со следующей матрицей стоимостей:

2 10 9 15 4 14.

C = (cij )= 13 14 16 4 15 13 Итерация Шаг 1. Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

0 8 7 11 0 10.

2 3 5 0 11 9 Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

0 8 2 C = 11 0 5 4.

2 3 0 0 11 4 Шаг 2. Поиск допустимого решения, для которого все назначения имеют нулевую стоимость.

а) Строки 1, 2 и 4 содержат по одному невычеркнутому нулю.

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

б) Столбцы 3 и 4 содержат по одному невычеркнутому нулю.

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

(0) 8 2 11 (0) 5.

2 3 (0) 0 11 4 Таким образом, ни одно полное назначение не может быть получено, и необходимо провести дальнейшую модификацию редуцированной матрицы стоимостей.

Шаг 3. Модификация редуцированной матрицы.

0 8 2 C = 11 0 5 4.

2 3 0 0 11 4 а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно.

Для столбцов соответствующие величины равны 2, 1, 1 и 1.

б) Максимальное число нулей, по два, содержат строка 3 и столбец 1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной линией.

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

0 8 2 11 0 5.

2 3 0 0 11 4 г) Значение минимального невычеркнутого элемента равно 2.

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

0 6 0 13 0 5.

4 3 0 0 9 2 Итерация 2.

Шаг 2.

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

0 6 (0) 13 (0) 5.

4 3 0 (0) (0) 9 2 Оптимальное назначение:

* * * * * x13 = 1, x22 = 1, x34 = 1, x41 = 1, остальные x = 0, ij * F(X ) = 9 + 4 + 11 + 4 = 28.

Пример 4.8: (Задача размещения производства) Компания разрабатывает план выпуска трех новых видов продукции. Предположим, что компания владеет пятью предприятиями и что на трех из них должны производиться новые виды продукции - по одному виду на одно предприятие. Ниже указаны издержки производства и сбыта единицы продукции.

1. Издержки производства единицы продукции (руб.):

Предприятие 1 2 3 4 1 20 23 38 15 Вид 2 8 29 6 35 продукции 3 5 8 3 4 2. Издержки сбыта единицы продукции (руб.):

Предприятие 1 2 3 4 Вид 1 20 50 20 10 продукции 2 7 90 8 35 3 5 5 4 15 Плановый объем годового производства, который позволил бы удовлетворить спрос, и плановая стоимость единицы продукции каждого вида следующие:

Вид Плановый Плановая продукции объем стоимость производства (руб.) 1 35000 2 160000 3 54000 Решение: Общие издержки на единицу продукции складываются из издержек производства и издержек сбыта. Поскольку продажная цена единицы каждого вида продукции известна, то можно вычислить прибыль на единицу продукции:

Предприятие 1 2 3 4 Вид 1 15 -18 -3 30 продукции 2 35 -69 36 -20 - 3 20 17 23 11 Умножая прибыль, приходящуюся на единицу продукции, на годовой объем сбыта, можно получить общую годовую прибыль, соответствующую каждой паре вид продукции - предприятие. Данные величины (в тыс. руб.) приведены в следующей таблице:

Предприятие Вид 1 2 3 4 продукции 1 525 -630 -105 1050 2 5600 -11040 5760 -3200 - 3 1080 918 1242 594 Если прибыль рассматривать как отрицательные затраты, то исходная задача максимизации может быть сведена к минимизационной задаче о назначениях. Для того чтобы матрица стоимостей не содержала отрицательных элементов, сложим каждый элемент матрицы с числом 5760 и введем два вида фиктивной продукции (4 и 5), которой соответствует нулевая прибыль. В результате будет получена следующая матрица:

Предприятие 1 2 3 4 Вид 1 -525 630 105 -1050 - продукции 2 -5600 11040 -5760 3200 3 -1080 -918 -1242 -594 - Предприятие 1 2 3 4 1 5235 6390 5865 4710 Вид 2 160 16800 0 8960 продукции 3 4680 4842 4518 5166 4 0 0 0 0 5 0 0 0 0 5235 6390 5865 4710 160 16800 0 8960 4680 4842 4518 5166 С = 0 0 0 0 0 0 0 0 Итерация Шаг 1.

525 1680 1155 0 160 16800 0 8960.

C = 162 324 0 648 0 0 0 0 0 0 0 0 Шаг 2.

525 1680 1155 (0) 160 16800 (0) 8960 162 324 0 648.

0 0 0 0 0 0 0 0 Шаг 3.

525 1680 1155 0 160 16800 0 8960 162 324 0 648.

0 0 0 0 0 0 0 0 Итерация 2:

Шаг 2. Воспользуемся замечанием 1. Тогда получим:

365 1520 1155 (0) (0) 16640 0 8960 2 164 (0) 648 164.

0 (0) 160 160 0 0 160 160 (0) Оптимальное решение данной задачи следующее: производство первого вида продукции назначается предприятию 4, второго вида - предприятию 1, третьего вида - предприятию 3, четвертого вида - предприятию 2, пятого вида - предприятию 5. Очевидно, что последних назначения являются фиктивными. Суммарная годовая прибыль, соответствующая данному решению, равна1050 + 5600 + = 7892 тыс. руб.

Оптимальное исследование рынка.

Pages:     | 1 | 2 |    Книги, научные публикации