Метод Гомори. Решение задачи без учета условия целочисленности. Приведем задачу к специальной форме

• Название: Решение задачи без учета условия целочисленности. Приведем задачу к специальной форме
• Дата: 03.03.2019
• Размер: 28.35 Kb.
• Имя файла: Метод Гомори.docx
• Тип: Решение; #69457

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

Дано условие:





Шаг 1. Симплекс методом находим оптимальное решение задачи без учета условия целочисленности.

Приведем задачу к специальной форме.





Составим симплекс таблицу.

	0	-3	-4
	10	1	4
	8	3	2

	10	-2	1
	10/4	1/4	1/4
	3	10/4	-1/2

	124/10	8/10	6/10
	22/10	-1/10	3/10
	12/10	4/10	-2/10

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

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



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

	124/10	8/10	6/10
	22/10	-1/10	3/10
	12/10	4/10	-2/10
	-2/10	-9/10	-3/10

	110/9	8/9	3/9
	20/9	-1/9	3/9
	10/9	4/9	-3/9
	2/9	-10/9	3/9

Оптимальное решение все еще не целочисленное.

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



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

	110/9	8/9	3/9
	20/9	-1/9	3/9
	10/9	4/9	-3/9
	2/9	-10/9	3/9
	-2/9	-8/9	-3/9

	12	1	0
	9/4	-1/8	3/8
	1	1/2	-1/2
	1/2	-5/4	3/4
	1/4	-9/8	3/8

Оптимальное решение все еще не целочисленное.

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



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

	12	1	0
	9/4	-1/8	3/8
	1	1/2	-1/2
	1/2	-5/4	3/4
	1/4	-9/8	3/8
	-1/2	-3/4	-3/4

	12	1	0
	2	-1/2	1/2
	4/3	1	-2/3
	0	-2	1
	0	-3/2	1/2
	2/3	1	-4/3

Оптимальное решение все еще не целочисленное.

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



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

	12	1	0
	2	-1/2	1/2
	4/3	1	-2/3
	0	-2	1
	0	-3/2	1/2
	2/3	1	-4/3
	-2/3	0	-2/3

	12	1	0
	3/2	-1/2	3/4
	2	1	-1
	-1	-2	3/2
	-1/2	-3/2	3/4
	2	1	-2
	1	0	-3/2

	23/2	1/2	3/4
	7/4	-1/4	3/8
	3/2	1/2	-1/4
	1/2	-1/2	-3/4
	1/4	-3/4	-3/8
	3/2	1/2	-5/4
	1	0	-3/2

Оптимальное решение все еще не целочисленное.

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



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

	23/2	1/2	3/4
	7/4	-1/4	3/8
	3/2	1/2	-1/4
	1/2	-1/2	-3/4
	1/4	-3/4	-3/8
	3/2	1/2	-5/4
	1	0	-3/2
	-3/4	-3/4	-3/8

	11	2/3	1/2
	2	-1/3	1/2
	1	2/3	-1/2
	1	-2/3	-1/2
	1	-1	0
	1	2/3	-3/2
	1	0	-3/2
	1	-4/3	-1/2