Лабораторная работа № 24 Задача линейного программирования

Пусть задана следующая задача линейного программи­рова­ния.

Предположим, что для производства двух видов продукции А и В можно использовать только материал трех сортов. При этом на изготовление единицы изделия вида А расходуется (19 – — 0, 02k) кг материала первого сорта, (20 + 0,03k) кг материала второго сорта и (20 + 0,02k) кг материала третьего сорта. На изго­товление единицы изделия вида В расходуется (24 + 0,1k) кг материала первого сорта, (42 – 0, 05k) кг материала второго сорта, (20 – 0,02k) кг материала третьего сорта. На складе фаб­рики имеется всего материала первого сорта (5100 + k) кг, материала второго сорта (7200 + 2k) кг, материала третьего сорта (5000 + 3k) кг. От реализации готовой продукции вида А фабрика имеет прибыль (5 + 0,1k) руб., а от продукции вида В прибыль (6 + 0,2k) руб. Здесь k – номер фамилии студента в журнале преподавателя. Определить максимальную прибыль от реализации всей про­дук­ции видов А и В.

Задание. Составить математическую модель задачи. Решить задачу геометрически, а также симплекс – методом.

Лабораторная работа № 25 Транспортная задача

Дана следующая транспортная задача. На трех базах Б₁, Б₂ и Б₃ находится однородный груз в количестве соответственно: а₁, а₂ и а₃ условных единиц. Этот груз необходимо перевести на пять предприятий П₁, П₂, П₃, П₄ и П₅, потребности которых составля­ют соответственно b₁, b₂, b₃, b₄ и b₅ условных единиц. Стоимость пе­ревозки одной условной единицы груза с базы Б_i на пред­прия­тие П_i составляет c_ij руб. Эти стоимости указаны в табл. 4.

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

Таблица 4

Базы	Предприятия					Запасы на базах
	П1	П2	П3	П4	П5
Б1 Б2 Б3	c11 c21 c31	c12 c22 c32	c13 c23 c33	c14 c24 c34	c15 c25 c35	а1 а2 а3
Потребность предприятий	b1	b2	b3	b4	b5

Задание. Составить математическую модель сформулированной задачи. Решить задачу при следующих данных:

a₁ = 920 + 2k; a₂ = 780 + 3k; a₃ = 840 + 4k;

b₁ = 510 + 3k; b₂ = 480 + 2k; b₃ = 470 + k;

b₄ = 530 + 2k; b₅ = 550 +k.

Матрица стоимости перевозок имеет вид:

где k – номер фамилии студента в журнале преподавателя, m = k (mod 3), т. е. m равно остатку от деления k на три.

Лабораторная работа № 26 Метод наискорейшего спуска

Метод применяется для нахождения минимума некоторой функции = f(x₁, x₂, ..., x_n), заданной в евклидовом про­ст­ран­ст­ве, где = (x₁, x₂, ..., x_n) — вектор. Численные методы отыс­ка­ния экстремума функции состоят в построении последова­тельности векторов {}, удовлетворяющих условию: f() > > f(⁽¹⁾) > ... > f(⁽ⁿ⁾). Методы построения таких последо­ватель­ностей называются методами спуска. В этих методах элементы последовательности {} вычисляются по формуле

(k = 0,1,2,...…),

где вектор ^(k) определяет направление спуска; — длина шага в данном направлении.

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

(k = 0,1,2,...),

где в точке .

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

,

т. е. на каждом шаге решается одномерная задача минимизации. Для решения этой задачи можно применить метод золотого сечения. Отметим, что на двух последовательных шагах решения направления спуска ортогональны. Для окончания процесса счета можно использовать различные критерии. Например, счет можно прекратить, если выполняется условие

 grad f(^(k+1))  <  , где  grad f  = . В этом случае полагаем .

Задание. Методом наискорейшего спуска найти минимум функции где — номер фамилии студента в журнале преподавателя. Значения и , в которых функция достигает минимума, найти с точ­ностью  = 0,0001. Начальное приближение найти методом слу­чайного поиска.