Условие оптимальности выполняется

Решение задачи: x ₁ = 2.5, x ₂ = 0, x ₃ = 1, z = 53.

Условие целочисленности не выполнено для переменной х₁.

Итерация 5. Рассматриваем исходную ЗЛП с дополнительными ограничениями:

х₁ £ 3, х₃ £ 0 и х₂ £ 0.

max z = 18x₁ + 9x₂ + 8x₃

          2x₁ + 21x₂ + 4x₃ £ 15

          6x₁ + 20x₂ + 5x₃ £ 20

          х₁ £ 3

          х₃ £ 0

          х₂ £ 0

          x_i ³ 0

Стандартная форма:

max z = 18x₁ + 9x₂ + 8x₃

          2x₁ + 21x₂ + 4x₃ + x₄ = 15

          6x₁ + 20x₂ + 5x₃ + x₅ = 20

          х₁ + х₆ = 3

          х₃ + х₇ = 0

          х₂ + х₈ = 0

          x_i ³ 0

Решение ЗЛП с помощью программы:

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

1	Число переменных	8
2	Число ограничений	5
3	Признак оптимизации	1
4	Число этапов моделирования	1

Коэффициенты целевой функции

	х1	х2	х3	х4	х5	х6	х7	х8
c	18	9	8	0	0	0	0	0

Фиктивные слагаемые коэффициентов целевой функции

	х1	х2	х3	х4	х5	х6	х7	х8
cm	0	0	0	0	0	0	0	0

Номера базисных переменных

	огр.1	огр.2	огр.3	огр.4	огр.5
x	4	5	6	7	8

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
огр. 1	2	21	4	1	0	0	0	0	15
огр. 2	6	20	5	0	1	0	0	0	20
огр. 3	1	0	0	0	0	1	0	0	3
огр. 4	0	0	1	0	0	0	1	0	0
огр. 5	0	1	0	0	0	0	0	1	0

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	x8	правые части
z	0	0	0	0	0	18	8	9	54
zm	0	0	0	0	0	0	0	0	0
x4	0	0	0	1	0	-2	-4	-21	9
x5	0	0	0	0	1	-6	-5	-20	2
х1	1	0	0	0	0	1	0	0	3
х3	0	0	1	0	0	0	1	0	0
х2	0	1	0	0	0	0	0	1	0

Условие оптимальности выполняется

Решение задачи: x₁ = 3, x₂ = 0, x₃ = 0, z = 54.

Условие целочисленности выполнено. Значение z = 54 принимается в качестве текущей границы. Данная ветвь – прозондирована. Кроме того, считается прозондированной ветвь с дополнительными ограничениями х₁ £ 3 и х₃ ³ 1 (итерация 4), так как значение целевой функции на этой ветви z = 53 меньше текущей границы.

Итерация 6. Рассматриваем исходную ЗЛП с дополнительными ограничениями:

х₁ £ 3, х₃ £ 0 и х₂ ³ 1.

max z = 18x₁ + 9x₂ + 8x₃

          2x₁ + 21x₂ + 4x₃ £ 15

          6x₁ + 20x₂ + 5x₃ £ 20

          х₁ £ 3

          х₃ £ 0

          х₂ ³ 1

          x_i ³ 0

Стандартная форма:

max z = 18x₁ + 9x₂ + 8x₃ – Мх ₉  

          2x₁ + 21x₂ + 4x₃ + x₅ = 15

          6x₁ + 20x₂ + 5x₃ + x₆ = 20

          х₁ + х₇ = 3

          х₃ + х₈ = 0

          х₂ – х₄ + х₉ = 1

          x_i ³ 0

Решение ЗЛП с помощью программы:

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

1	Число переменных	9
2	Число ограничений	5
3	Признак оптимизации	1
4	Число этапов моделирования	1

Коэффициенты целевой функции

	х1	х2	х3	х4	х5	х6	х7	х8	х9
c	18	9	8	0	0	0	0	0	0

Фиктивные слагаемые коэффициентов целевой функции

	х1	х2	х3	х4	х5	х6	х7	х8	х9
cm	0	0	0	0	0	0	0	0	-1

Номера базисных переменных

	огр.1	огр.2	огр.3	огр.4	огр.5
x	5	6	7	8	9

Матрица коэффициентов

	x1	x2	x3	x4	x5	x6	x7	x8	x9	правые части
огр. 1	2	21	4	0	1	0	0	0	0	15
огр. 2	6	20	5	0	0	1	0	0	0	20
огр. 3	1	0	0	0	0	0	1	0	0	3
огр. 4	0	0	1	0	0	0	0	1	0	0
огр. 5	0	1	0	-1	0	0	0	0	1	1

Результирующая симплекс-таблица

	x1	x2	x3	x4	x5	x6	x7	x8	x9	правые части
z	-17.14	0	-6.286	0	0.429	0	0	0	0	6.429
zm	0.095	0	0.19	1	0.048	0	0	0	0	-0.286
x2	0.095	1	0.19	0	0.048	0	0	0	0	0.714
x6	4.095	0	1.19	9	-0.952	1	0	0	0	5.714
х7	1	0	0	0	0	0	1	0	0	3
х8	0	0	1	0	0	0	0	1	0	0
х9	-0.095	0	-0.19	-1	-0.048	0	0	0	1	0.286

Условие оптимальности выполняется

Решение задачи: x₁ = 3, x₂ = 0, x₃ = 0, z = 54.

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

Все ветви прозондированы, поэтому оптимальное значение целевой функции совпадает с текущей границей, а соответствующей ей набор переменных является решением задачи (итерация 5): x₁ = 3, x₂ = 0, x₃ = 0, z = 54.

Схема решения задачи.

 

 

 

 

Аналогично оформляется отчет по частично целочисленной задаче линейного программирования.

Литература

1.	Трушков А. С. Решение и моделирование задач линейного программирования. Отчет и программная документация. - КФ МГОУ, г. Коломна, 1998 г., 76 с.
2.	Трушков А. С. Симплексный метод решения задач линейного программирования. Алгоритмы и приложения.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1996 г., 107 с.
3.	Трушков А.С. Методы решения задач математического программирования.// Учебное пособие. Изд-во КФ МГОУ, г. Коломна, 1997 г., 102 с.
4.	Трушков А.С. Контрольная работа “Динамическое программирование”. Контрольная работа “Целочисленное программирование”.// Сборник вариантов контрольной работы. Изд-во КФ МГОУ, г. Коломна, 1997 г., 100 с.