Математическое моделирование. 5

Задание №1. Построить на плоскости область решения системы линейных неравенств и найти максимальное и минимальное значение линейной функции в этой области.

Необходимо найти минимальное  и максимальное значение целевой функции z = 5x₁+4x₂, при системе ограничений:

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

1. На плоскости X₁0X₂ строят прямые, получаемые из системы ограничений.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂ + c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений для нахождения максимума функции или в направлении противоположном вектору N, для нахождения минимума.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

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

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

Рассмотрим целевую функцию  задачи z = 5x₁+4x₂ → min.

Построим вектор N=(5;4).Построим прямую, отвечающую значению функции z = 5x₁+4x₂ = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений  представляет собой многоугольник.

Прямая z(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (4) и (5), то ее координаты удовлетворяют уравнениям этих прямых:

x₂=0

x₁=0

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

Откуда найдем минимальное  значение целевой функции:

z(X) = 5*0 + 4*0 = 0

Рассмотрим целевую функцию  задачи z = 5x₁+4x₂ → max. Будем двигать прямую z = 5x₁+4x₂ параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Область допустимых решений  представляет собой многоугольник.

Прямая z(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

-x₁+x₂≤1

2x₁+x₂≤22

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

Откуда найдем максимальное значение целевой функции:

z(X) = 5*7 + 4*8 = 67

Задание №2.Торговое предприятие при продаже трех групп товаров (j=1,3) использует три вида материально-денежных ресурсов (i=1,3) в количестве единиц. Известны нормы затрат ресурсов на реализацию единицы товарооборота – и доход от реализации единицы товарооборота - . Требуется определить оптимальны план реализации товаров, обеспечивающий торговому предприятию максимальную прибыль симплексным методом.

Исходные данные по каждому  варианту приведены в таблице.

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

Определим максимальное значение целевой функции F(X) = 5x₁+3x₂+4x₃ при следующих условиях-ограничений.

3x₁+4x₂+x₃≤400

2x₁+3x₂+6x₃≤500

3x₁+4x₂+2x₃≤300

3x₁ + 4x₂ + 1x₃ + 1x₄ + 0x₅ + 0x₆ = 400

2x₁ + 3x₂ + 6x₃ + 0x₄ + 1x₅ + 0x₆ = 500

3x₁ + 4x₂ + 2x₃ + 0x₄ + 0x₅ + 1x₆ = 300

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений  относительно базисных переменных:

x₄, x₅, x₆,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,400,500,300)

Переходим к основному  алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1 и из них выберем наименьшее:

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении  ведущего столбца и ведущей строки.

После преобразований получаем новую таблицу:

Итерация №1.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x₃, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i3 и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (4.67) и находится на пересечении  ведущего столбца и ведущей строки.

После преобразований получаем новую таблицу:

Конец итераций: индексная  строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

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

x₄ = 164.29

x₃ = 64.29

x₁ = 57.14

F(X) = 5*57.14 + 4*64.29 = 542.86

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

Составим двойственную задачу к прямой задаче.

3y₁ + 2y₂ + 3y₃≥5

4y₁ + 3y₂ + 4y₃≥3

y₁ + 6y₂ + 2y₃≥4

400y₁ + 500y₂ + 300y₃ → min

y₁ ≥ 0

y₂ ≥ 0

y₃ ≥ 0

Решение двойственной задачи дает оптимальную систему оценок ресурсов.

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

Из теоремы двойственности следует, что Y = C*A^-1.

Составим матрицу A из компонентов  векторов, входящих в оптимальный  базис.

Определив обратную матрицу D = А^-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A^-1 расположена в столбцах дополнительных переменных.

Тогда Y = C*A^-1 =

Оптимальный план двойственной задачи равен:

y₁ = 0

y₂ = ¹/₇

y₃ = 1⁴/₇

Z(Y) = 400*0+500*¹/₇+300*1⁴/₇ = 542⁶/₇

Задание 4. Имеется три завода, объем производства которых соответственно равен тонн в сутки. Эти заводы ежедневно удовлетворяют потребности четырех строительных объектов в количествах тонн в сутки соответственно. Стоимость перевозки (тыс.руб.) перевозки единицы продукции с каждого завода на каждый строительный объект задана матрицей тарифов С=(С_ij), i=1..4, j=1..3. Найти такой план транспортировки груза, чтобы общие затраты на перевозки грузов были минимальными.

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij,    (1)

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

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

Стоимость доставки единицы  груза из каждого пункта отправления  в соответствующие пункты назначения задана матрицей тарифов

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

∑a = 30 + 40 + 80 = 150

∑b = 20 + 70 + 10 + 50 = 150

Этап I. Поиск первого  опорного плана.

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

2. Подсчитаем число занятых  клеток таблицы, их 5, а должно  быть m + n - 1 = 6. Следовательно, опорный план является вырожденным.

Строим новый план.

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

2. Подсчитаем число занятых  клеток таблицы, их 6, а должно  быть m + n - 1 = 6. Следовательно, опорный план является невырожденным.

Этап II. Улучшение  опорного плана.

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

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

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

Для этого в перспективную  клетку (1;3) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

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

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

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

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

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

Для этого в перспективную  клетку (3;4) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

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

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

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