Глава II. Модели линейного программирования 5 страница

2° Для каждой свободной клетки составляют число

.

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

3° Из всех чисел выбирают максимальное и заполняют соответствующую ему свободную клетку, пользуясь циклом. Циклом называют замкнутую ломанную линию, состоящую из горизонтальных и вертикальных отрезков прямых, одна из ее вершин находится в свободной клетке, а остальные – в занятых клетках, причем число вершин всегда четное, а две соседние вершины расположены либо в одной строке, либо в одном столбце. Чаще всего ломанная имеет вид прямоугольника, но возможны иные фигуры (см. рис. 8.1).

Если ломаная линия, образуя цикл, пересекается, то точки самопересечения не являются вершинами.

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

- каждой из клеток, связанной циклом с данной свободной клеткой, приписывается определенный знак (в вершинах), причем свободной клетке «+», а всем остальным – поочередно «–» и «+» (плюсовые и минусовые клетки);

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

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

Рис. 8.1

4° Полученный опорный план проверяют на оптимальность, т. е. снова повторяют все действия, начиная с 1°.

Применим описанный алгоритм к решению транспортной задачи, заданной таблицей 8.2.

Первый опорный план найден методом наименьших затрат (таблица 8.4).

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

1°. Найдем потенциалы и для занятых клеток. Составим систему уравнений:

Полагая , найдем

, , , ,

, , .

2°. Для свободных клеток (см. таблицу 8.4) составим числа :

Построенный опорный план не является оптимальным, т. к. среди чисел есть положительные: и .

3°. Из двух свободных клеток (3; 1) и (3; 3) выберем одну, к примеру (3.1) и построим для нее цикл. Припишем знаки каждой клетке в вершинах ломанной как показано в таблице 8.5.

Таблица 8.5

	–	+
		+ 3	–

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

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

.

Таблица 8.6

	+	–
			– 2	+

4°. Новый опорный план проверим на оптимальность, повторив предыдущие действия. Имеем

1°

, , , , ,

, , .

2°

Построенный опорный план не является оптимальным .

3° Построим цикл для свободной клетки (3; 3) и припишем знаки каждой клетке, связанной с циклом как показано в таблице 8.6. Найдем , переместим грузы в соответствующих клетках и получим новый опорный план, представленный таблицей 8.7, для которого

.

Таблица 8.7

Проверим полученный опорный план на оптимальность.

1° Имеем

, , , , ,

, , .

2°

Среди чисел нет положительных. Полученный план оптимальный.

Ответ:

, .

Замечание: Транспортная задача используется при решении и других экономических задач. Приведем примеры.

Задача оптимального использования оборудования.

Имеется m видов оборудования по изготовлению n типов деталей. Известно количество деталей каждого типа, изготавливаемых на каждом виде оборудования – , и необходимое количество требуемых деталей каждого типа – . Задается время использования i -го оборудования при изготовлении одной детали j -го типа – . Требуется определить минимальное время использования оборудования при выполнении планового задания. Математическая модель задачи имеет вид (8.1) – (8.4).

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

Имеется m различных станков, на которых может изготавливаться каждое из n изделий. Известны мощности станков – , в станко-часах и план выпуска изделий – , единиц. Задаются затраты в руб. на единицу j -го изделия при производстве его на i -ом станке – , а также производительность в шт/час i -го станка при производстве j -го изделия – . Требуется минимизировать суммарные затраты при выполнении плана выпуска. Математическая модель задачи имеет вид

при условиях

Модели целочисленного линейного программирования. Метод Гомори

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

Рассмотрим некоторые методы решения таких задач.

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

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

III. Метод отсечения или метод Гомори состоит в том, что сначала ЗЛП решается без условия целочисленности. Если полученное решение целочисленное, то задача решена. В противном случае к ограничениям задачи добавляется новое ограничение, называемое отсечением.

Опишем его построение. Пусть в оптимальном решении задачи () компонента не является целой. Составим неравенство (отсечение)

, (9.1)

где – дробная часть числа.

Оно обладает свойствами:

а) линейное относительно неизвестных ,

б) отсекает найденный оптимальный нецелочисленный план,

в) не отсекает ни одного целочисленного решения.

Далее ЗЛП решается с учетом нового ограничения. Если полученное решение целочисленное, то задача решена. В противном случае добавляется новое ограничение и т. д.

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

Обратимся к примерам применения указанных методов к решению ЗЛП.

Задача о модернизации оборудования.

При модернизации оборудования в цехе выделено 72 м² для установки оборудования первого и второго типов. На установку одного комплекта оборудования первого типа требуется 3 м², на установку одного комплекта оборудования второго типа – 4 м². Причем оборудование первого типа приносит ежемесячный доход 2 млн. руб., а оборудование второго типа – 6 млн. руб. Определить количество комплектов оборудования первого и второго типов, обеспечивающее максимальную прибыль, при условии, что предприятие может приобрести не более 16 комплектов оборудования первого типа и не более 8 комплектов оборудования второго типа.

Решение. Составим ЭММ задачи. Пусть – количество устанавливаемого оборудования j -го типа, . Тогда математическая модель задачи примет вид:

при условиях

где – целые числа.

Сначала решим задачу геометрическим методом.

На плоскости построим прямые:

или , и .

Очевидно, OABCD – многоугольник допустимых решений (см. рис. 9.1). Построим вектор . Перемещая линию уровня (на рис. 9.1 она изображена пунктиром), убеждаемся, что точка B – последняя точка встречи линии уровня с многоугольником OABCD. Найдем координаты точки B:

, .

Таким образом, – нецелочисленное оптимальное решение ЗЛП.

Рис. 9.1

Для нахождения целочисленного решения ЗЛП методом I построим целочисленную решетку на плоскости и заменим многоугольник OABCD многоугольником OAKLMNPD (см. рис. 9.1). Его вершина K будет последней точкой встречи с линией уровня, т. е. координаты точки K: и – оптимальное целочисленное решение ЗЛП.

Округляя , очевидно, получим такой же ответ задачи методом II.

Теперь найдем целочисленное решение методом Гомори.

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

(9.2)

, (9.3)

при которых требуется найти

Шаг 1: , , – базисные неизвестные; , – свободные неизвестные. Система ограничений (9.2) примет вид

(9.4)

Тогда (0; 0; 72; 16; 8) – базисное решение и .

Шаг 2: , , – базисные неизвестные; , – свободные неизвестные. Система ограничений (9.4) примет вид

(9.5)

Тогда (0; 8; 40; 16; 0) – базисное решение и примет значение .

Шаг 3: , , – базисные неизвестные; , – свободные неизвестные. Система ограничений (9.5) примет вид

(9.6)

Тогда – базисное решение и примет значение .

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

.

Имеем

;

;

,

где [ × ] – целая част числа.

Тогда отсечение (9.1) запишется в виде

(9.1¢)

или после введения в него дополнительной целочисленной неизвестной

. (9.1¢¢)

Шаг 4: , , , – базисные неизвестные; , – свободные неизвестные. Система ограничений (9.6) дополнится уравнением (9.1¢¢):