Решение задач о назначениях с помощью табличных процессоров

Таблица 3.1

 

 

План назначения (1—4), (2—1), (3—3), (4—2),

maxZ =с14+с21+с33+с42 =12 + 7+ 15+14 = 48.

4. Метод отсечения

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

 

     (4.1)

     (4.2)

      (4.3)

     (4.4)

Алгоритм Гамори состоит  из нескольких этапов:

1. Решается задача (4.1) — (4.3) с отброшенным условием  целочисленности.

2. Полученное оптимальное  решение (если оно существует) проверяется на целочисленность. Если условие целочисленности выполняется по всем переменным, то оптимальное решение задачи (4.1) — (4.4) совпадает с оптимальным решением задачи (4.1) — (4.3). Если это решение не выполняется хотя бы по одной переменной, то переходят к третьему этапу. Если задача (4.1)-(4.3) оказывается неразрешимой, то задача (4.1)-(4.4) тоже не имеет решения.

3. Строится дополнительное  ограничение, отсекающее часть  области, в которой содержится  оптимальное решение задачи (4.1) —  (4.3) и не содержится ни одного  допустимого решения задачи (4.1) — (4.4).

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

Алгоритм Гомори позволяет за конечное число шагов прийти к оптимальному целочисленному решению, если оно существует.

С геометрической точки зрения каждому  дополнительному линейному ограничению  в n-мерном пространстве соответствует определенная гиперплоскость, отсекающая от многогранника решений некоторую его часть, включая и оптимальную на данном этапе нецелочисленную вершину.

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

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

Для лучшего понимания  существа вопроса обратимся к  наглядной иллюстрации случая п=2 (рис. 4.1). Ограничения задачи определяют на плоскости x1Ox2 некоторый многоугольник М, в вершине которого, если не учитывать условия целочисленности, достигается максимум целевой функции. Внутри этого многоугольника имеется конечное множество точек, которым соответствуют решения с целочисленными значениями переменных (на рисунке они обозначены кружочками). На рисунке показаны три прямые l1 ,l2 ,l3 соответствующие трем дополнительным линейным ограничениям. Каждая из прямых отсекает часть области допустимых решений. Так, после отсечения части области прямой оптимальной оказывается вершина ,и, наконец, оптимальной становится целочисленная вершина .Основное в алгоритме — составление дополнительного ограничения, т. е. отсекающей гиперплоскости, которая называется правильным отсечением. Правильное отсечение должно удовлетворять следующим условиям: 1) быть линейным; 2) отсекать найденное оптимальное нецелочисленное решение задачи (4.1) — (4.3); 3) не отсекать ни одной из целочисленных точек задачи (4.1) — (4.5).

 

 

 

 

 

 

Рисунок 4.1

 

Формирование правильного  отсечения. После каждой итерации система ограничений имеет вид

   (4.5)

где {БП} — множество  базисных переменных.

Если выполняется условие  оптимальности задачи, то находим  оптимальное решение. Если, все компоненты оптимального плана целочисленны, то задача решена. Предположим, что некоторые ( — нецелые. Пусть компонента i0 — нецелая. Рассмотрим i0 равенство системы (4.5), для которой выполняется условие оптимальности, т.е.

 

       (4.6)

 

Напомним, что наибольшая целая часть числа а, его не превосходящая, обозначается [а], а дробная положительная— {а}. Причем

 

      (4.7)

 

Например, пусть а = 3,2. Имеем [3,2] = 3; {3,2}=0,2; 3,2 =3+0,2. Пусть а= — 4,3. Имеем [-4,3]=-5, {-4,3}=0,7, -4,3=-5 + 0,7.

Перейдем к дальнейшему  изучению уравнения (4.6). Найдем целую  и дробную части его коэффициентов и .Согласно равенству (4.7), имеем:

     (4.8)

 

Так как, по предположению, нецелое, то

Кроме того, . Подставив выражение (4.8) в равенство (4.6), получим

  (4.9)

Так как первое слагаемое  равенства (4.9) есть целое число, то, для того чтобы было целым, необходимо, чтобы второе слагаемое также было целым, т. е. величина

 

должна быть целым  числом. Так как xio— координата допустимого целочисленного решения задачи (4.1) — (4.4), то Li0 -всегда целое число. Покажем, что Li0≤0. В самом деле, величина

не может быть отрицательной. Из условия (4.7) следует  Так как Li0 -целое, то из предположения,что Li0 > 0, должно следовать , что противоречит определению дробной части числа.

Итак, доказано, что любое  допустимое решение задачи (4.1) — (4.4) должно удовлетворять неравенству

       (4.10)

 

 

Глава 2 Решение задач о назначениях с помощью табличных процессоров

2.1 Постановка  задачи

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

Общая задача линейного программирования (ЗЛП) состоит  в нахождении экстремального значения (максимума или минимума) линейной функции.

Примером решения задачи является разработка оптимального плана деповского ремонта грузовых вагонов. В настоящее время этот вид ремонта выполняется в ремонтных вагонных депо, входящих в департамент ОАО «РЖД» по ремонту грузового вагонного парка. Программа ремонта по количеству и типам вагонов для каждого депо в отдельности устанавливается департаментом исходя из потребностей в ремонте, производственных  мощностей депо и имеющихся в наличии производственных ресурсов. С учетом того, что в настоящее время неуклонно возрастает вагонный парк других собственников, а также предстоящим акционированием департамента возникает проблема определения оптимальной производственной программы депо, обеспечивающей максимальную прибыль предприятию.

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

х_j – объем ремонта вагонов j-го типа; j = 1, 2, … n;

b_i – объем, имеющихся в наличии производственных ресурсов i-го вида; i = 1, 2, … m;

a_ij – расход i-го вида ресурсов на ремонт одного вагона j-го типа;

C_j – прибыль, получаемая предприятием за один отремонтированный вагон j-го типа.

Решение задачи осуществляется на основе следующей экономико-математической модели.

Найти совокупность переменных х_j, максимизирующих целевую функцию F:

 

,                 (1.1)

 

при наложенных ограничениях (система m линейных уравнений и неравенств с n переменными):

 

,                  (1.2)

 

x_j, j = 1….n,                                              (1.3)

 

где a_ij, b_i, с_j – заданные постоянные величины

Линейную функцию (1.1), для которой ищется экстремальное значение, принято называть целевой функцией. Условия (1.2) называются функциональными, а (1.3) – прямыми ограничениями задачи.

Для решения ЗЛП необходимо построить экономико-математическую модель исследуемого экономического процесса.

2.2 Решение задач линейного программирования с помощью надстройки MS Excel «Поиск решения»

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

Он достаточно трудоемок. Поэтому выполнение расчетов рекомендуется  в среде MS Excel.

Технологию решения  задач линейного программирования в среде MS Excel продемонстрируем на следующем примере.

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

Таблица 1.1

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

Ресурсы	Нормы расхода ресурсов на один вагон				Наличие ресурсов
	полувагон	крытый	платформа	хопер-дозатор
Раб. сила, чел.-ч	180	205	160	336	650 000
Материалы, тыс. руб.	28	27	26	54	100 000
Фонд времени, ч	17	18	16	30	125 000
Специальные   запчасти, тыс. руб.	0	0	0	15	5000
Прибыль на 1 вагон, тыс. руб.	7,3	7,5	6,5	15

 

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

Обозначим через х₁, х₂, х₃, х₄ количество вагонов каждого типа. Сформулируем экономико-математическую модель задачи:

 

F = 7,3х₁ + 7,5х₂ + 6,5х₃ + 15х₄ à max;

180х₁ + 205х₂ + 160х₃ + 336х₄ ≤ 650 000;

28х₁ + 27x₂ + 26х₃ + 54х₄ ≤ 100 000;

17х₁ + 18х₂ + 16х₃ + 30х ₄ ≤ 125 000;                      (1.4)

15 ∙ х₄ ≤ 5000;

x₁ ≥ 0; x₂ ≥ 0; x₃ ≥ 0; x₄ ≥ 0.

Решение задач линейного  программирования в среде MS Excel осуществляется с помощью надстройки «Поиск решения». Если в меню Сервис отсутствует команда  Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервиса Надстройки и активизируйте надстройку «Поиск решения». Если же этой надстройки нет в диалоговом окне «Надстройки», то необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки MS Excel (или Office) установить надстройку «Поиск решения». Для решения задачи необходимо:

1) создать форму для  ввода условий задачи;

2) указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки);

3) ввести исходные  данные;

4) ввести зависимость  для целевой функции;

5) ввести зависимости  для ограничений;

6) указать назначение целевой функции (установить целевую ячейку);

7) ввести ограничения;

8) ввести параметры для решения задачи линейного программирования.

Для рассматриваемого примера  продемонстрируем технологию решения  задачи оптимального использования  ресурсов.

1.  Подготовим форму для ввода условий задачи (рис. 1.1).

Рисунок 1.1. Форма для ввода условий задачи

2. В задаче оптимальные значения вектора X = (х₁, х₂ х₃, х₄) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции – в ячейке F4.

3. Введем исходные  данные в созданную форму. Получим  результат, показанный на рис. 1.2.

		Переменные
	Х1	Х2	Х3	Х4
Значение		0	0		ЦФ
коэф. в ЦФ	7,3	7,5	6,5	15	0
		Ограничения
Вид ресурсов					Левая часть	Знак	Правая часть
Труд	180	205	160	336	0	<=	650 000
Материалы	28	27	26	54	0	<=	100 000
Фонд времени	17	18	16	30	0	<=	125 000
Спец.запчасти	0	0	0	15	0	<=	5000