Контрольная работа по «Методу оптимальных решений»

 

        IV

i	ба зис			4	1	2	3	0	0	0
											Q
1		2			0	1				0
2		0			0	0				1
3		1			1	0				0
4					0	0		-	-	0

 

При этом плане   max .

 

Задача № 9

 

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

a_i – запасы поставщиков, b_j – заявка потребителей.

 

Вариант 1:

          6    5    4   -

        

С =    8    8    2   6      a₁ = 500; a₂ = 300; a₃ = 100

 

          9  -     7    6

 

b₁ = 400;  b₂ = 200; b₃ = 150; b₄ = 250.

 

Решение:

 

постав- щики	Потребители
					запасы
	6	5	4	-	500
	8	8	2	6	300
	9	-	7	6	100
	400	200	150	250

 

 

 

Если суммарные запасы и потребности  совпадают  , то

называется закрытой моделью.

,      .

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

 

постав- щики	Потребители
					запасы
	(-) (400)	5 (+) (100)	4	М	500
	8	8 (-) (100)	2 (150)	6 (+) (50)	300
	9	М	7	6 (100)	100
	0 (+) (100)	0	0	0 (-) (100)	100
	400	200	150	250	1000

 

 

Для получения начального опорного плана применяем метод наименьших стоимостей: 

Проверим оптимальность полученного  плана перевозок через потенциалы (m + n - 1), 4 + 4 - 7 = 7 – число занятых клеток. Для каждой занятой клетки сумма потенциалов должна быть равной стоимости единицы перевозки.

                            Пусть   ,  ,  ,   ,

                                  то  ,   ,  ,   .

 

,   ,    ,

,     ,     ,

,     ,   .

 

 

 

Наличие отрицательных оценок показывает неоптимальность плана.

 

   0    0      5  М-3

         -1   0       0   0

          7   М-8   5  0

        -3     -2     4  0

 

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

постав- щики	Потребители
					запасы
	6 (300)	5 (200)	4	М	500
	8	8 (0)	2 (150)	6 (150)	300
	9	М	7	6 (100)	100
	0 (100)	0	0	0 (0)	100
	400	200	150	250	1000

 

Проверим оптимальность плана:

                            Пусть   ,  ,  ,   ,

                                  то  ,   ,  ,   .

 

,     ,     ,       ,

,   ,  ,

,    ,    ,

.

        План улучшен на 300 ед.    

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача № 10

 

    По плану производства  продукции предприятию необходимо  изготовить k изделий. Эти изделия могут быть изготовлены двумя технологическими способами. Стало известно, что при производстве х₁ изделий первым способом затраты равны:    mх₁ + х₁² руб.

    При изготовлении х2  изделий вторым способом они  составляют:

nх₂ + х₂² руб.

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

Вариант 1: m = 4,  n = 8, k = 180.

Решение:

Математическая постановка задачи состоит в определении минимального значения функции  ,    при условиях  , .

Сначала найдем решение задачи, используя  геометрическую интерпретацию. Областью допустимых  значений исходной задачи является отрезок прямой АВ, а линии уровня окружности с центром в точке Е (-2;-4).

Минимальное значение целевой функции  в точке Д, чтобы найти координаты точки Д воспользуемся тем, что угловой  коэффициент в окружности  . Точка Д совпадает с угловым коэффициентом прямой линии ,   К= - 1.

                                 

 

Найдем производные от , , ,  .

,  ,           отсюда

,    ,  ,  ,  то   .

,        .

Если предприятие изготовит 1 способом 91 изд. , 2 способом 89 изд., то общие затраты будут минимальны и составят  17286 руб.

Решаем задачу методом Лагранжа:

Составим функцию Лагранжа ,

Найдем частные производные  от , , :

,   ;

  ,   ;

,   ;

,     = 91,   = 89.

Д (91;89) – точка экстремума является подозрительной.

,       ,

4 = 364,       = 91,    = 89.

 

В данной точке  (91;89) – функция  имеет минимальное значение.