Контрольная работа: Решение задач симплекс-методом

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

ЗАДАНИЕ 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.