МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное образовательное учреждение высшего образования

«САНКТ-ПЕТЕРБУРГСКИЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

КАФЕДРА № 41

ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

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

ОТЧЕТ О ПРАКТИЧЕСКОЙ РАБОТЕ №1

Линейное программирование

по курсу: Исследование операций

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР. №	4616				А.В.Павлов
			подпись, дата		инициалы, фамилия

Санкт-Петербург 2019

Цель работы: Решите задачу линейного программирования графическим методом и аналитически -симплекс-методом. Проверить решение c помощью Excel.

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

Вариант 7.

Ход работы:

Графический метод буду делать с помощью сайта Desmos. Ось x1 = x, x2=y

1)Ввожу первое уравнение . Т.к стоит знак значит закрашивает выше прямой.

Рисунок 1 – Уравнение №1

2)Ввожу второе уравнение . Т.к стоит знак значит закрашивает ниже прямой.

Рисунок 1 – Уравнение №1

3)Ввожу второе уравнение . Т.к стоит знак значит закрашивает выше прямой.

Рисунок 3 – Уравнение №3

Рисунок 4 – Пересечение

4) Добавлю вектор V=(3,1).

Рисунок 5 – Вектор

5) Сделаю перпендикулярную ему линию(3x+y=C) и буду двигать ее. Последнее пересечение будет когда C=18. Значит функция достигает макс значение в этой точке отмеченной на графике. Она принадлежит зеленному и синему уравнению. Составив и решив систему уравнения получим x1=4 и x2=6 . Тогда F=3*4+1*6=18

Рисунок 6 – Нахождение максимума

Симплекс-Метод:

Вводим дополнительные переменные x3,x4,x5 для каждого уравнения соответственно.

	B	X1	X2	X3	X4	X5
X3	-12	-2	-3	1	0	0
X4	2	-1	1	0	1	0
X5	2	2	-1	0	0	1
F(x0)	0	-3	-1	0	0	0

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

Разрешающий столбец: x2

Разрешающая строка: x3

Тогда

	B	X1	X2	X3	X4	X5
X2	4	0.7	1	-0.3	0	0
X4	4	0.7	1	-0.3	0	0
X5	4	0.7	1	-0.3	0	0
F(x0)	4	-2.3	0	-0.3	0	0

Пример расчета Жордана-Гаусса

Элемент = S - (А*В)/D

S – старый элемент, D - разрешающий элемент, А и В – старые элементы плана, образующие прямоугольник с элементами S и D.

	B	X1	X2	X3	X4	X5
X2	-12 / -3	-2 / -3	-3 / -3	1 / -3	0 / -3	0 / -3
X4	2-(-12 * 1)/-3	-1-(-2 * 1)/-3	1-(-3 * 1)/-3	0-(1 * 1):/3	1-(0 * 1)/-3	0-(0 * 1)/-3
X5	2-(-12 * -1)/-3	2-(-2 * -1)/-3	-1-(-3 * -1)/-3	0-(1 * -1)/-3	0-(0 * -1)/-3	1-(0 * -1)/-3
F(x0)	-12 / -3	-2 / -3	-3 / -3	1 / -3	0 / -3	0 / -3

Еще раз повторяем т.к есть отрицательные числа.

Разрешающий столбец: x1

Разрешающая строка: x4

Тогда

	B	X1	X2	X3	X4	X5
X2	3.2	0	1	-0.2	0.4	0
X1	1.2	1	-0	-0.2	-0.6	-0
X5	2.8	0	0	0.2	1.6	1
F(x0)	6.8	0	0	-0.8	-1.4	0

Еще раз повторяем т.к есть отрицательные числа.

Разрешающий столбец: x3

Разрешающая строка: x5

Тогда

	B	X1	X2	X3	X4	X5
X2	6	0	1	0	2	1
X1	4	1	0	0	1	1
X3	14	0	0	1	8	5
F(x0)	18	0	0	0	5	4

Ответ F=18, x1=6,x2=4

Решение в Excel:

Рисунок 7 – Настройка поиска решений

Рисунок 8 – Полученный результат

Составление двойственной задачи

Т.к. целевая функция минимизируется, то неравенства должны быть записаны с помощью знака . Поэтому, прежде чем приступать к построению двойственной задачи, необходимо упорядочить запись исходной, умножив неравенство на (-1):

Симплекс-Метод:

	B	Y1	Y2	Y3	Y4	Y5
Y4	-3	2	1	-2	1	0
Y5	-1	3	-1	1	0	1
F	0	-12	2	2	0	0

Разрешающий столбец: y3

Разрешающая строка: y4

	B	Y1	Y2	Y3	Y4	Y5
Y3	1.5	-1	-0.5	1	-0.5	0
Y5	-2.5	4	-0.5	0	0.5	1
F	-3	-10	3	0	1	0

Разрешающий столбец: y2

Разрешающая строка: y5

	B	Y1	Y2	Y3	Y4	Y5
Y3	4	-5	0	1	-1	-1
Y2	5	-8	1	-0	-1	-2
F	18	14	0	0	4	6

Ответ y3=5, y2=5,F=18

Решение в Excel

Рисунок 9 – Настройка расчета

Рисунок 10 – Результат работы

Fmax прямой задачи равен 18, тогда как Fmin двойственной задачи равен 18. Тогда по Теореме 1 “Для прямой и двойственной задач в силе одно и только одно из следующих утверждений. 1. Если одна из задач линейного программирования имеет конечный оптимум, то и двойственная к ней задача также имеет конечный оптимум, причём оптимальные значения линейных форм обеих задач совпадают, т. е. Fmax = Zmin или Fmin = Zmax. 2. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы. 3. Обе задачи не имеют решения, так как системы ограничений противоречивы.” - Все решено верно

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