Решение задач симплекс-методом

Решение задач симплекс-методом

ЗАДАНИЕ 1

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

Сельскохозяйственное предприятие снабжает своей продукцией перерабатывающие предприятия региона. Для производства двух видов сельскохозяйственной продукции с пастбищ и сенокосов (П1, П2 ), требуется три вида ресурсов Р1 , Р2 , Р3 , где Р1 - трудовые ресурсы, Р2 - минеральные удобрения, Р3 - оросительная вода. При получении 1т продукции с пастбищ первый ресурс используется t^п1 чел- час, второй ресурс - t^п2 кг, третий ресурс -t^п3 м 3 . При получении 1 т продукции с сенокосов первый ресурс используется t^с1 чел- час, второй ресурс - t^с2 кг, третий ресурс - t^с3 м³ . Запасы ресурсов ограничены и не может превышать для первого вида продукции T1 чел-час, для второго - T2 кг, для третьего - T3 м³ . При реализации 1 т продукции с пастбищ предприятие получает прибыль С1 рублей, а при реализации 1 т продукции с сенокосов - С2 рублей. Найти оптимальный план выпуска продукции каждого вида, дающий максимальную прибыль от реализации всей продукции.

Решение:

Обозначим за X1 - объем в тоннах продукции с пастбищ, за X2 - объем в тоннах продукции с сенокосов

Составим математическую модель

Ограничение на трудовые ресурсы:

x₁+3x₂≤259

Ограничение на минеральные удобрения

x₁+2x₂≤162

Ограничения на оросительную воду:

₁≤39

При этом заметим, что объем продукции не должен быть отрицательным

_1, x₂≥0

Целевая функция будет иметь вид:

= 18x₁+11x₂ → max

Решим задачу графически:

Построим уравнение 5x₁+3x₂ = 259 по двум точкам.

₁ = 0 =>x₂ = 86.33.₂ = 0 => x₁ = 51.8.

Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 5 • 0 + 3 • 0 - 259 ≤ 0, т.е. 5x₁+3x₂ - 259≤ 0 в полуплоскости ниже прямой.

Построим уравнение 3x₁+2x₂ = 162 по двум точкам.

₁ = 0 => x₂ = 81.₂ = 0 => x₁ = 54.

Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 • 0 + 2 • 0 - 162 ≤ 0, т.е. 3x₁+2x₂ - 162≤ 0 в полуплоскости ниже прямой.

Построим уравнение x₁ = 39.

Эта прямая проходит через точку x₁ = 39 параллельно оси OX2. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 - 39 ≤ 0, т.е. x₁ - 39≤ 0 в полуплоскости левее прямой.

Построим прямую, отвечающую значению функции F = 0: F = 18x₁+11x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора - точка (0; 0), конец - точка (18; 11).

Прямая F(x) = const пересекает область в точке C, полученная в результате пересечения прямых:

x₁+3x₂=259

x₁+2x₂=162

Решив систему уравнений, получим: x₁ = 32, x₂ = 33

Откуда найдем максимальное значение целевой функции:(X) = 18*32 + 11*33 = 939

Решим задачу симплекс методом

переход к канонической форме

В 1-м неравенстве смысла (≤) вводим базисную переменную x₃. В 2-м неравенстве смысла (≤) вводим базисную переменную x₄. В 3-м неравенстве смысла (≤) вводим базисную переменную x₅.

x₁ + 3x₂ + 1x₃ + 0x₄ + 0x₅ = 259

x₁ + 2x₂ + 0x₃ + 1x₄ + 0x₅ = 162

x₁ + 0x₂ + 0x₃ + 0x₄ + 1x₅ = 39

Данное решение X=(0;0) соответствует точке A на графике

Данное решение X=(39;0) соответствует точке D на графике

Данное решение X=(39; 21¹/₃) соответствует точке E на графике

Данное решение X=(32; 33) соответствует точке C на графике

При решении задачи на компьютере получаем следующую модель:

Формулы имеют следующий вид:

Математическая модель

В результате получаем

ЗАДАНИЕ 2

Решить симплексным методом с искусственным базисом каноническую задачу линейного программирования:

Z = c₁x₁ + c₂x₂ + c₃x₃ + c₄x₄ + c₅x₅ → max

При условиях:

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

Решение

(X) = 2x₁ - 2x₂ - 3x₃ - 2x₄ - 2x₅ ->max

3x₁ + 3x₂ - x₃ - x₅≤13₁ + 3x₂ - x₄ - 3x₅≤1

2x₁ + x₂ + x₃ - 3x₄ + x₅≤8

переход к канонической форме

В 1-м неравенстве смысла (≤) вводим базисную переменную x₆. В 2-м неравенстве смысла (≤) вводим базисную переменную x₇. В 3-м неравенстве смысла (≤) вводим базисную переменную x₈.

x₁ + 3x₂-1x₃ + 0x₄-1x₅ + 1x₆ + 0x₇ + 0x₈ = 13

x₁ + 3x₂ + 0x₃-1x₄-3x₅ + 0x₆ + 1x₇ + 0x₈ = 1

x₁ + 1x₂ + 1x₃-3x₄ + 1x₅ + 0x₆ + 0x₇ + 1x₈ = 8

решение задача математический симплексный

Оптимальный план можно записать так:

X =( 4³/₄;0;0;0; 1¹/₄)(X) = -2•1¹/₄ + 2•4³/₄ = 7

Составим двойственную задачу:

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

*4³/₄ + 3*0 + (-1)*0 + 0*0 + (-1)*1¹/₄ = 13 = 13 => y₁ ≥ 0

*4³/₄ + 3*0 + 0*0 + (-1)*0 + (-3)*1¹/₄ = 1 = 1 => y₂ ≥ 0

*4³/₄ + 1*0 + 1*0 + (-3)*0 + 1*1¹/₄ = -8¹/₄ < 8 => y₃ = 0

x₁ ≥ 0=>3y₁ + y₂ - 2y₃=2

x₅ ≥ 0=>- y₁ - 3y₂ + y₃=-2

Получаем систему из двух уравнений:

Получаем, что₁ = ¹/₂₂ = ¹/₂₃ = 0(Y) = 13*¹/₂+1*¹/₂+8*0 = 7

Так как Z(Y)=F(X), значит полученный план является оптимальным

ЗАДАНИЕ 3

Решение:

Проверим необходимое и достаточное условие разрешимости задачи.

∑a = 200 + 100 + 200 + 200 + 300 = 1000

∑b = 200 + 400 + 100 + 200 + 100 = 1000

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

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

₂₁ = min(100,200) = 100.₁₁ = min(200,100) = 100.₅₅ = min(300,100) = 100.₁₄ = min(100,200) = 100.₄₃ = min(200,100) = 100.₅₂ = min(200,400) = 200.₄₂ = min(100,200) = 100.₃₂ = min(200,100) = 100.₃₄ = min(100,100) = 100.

+ n - 1 = 9.

Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:(x) = 1*100 + 2*100 + 2*100 + 5*100 + 6*100 + 4*100 + 3*100 + 3*200 + 1*100 = 3000

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

₁ + v₁ = 1; 0 + v₁ = 1; v₁ = 1₂ + v₁ = 2; 1 + u₂ = 2; u₂ = 1₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2₃ + v₄ = 6; 2 + u₃ = 6; u₃ = 4₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1₄ + v₂ = 4; 1 + u₄ = 4; u₄ = 3₄ + v₃ = 3; 3 + v₃ = 3; v₃ = 0₅ + v₂ = 3; 1 + u₅ = 3; u₅ = 2₅ + v₅ = 1; 2 + v₅ = 1; v₅ = -1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(3;1): 4 + 1 > 3; ∆₃₁ = 4 + 1 - 3 = 2

Выбираем максимальную оценку свободной клетки (3;1): 3

Цикл приведен в таблице (3,1 → 3,4 → 1,4 → 1,1).

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2₃ + v₄ = 6; 2 + u₃ = 6; u₃ = 4₃ + v₁ = 3; 4 + v₁ = 3; v₁ = -1₂ + v₁ = 2; -1 + u₂ = 2; u₂ = 3₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1₄ + v₂ = 4; 1 + u₄ = 4; u₄ = 3₄ + v₃ = 3; 3 + v₃ = 3; v₃ = 0₅ + v₂ = 3; 1 + u₅ = 3; u₅ = 2₅ + v₅ = 1; 2 + v₅ = 1; v₅ = -1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;2): 3 + 1 > 3; ∆₂₂ = 3 + 1 - 3 = 1

(2;4): 3 + 2 > 4; ∆₂₄ = 3 + 2 - 4 = 1(1,1) = 1

Выбираем максимальную оценку свободной клетки (2;2): 3

Цикл приведен в таблице (2,2 → 2,1 → 3,1 → 3,2).

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

₁ + v₄ = 2; 0 + v₄ = 2; v₄ = 2₃ + v₄ = 6; 2 + u₃ = 6; u₃ = 4₃ + v₁ = 3; 4 + v₁ = 3; v₁ = -1₃ + v₂ = 5; 4 + v₂ = 5; v₂ = 1₂ + v₂ = 3; 1 + u₂ = 3; u₂ = 2₄ + v₂ = 4; 1 + u₄ = 4; u₄ = 3₄ + v₃ = 3; 3 + v₃ = 3; v₃ = 0₅ + v₂ = 3; 1 + u₅ = 3; u₅ = 2₅ + v₅ = 1; 2 + v₅ = 1; v₅ = -1

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j ≤ c_ij.

Минимальные затраты составят: F(x) = 2*200 + 3*100 + 3*200 + 4*100 + 3*100 + 3*200 + 1*100 = 2700