Практическая работа по "Программированию"

15 вариант

Задача №1 Задача линейного программирования.

Дана задача линейного программирования.

Z(x) = [pic 1]

[pic 2]

.[pic 3]

 Необходимо:

1. Решить исходную задачу графическим методом.
2. Составить двойственную задачу к исходной.
3. Найти решение двойственной задачи, используя решение исходной задачи.

Решение:

В первую очередь построим область ограничений исходной задачи.

1. 10[pic 4]

     [pic 5]

Графиком функции является прямая.

1. [pic 8]

     [pic 9]

Графиком функции является прямая.

1. [pic 12]

[pic 13]

[pic 14]

Графиком функции является прямая.

1. 2[pic 17]

[pic 18]

       [pic 19]

[pic 22]

Рис.1. График к задаче 1

Следующим шагом необходимо построить вектор градиент, который строится путем вычисления частных производных по x1 и х2 целевой функции исходной задачи. Координаты вектора градиента являются {1;5}. На графике (рис.1) вектор градиент отмечен .[pic 23]

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

Чтобы найти оптимальное значение исходной задачи, нам необходимо использовать решение системы, которая состоит из уравнений, пересечением которых является х*:

[pic 24]

,[pic 25]

значит, целевая функция исходной задачи будет принимать оптимальное значение в точке (0;5). Тогда оптимальное значение в этой точке равно:

Z(x*) = 0+25=25

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

10[pic 26]

[pic 27]

, [pic 28][pic 29]

.[pic 30]

Опираясь на первую теорему двойственности, можно сделать вывод, что:

Z(x*)= G(y*)=25.

Основываясь на вторую теорему двойственности составим систему уравнений:

( ) = 0, i=[pic 31][pic 32][pic 33]

[pic 34]

[pic 35]

[pic 36]

[pic 37]

,[pic 38]

Следовательно, y2* равно нулю, y3* равно нулю, y4* равно нулю, а y1* может принимать любые значения, что найти значение y1* используем решение системы уравнений, подставив в ограничения двойственной задачи:

[pic 39]

[pic 40]

[pic 41]

Значит решением двойственной задачи является точка . Сделаем проверку:[pic 42]

 G ([pic 43]

Вывод: решением исходной задачи является точка х*(0;5), оптимальное значение исходной задачи равно 25. Решением двойственной задачи является y*(2,5;0;0;0), а оптимальное значение двойственной задачи так же равно 25.

Задача №2 Транспортная задача (вариант 250).

Известно, что на складах А1, А2, А3 имеются запасы продукции в количестве 160т, 155т, 85т соответственно. Потребители В1, В2, В3, В4 должны получить продукцию в количестве 115т, 85т, 130т, 70т.

Расходы по перевозке 1т продукции заданы матрицей: (сij- стоимость одной перевозки).

[pic 44]

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

Решение:

Для начала проверим, является ли данная транспортная задача закрытой.

Используем формулу:

.[pic 45]

[pic 46]

[pic 47]

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

Следующим шагом будет составление таблицы базисной точки.

Таблица1-базисная точка