Задача целочисленного программирования. Решение методом Гомори, методом ветвей и границ, а также в Excel.

 

Модель задачи:

Найти производственную программу , максимизирующую целевую функцию прибыли:

(1)

 

при ограничениях по ресурсам:

(2)

 

И при условиях неотрицательности переменных:

 

. (3.)

Решение

Последняя таблица:

	Б	Н
		53, 33	-0, 33	0, 33	0, 00	0, 00	1, 00	0, 33	-1, 00
		33, 33	0, 67	0, 33	0, 00	1, 00	0, 00	0, 33	0, 00
		4, 58	1, 67	0, 08	1, 00	0, 00	0, 00	-0, 42	0, 25
		11175, 00	136, 00	62, 00	0, 00	0, 00	0, 00	55, 00	0, 00

 

Отрицательных двойственных оценок нет, следовательно, получен оптимальный план:

 

 

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

Не выполняется условие целочисленности решения: элементы базисного плана нецелочисленны.

 

Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонентjd нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (1)-(3) Если же в оптимальном плане задачи переменная принимает дробное значение, то к системе уравнений (2) добавляют неравенство

 

(4)

 

и находят решение задачи (1) – (3), (4).

 

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

 

Если в найденном плане задачи (1) – (3), (4) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (1) – (3), либо устанавливают ее неразрешимость.

 

Метод «ветвей и границ».

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

 

(1)

(2)

(3)

 

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

В = (4, 58; 33, 3)

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

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

 

 

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

 

Решение в Excel

(см. №1)

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

 

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

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

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

 

 

Допустимые уступки:

 

Формулировка задачи:

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

(5.1.)

(5.2.)

(5.3.)

При выполнении условий системы (5.4.)

(5.4.)

И неотрицательности переменных:

(5.5.)

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

Решение задачи

· ) – частный критерий;

 

 

· Если критерии на min, их следует привести к max умножением на -1;

· Критерии следует ранжировать по степени важности для предприятия;

· Назначаются уступки (величина допустимого отклонения .

 

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

 

 

Получено решение:

 

Переходим к максимизации функции при условиях (8.4) и дополнительном ограничении, учитывающем, что по критерию нельзя уступать более чем на . Так как , то дополнительное ограничение будет иметь вид: 6 (5.6.)

Графическое решение задач (5.2.), (5.4.), (5.5.) представлено на рисунке 6.

 

 

Получено решение:

 

Переходим к максимизации функции при условиях (5.4) и дополнительном ограничении, учитывающем, что по критерию нельзя уступать более чем на . Так как 7, 25, то дополнительное ограничение будет иметь вид: (5.7.)

Графическое решение задач (5.2.), (5.4.), (5.5.) и (5.7.) представлено на рисунке (7).

 

.

Получено решение:

 

Получено оптимальное решение многокритериальной задачи:

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Популярное:

1. New York, 1932, p. 407, а также Г. Салливен (Указ. соч., с. 10 и сл.).
2. А также 12 тестов по 10 вопросов,
3. Андрей Рублев также стал создателем высокого иконостаса. Ряды иконостаса, сформированные им, стали подниматься на алтарных преградах во всех русских храмах с 15 века.
4. Архитектурно-конструктивное решение
5. Архитектурно-конструктивное решение здания
6. Больше чем половинчатое решение: разрушайте, разрушайте
7. В соответствии с п. 1 ст. 27 АПК РФ, арбитражному суду подведомственны дела по экономическим спорам, а также связанные с осуществлением предпринимательской и иной экономической деятельностью.
8. Водные ресурсы России сосредоточены в реках и озёрах, болотах, ледниках и снежниках, а также в подземных водах (включая льды зоны многолетней мерзлоты).
9. Гибкое решение для передовой переработки
10. ГЛАВА VI: МИРНОЕ РАЗРЕШЕНИЕ СПОРОВ
11. Грамматические категории глагола(см. также №20)
12. Дифференциальные уравнения и их решение