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

Для построения модели двойственной задачи преобразуем столбцы системы неравенств прямой задачи в строки, заменяя величины запасов сырья прибылью α, β, γ, δ, а знаки "меньше" знаками "больше". Получим математическую модель двойственной задачи, где целевая функция достигает минимума:

       

Решение этой задачи получено в нижней строке последней симплекс-таблицы:

Wmin = 123,4375;   y1 = 1,0625;  y2 = 0; y3 = 0,7031.

Проверка:

Wmin = 50∙1,0625 + 40∙0 + 100∙0,70313 = 123,438 = Zmax.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3.Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трёх местах его получения, а запасы соответственно равны a1, a2, a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

;

Составить такой план перевозок, при котором общая себестоимость пере возок является минимальной. Задачу решить методом потенциалов.

	В1	В2	В3	В4
А1	6	7	2	4	90
А2	3	5	9	8	110
А3	10	2	6	7	100
	120	50	80	50

Решение: Проверим задачу на соответствие ресурсов и потребностей:

SAi = 90 + 110 + 100 = 300;   SВi = 120 + 50 + 80 + 50 = 300.

Т.к. SАi = SВi, то это транспортная задача закрытого типа.

Составляем первоначальный опорный план по методу минимального элемента. В верхний правый угол клеток вписана стоимость перевозки.

 

 

 

 

Вj Аi	В1 120	В2 50	В3 80	В4 50	Ui
А1 = 90	+ 6 -1	7   8	2 80	- 4 10	U1 = 0
А2 = 110	3 110	5   10	9   11	8   8	U2 = -4
А3 = 100	- 10 10	2 50	6   1	+ 7 40	U3 = 3
Vj	V1 = 7	V2 = -1	V3 = 2	V4 = 4	№1

Минимальная стоимость (2) в клетках А1В3 и А3В2 – закрываем потребности В3 и В2 поставкой из А1 и А3 и столбцы В2 и В3 исключаем из дальнейшего рассмотрения.

Следующий минимум в не исключённых столбцах и строках (3) в клетке А2В1 –  весь груз из А2 отправляем потребителю В1 и строку А2 исключаем из дальнейшего рассмотрения.

Следующий минимум (4) в клетке А1В4  –  остаток груза из А1 отправляем потребителю В4 и строку А1 исключаем из дальнейшего рассмотрения.

Осталось лишь 50 единиц груза у поставщика А3, которые распределяем между потребителями В1 и В4, закрывая их потребности.

Опорный план составлен. Число заполненных клеток должно быть:

m + n – 1 = 3 + 4 – 1 = 6,

Фактически число заполненных клеток 6, т.е. план не вырожден.

 Цена этого плана:

Z1 = 80∙2 + 10∙4 + 110∙3 + 10∙10 + 50∙2 + 40∙7 = 1010.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij – Vj;      Vj = Cij  – Ui,

где Cij – стоимость перевозок, записанная в правом верхнем углу клеток.

V3 = C13 – U1 = 2 – 0 = 2;     V4 = C14 – U1 = 4 – 0 = 4;       U3 = C34 – V4 = 7 – 4 = 3;  

V1 = C31 – U3 = 10 – 3 = 7;   V2 = C32 – U3 = 2 – 3 = -1;   U2 = C21 – V1 = 3 – 7 = -4;   

Определяем характеристики клеток, оставшихся свободными по формуле:

Eij = Cij – (Vj + Ui):  (вписаны в левый нижний угол):

Е11 = С11 – (V1 + U1) = 6 – (7 + 0) = -1; Е12 = С12 – (V2 + U1) = 7 – (-1+ 0) = 8;

Е22 = С22 – (V2 + U2) = 5 – (-1 – 4) = 10;   Е23 = С23 – (V3 + U2) = 9 – (2 – 4) = 11;

Е24 = С24 – (V4 + U2) = 8 – (4 – 4) = 8; Е33 = С33 – (V3 + U3) = 6 – (2 + 3) = 1;

Среди характеристик свободных клеток есть одна отрицательная в клетке Е11 = -1, следовательно, полученный план не оптимален и затраты на его реализацию могут быть уменьшены.

Строим для клетки А1В1 цикл (показан пунктиром) и перемещаем по циклу наименьшую из перевозок (10), находящихся в углах цикла, отмеченных знаком "минус".

Вj Аi	В1 120	В2 50	В3 80	В4 50	Ui
А1 = 90	6 10	7   8	2 80	4 0	U1 = 0
А2 = 110	3 110	5   9	9   10	8   7	U2 = -3
А3 = 100	10   1	2 50	6   1	7 50	U3 = 3
Vj	V1 = 6	V2 = -1	V3 = 2	V4 = 4	№1

Получаем новый план. Его цена:

Z2 = 10∙6 + 80∙2 + 110∙3 + 50∙2 + 50∙7 = 1000.

что лучше первоначального плана на 10 ден. единиц.

Т.к. теперь число заполненных клеток оказалось равно 5, что меньше m + n – 1 = 6, то план стал вырожденным. Для устранения вырожденности плана вписываем в клетку А1В4 значение 0.

Определив потенциалы строк и столбцов (U1 = 0) и характеристики свободных клеток по тем же формулам, устанавливаем, что этот план оптимален, т.к. среди характеристик свободных клеток нет отрицательных.

Zопт = Zmin =  Z2 = 1000.

Т.о. оптимальный план перевозок:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 4. Решить задачи целочисленного программирования геометрическим методом.

Решение: Построим в осях Х1ОХ2 граничные прямые, соответствующие исходным неравенствам. Каждая из этих прямых делит плоскость на две части, одна из которых удовлетворяет неравенству. Подставив в неравенство координаты любой точки, например (0;0), находим эту полуплоскость (показано стрелками). В результате получен четырёхугольник ОАВС, ограничивающий часть плоскости, удовлетворяющую всем ограничениям – это область допустимых решений – ОДР (заштрихован). Точка В – точка пересечения прямых, заданных уравнениями системы ограничений.

Уточним границу области допустимых решений задачи целочисленного программирования. Для этого придадим переменной х1 целочисленные значения от 0 до 6 (значение х1 = 7 уже вне ОДР) и вычислим соответствующие значения х2 из обеих уравнений.

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

 

 

 

 

х1	0	1	2	3	4	5	6
х2 из неравенства 2х1+ х2 ≤ 13	≤ 13	≤ 11	≤ 9	≤ 7	≤ 5	≤ 3	≤ 1
х2 из неравенства -2х1+ 3х2 ≤ 18	≤ 6	≤ 6,667	≤ 7,333	≤ 8	≤ 8,667	≤ 9,333	≤ 10
х2	6	6	7	7	5	3	1

Целевая функция в виде нулевой линии уровня проходит через начало координат. Перемещая эту линию параллельно самой себе в направлении вектора , увеличиваем значение F. Узел этой ступенчатой линии, через которую проходит последняя линия уровня, определит наибольшее значение целевой функции. Этой вершиной оказалась точка L, координаты которой Е(6; 0).

Т.о. значения х1 = 6 и х2 = 0 обеспечивают максимальное значение целевой функции в целых числах:

 

 

 

 

 

 

 

 

 

 

 

 

Задача 5.Целочисленное линейное программирование.

На предприятии производятся изделия четырёх наименований, обладающие различной ценностью. В производственном процессе используются три вида сырья. Информация о ресурсе сырья, о нормах их расхода на единичное изделие и ценности изделий приведена в табл. 1:

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	Изделие 1	Изделие 2	Изделие 3	Изделие 4
Ресурс 1	3	7	1	1	50
Ресурс 2	1	4	2	5	40
Ресурс 3	4	7	12	10	100
Ценность	6	7	9,5	7

Решение: Обозначим х1 – выпуск изделия 1; х2 – выпуск изделия 2; х3 – выпуск изделия 3; х4 – выпуск изделия 4.

Т.к. затраты ресурсов не могут превосходить их запасы сi, то математическая модель задачи предстанет в виде:

где целевая функция Z, обозначающая прибыль, стремится к максимуму:

Z = αх1 + βх2 + γх2 + δх2 = 6х1 + 7х2 + 9,5х3 + 7х4 → max;

Преобразуем систему неравенств в систему уравнений, введя дополнительные переменные х5; х6; х7, которые дают начальный  базис:

Т.к. исходные данные те же, что и в задаче 3.6. то приведём сразу матрицу её решения:

Сi Базис хi	Сi	В	6	7	9,5	7	0	0	0
			x1	x2	х3	х4	х5	х6	х7
х1	6	15,625	1,000	2,406	0,000	1,188	0,375	0,000	-0,031
х6	0	18,125	0,000	2,031	0,000	2,938	-0,125	1,000	-0,156
х3	9,5	3,125	0,000	-0,219	1,000	0,438	-0,125	0,000	0,094
Z ≥ 0		123,4375	0,000	5,359	0,000	4,281	1,0625	0,000	0,70313	№3

Т.о. х1 = 15,625; х2 = х4 = 0; х3 = 3,125; Zmax = 123,4375.

Т.к. требуется целочисленное решение, то округлим полученные значения в меньшую сторону до х1 = 15 и х3 = 3, тогда:

Z = 15·6 + 9,5·3 = 118,5.

Максимально ли это решение в целочисленном исчислении?

Наибольшая дробная часть 0,625 имеется в значении переменной х1, поэтому для строки х1 последней симплекс-таблицы составляем дополнительное ограничение:

х1 + 2,406х2 + 1,118х4 + 0,375х5 – 0,031х7 ≥ 15,625;

Берём только дробные части чисел. Для числа (-0,031) дробная часть [-0,031-(-1) = 0,969].