Контрольная работа по математическому программированию

Заказ: 1802/12

Контрольная работа №1

Предмет: математическое программирование

Вариант:18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача №1

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

 

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

Решение:

Исходная матрица имеет вид:

9	8	9	7
4	6	3	2
7	2	1	4
8	7	5	6

 

Шаг №1.

Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

2	1	2	0	7
2	4	1	0	2
6	1	0	3	1
3	2	0	1	5

Затем такую же операцию редукции проводим по столбцам, для чего в  каждом столбце находим минимальный  элемент:

0	0	2	0
0	3	1	0
4	0	0	3
1	1	0	1
2	1	0	0

После вычитания минимальных элементов  получаем полностью редуцированную матрицу.

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

В итоге получаем следующую матрицу:

[0]	[-0-]	2	[-0-]
[-0-]	3	1	[0]
4	[0]	[-0-]	3
1	1	[0]	1

 

Количество найденных нулей  равно k = 4. В результате получаем эквивалентную  матрицу Сэ:

0	0	2	0
0	3	1	0
4	0	0	3
1	1	0	1

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

[0]	[-0-]	2	[-0-]
[-0-]	3	1	[0]
4	[0]	[-0-]	3
1	1	[0]	1

 

Cmin = 9 + 2 + 2 + 5 = 18

Альтернативный вариант №2.

[-0-]	[-0-]	2	[0]
[0]	3	1	[-0-]
4	[0]	[-0-]	3
1	1	[0]	1

 

Cmin = 7 + 4 + 2 + 5 = 18

Получили два варианта решения:

1. Первый филиал выпускает первый вид продукции, второй филиал выпускает четвертый вид продукции, третий филиал выпускает второй вид продукции, а четвертый филиал выпускает третий вид продукции.
2. Первый филиал выпускает четвертый вид продукции, второй филиал выпускает первый вид продукции, третий филиал выпускает второй вид продукции, а четвертый филиал выпускает третий вид продукции.

При этом себестоимость продукции  будет 18 единиц.

Задача №2

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

А) Z-min

Б) Z-max

 

 

 

Решение:

Сначала определим многоугольник  решений. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки  неравенств заменим на знаки точных равенств и построим соответствующие  прямые:

X1	0	3
X2	2	1/5

X1	0	3
X2	0	7

 

Получили область OAB

Линии уровня 9x₁+15x₂=С, двигаясь вдоль вектора grad F =(9, 15) появятся в области допустимых решений в точке O, а покинут её в отрезке AB:

Найдем координаты точек A и B:

 

Получаем  

 

То есть A().

 

 

То есть B().

Найдем значение функции в этой точке F(B)=F(

F(A)=F(

Наименьшее значение функции F=F)=0

Ответ:  наименьшее значение функции  F= F)=0

наибольшеe  значение функции достигается в любой точке отрезка AB, например, F( или F(

Задача №3

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

 

 

Решение:

Запишем эту  задачу в виде основной задачи линейного  программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем три дополнительные переменные, в результате чего ограничения запишутся  в виде системы уравнений:

 

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

Составляем симплекс-таблицу:

	X1	X2	X3	X4	X5	X6	Свобод.
X4	1	-2	-4	1	0	0	20	20
X5	1	-2	2	0	1	0	10	10
X6	2	1	-2	0	0	1	24	12
F	-2	3	1	0	0	0	0

В функции F есть отрицательные коэффициенты, т.е. план не оптимален.

Разрешающий столбец x₁, разрешающая строка x₅. Генеральный элемент 1.

Получаем симплекс-таблицу:

	X1	X2	X3	X4	X5	X6	Свобод.
X4	0	0	-6	1	-1	0	10
X1	1	-2	2	0	1	0	10
X6	0	5	-6	0	-2	1	4	4/5
F	0	-1	5	0	2	0	20

В функции F есть отрицательные коэффициенты, т.е. план не оптимален.

Разрешающий столбец x₂, разрешающая строка x₆. Генеральный элемент 5.

Получаем симплекс-таблицу:

	X1	X2	X3	X4	X5	X6	Свобод.
X4	0	0	-6	1	-1	0	10
X1	1	0	-2/5	0	1/5	2/5	58/5
X2	0	1	-6/5	0	-2/5	2/5	4/5
F	0	0	19/5	0	8/5	1/5	104/5

В данной итерации найдено оптимальное  решение, т.к. в функции F нет отрицательных коэффициентов.

X=(), этом значение целевой функции Z= .

Ответ: max Z=Z()=

Решение в Excel находим с помощью надстройки Поиск решения.

В ячейках  B2-B4 будут полученные значения. В ячейках С2-С4 записываем формулы уравнений системы. В ячейке B7 записываем целевую функция. Затем выбираем надстройку ПОИСК РЕШЕНИЯ и заполняем поля как показано на рисунке.

 

Нажимаем выполнить и в заданных ячейках получаем искомые значения.

Файл с Excel прилагается.