Условно-стандартная задача линейного программирования

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

Размещено на

Размещено на

Условно-стандартная задача линейного программирования

двойственный линейный программирование гомори

Необходимо выполнить в указанном порядке следующие задания.

1. Найти оптимальный план прямой задачи:

а) графическим методом;

б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

2. Построить двойственную задачу.

3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.

4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).

6. Найти оптимальное целочисленное решение:

а) графическим методом;

б) Методом Гомори.

Сравнить значения функций целочисленного и нецелочисленного решений.

1. а) Найдем оптимальный план прямой задачи графическим методом

Решение: Изобразим на плоскости систему координат Ох₁х₂ и построим граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):

Область допустимых решений определяется множеством АВСDЕ.

Для линий уровня 2х₁ + 3х₂ = h (h - const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рисунке она проходит через начало координат) Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L₆ и L₄, т.е. через точку . Для определения координат точки А решаем систему уравнений:



Это и будет оптимальным решением данной задачи, которому соответствует максимальное значение целевой функции Z_max:

.

1. б) Найдем оптимальный план прямой задачи симплекс-методом.

Приводим задачу к каноническому виду. Умножим первое ограничение на -1:

Для этого в левую часть ограничений-неравенств типа «» вводим по дополнительной переменной с коэффициентом (+1). В целевую функцию эти переменные входят с коэффициентом (0). Получаем

В 3-м ограничении отсутствует базисная переменная. Формулируем задачу искусственного базиса.

Полученную задачу будем решать модифицированным симплексным методом [1].

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

Находим начальное опорное решение. Для этого свободные переменные приравниваем к нулю х₁ = х₂ = 0. Получаем опорное решение Х₁ = (0,0,19,28,0,47,19) с единичным базисом

Б₁ = (А₃, А₄, А₇, А₆).

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



Оценки векторов, входящих в базис, всегда равны нулю. Опорное решение, коэффициенты разложений и оценки разложений векторов условий по базису опорного решения записываем в симплексную таблицу

Сб			0	0	0	0	0	0	-1
	xb	b	x1	x2	x3	x4	x5	x6	х7	b/x1	b/x2
0	x3	19	5	-4	1	0	0	0	0	3 4/5	-
0	x4	28	-2	-5	0	1	0	0	0	-	-
-1	x7	4	4	1	0	0	-1	0	1	1	4	Min
0	x6	47	6	7	0	0	0	1	0	7 5/6	6 5/7
	k	-4	-4	-1	0	0	1	0	0	4	4

Начальное опорное решение не является оптимальным, так как оценки ₁ = 4, ₂ = 1 для векторов А₁ и А₂ противоречат признаку оптимальности. Для оптимальности опорного решения в задаче на максимум требуется неотрицательность оценок для всех векторов условий.

Определим, введение, какого из двух векторов приведёт к большему приращению целевой функции. Приращения целевой функции найдём по формуле . Вычислим значения параметра ₀₁ для первого и третьего столбцов по правилу Креко, получим ₀₁ = 1 при l = 2 и ₀₂ =4 при l =2. Находим приращение целевой функции при введении в базис первого вектора и второго вектора . Следовательно, для наиболее быстрого нахождении оптимального решения необходимо ввести в базис опорного решения вектор А₂ вместо вектора базиса А₇.

Далее выполним преобразование Жордана-Гаусса с элементом х₂₂ = 1, получим второе опорное решение Х₂:

Сб			0	0	0	0	0	0	-1
	xb	b	x1	x2	x3	x4	x5	x6	х7
0	x3	35	21	0	1	0	-4	0	4
0	x4	48	18	0	0	1	-5	0	5
0	x2	4	Другие файлы: Основы линейного программирования В книге английского автора освещены основные положения и методы линейного программирования. Рассмотрены симплекс-метод и его реализация на ЭВМ, пробле... Транспортная задача линейного программирования История зарождения и создания линейного программирования. Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей. Методы сос... Программный комплекс решения задачи многокритериального линейного программирования Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об отно... Лекции - Линейное программирование с примерами решения задач Тематика лекций:Постановка задачи линейного программирования.Основная задача линейного программирования.Геометрическая интерпретация задачи линейного... Двойственность в линейном программировании Стандартная задача линейного программирования с n переменными и m ограничениями в форме неравенства. Симметричная пара двойственных задач. Экономическ...