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

Задания для  самостоятельного решения

 

ВАРИАНТ №6

 

Задание 1

 

Минимизировать функцию при ограничениях:

 

Решить задачу графически.

 

РЕШЕНИЕ: Построим чертеж (см. чертеж), на котором отразим все ограничения-неравенства, включая условия неотрицательности. В итоге получаем множество допустимых планов, которое не является компактным. Его площадь бесконечна. Вектор есть градиент функции, которую требуется минимизировать. Исходя из интуитивно-графических соображений, на данном множестве не достигается ни минимум, ни максимум.

 

ОТВЕТ: Минимум целевой функции на заданном множестве не существует.

 

 

ЧЕРТЕЖ ПРИЛАГАЕТСЯ В ПРИЛОЖЕНИИ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задание 2

 

Для производства 4-х видов  продукции используется 3 вида сырья. Нормы расхода сырья (кг), его запасы (кг), ценность от реализации единицы продукции заданы таблицей.

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

 

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	Изделие 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

 

РЕШЕНИЕ:

Составим математическую модель задачи:

Пусть x_i – план выпуска изделий i-того вида, тогда модель принимает вид:

 

 

Задача линейного программирования сформулирована.

 

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

 

 

 

 

 

 

В векторно-матричной  форме задача имеет вид:

 

 

 

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

 

		х1	х2	x3	x4	у1	у2	у3	В	Лямбда
N п/п	Базис
1	y1	3	7	1	1	1	0	0	50	50/1=50
2	y2	1	4	2	5	0	1	0	40	40/2=20
3	y3	4	6	12	10	0	0	1	100	100/12=8,333
4	Z	-6	-7	-9,5	-7	0	0	0	0

 

Итак, опорный план таков:

 x₁ = 0 , x₂ = 0 , x₃ = 0 , x₄ = 0 , y₁ = 50 , y₂ = 40 , y₃ = 100

При этом Z = 0

 

Наличие в строке 4 хотя бы одного отрицательного числа означает неоптимальность текущего плана. По алгоритму мы должны из строки 4 выбрать «самый отрицательный» элемент. Это число -9,5 в столбце x_3.. В этом столбце ищем опорный элемент по принципу минимального неотрицательного λ_i = b_i / a_ij . Выбираем элемент в строке 3. Это число 12, оно выделено серым. Преобразуем симплекс-таблицу относительно выделенного элемента, получаем новую симплекс таблицу:

 

		х1	х2	x3	x4	у1	у2	у3	В	Лямбда
N п/п	Базис
1	y1	2,667	6,5	0	0,167	1	0	-0,083	41,667	15,625
2	y2	0,333	3	0	3,333	0	1	-0,167	23,333	70
3	х3	0,333	0,5	1	0,833	0	0	0,083	8,333	25
4	Z	-2,833	-2,25	0	0,917	0	0	0,792	79,167

 

Итак, имеем новый план:

 x₁ = 0 , x₂ = 0 , x₃ = 8,333 , x₄ = 0 ,  y₁ = 41,667 , y₂ = 23,333 , y₃ = 0

При этом Z = 79,167

 

Из-за наличия отрицательного числа -2,833 в строке 4 план опять не оптимален.

Это отрицательное число  определяет новый разрешающий столбец  – х_1. Анализируя «лямбды», находим наименьшее неотрицательное «лямбда» и выбираем новый разрешающий элемент – это будет число 2,667 в строке 1. Выделяем его серым цветом. Преобразуем симплекс-таблицу относительно выделенного элемента, получаем новую симплекс-таблицу:

 

		х1	х2	x3	x4	у1	у2	у3	В
N п/п	Базис
1	х1	1	2,438	0	0,063	0,375	0	-0,031	15,625
2	y2	0	2,188	0	3,313	-0,125	1	-0,156	18,125
3	х3	0	-0,312	1	0,813	-0,125	0	0,094	3,125
4	Z	0	4,656	0	1,094	1,063	0	0,703	123,4375

 

Итак, имеем новый план:

 x₁ = 15,625 , x₂ = 0 , x₃ = 3,125 , x₄ = 0 ,  y₁ = 0 , y₂ = 18,125 , y₃ = 0

При этом Z = 123,4375

 

В строке 4 нет отрицательных  чисел. Это означает, что план оптимален. Итак,

x₁ = 15,625 , x₂ = 0 , x₃ = 3,125 , x₄ = 0

При этом Z = 123,4375

 

То есть оптимальный  план таков: выпускать 15,625 единиц изделий 1-го вида и 3,125 единиц изделий 3-го вида, имея прибыль 123,4375. Изделия 2-го и 4-го видов НЕ ВЫПУСКАТЬ.

 

 

ТЕПЕРЬ СОСТАВИМ И РЕШИМ ДВОЙСТВЕННУЮ ЗАДАЧУ.

 

Требуется определить вектор U = {u₁, u₂, u₃}

 

 

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

 

Не обязательно применять  симплекс-метод для ее решения. Можно  воспользоваться соотношениями  двойственности. В основной задаче, решенной нами выше, первое и третье ограничения выполнялись как равенства, а второе – как неравенство. Поэтому можно утверждать u₂ = 0 , а первое и третье неравенства системы в двойственной задаче записать как равенства:

   (1)

 

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

 

Решая систему (1), находим:

 

Итак, решение двойственной задачи:

 

u₁ = 1,0625

u₂ = 0

u₃ = 0,703125

 

Целевая функция принимает  при этом значение:

 

Таким образом, соблюдается  основное соотношение двойственности:

 

 

Задание 3

 

Четыре предприятия  данного экономического района для  производства продукции используют три вида сырья. Потребности в  сырье каждого из предприятий  соответственно равны В1, В2, В3 и В4 единиц. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны А1, А2 и А3 единиц. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

 

 

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

 

 

Поставщики  и их запасы		Потребители и  потребительский спрос
		В1	В2	В3	В4
		120	50	80	50
А1	90	8	7	2	4
А2	110	3	5	9	8
А3	100	10	2	6	7

 

РЕШЕНИЕ:

Итак, следует решить задачу:

 

при ограничениях на перевозки:

 

где

 

Имеем закрытую транспортную задачу, решим ее методом потенциалов.

 

Составим базисный план, или т.н. первый опорный план. Воспользуемся методом наименьшего элемента и построим первый (опорный) план:

 

 

Это – допустимый план, его стоимость равна:

 

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

 , где V_i и W_j – т.н. потенциалы.

 

Получаем уравнения:

V₁ + W₃ = 2

V₁ + W₄ = 4

V₂ + W₁ = 3

V₃ + W₁= 10

V₃ + W₂ = 2

V₃ + W₄ = 7

 

Полагаем произвольно V₁ = 0, тогда:

V₁ = 0

V₂ = - 4

V₃ = 3

W₁ = 7

W₂ = - 1

W₃ = 2

W₄ = 4

 

Теперь для каждой свободной клетки плана перевозок  находим соотношение:

 

Получаем:

D₁₁ = 8 – (0 + 7) = 1 > 0  

D₁₂ = 7 – (0 + (-1)) = 8 > 0

D₂₂ = 5 – (-4 + (-1)) = 10 > 0

D₂₃ = 9 – (-4 + 2) = 11 > 0 

D₂₄ = 8 – (-4 + 4) = 8 > 0  

D₃₃ = 6 – (3 + 2) = 1 > 0    

 

План не содержит «плохих», или «отрицательных», клеток. Следовательно, он оптимален, его нельзя улучшить. Заметим, что первый же (т.е. опорный) план оказался оптимальным.

 

ОТВЕТ: - оптимальный план, его стоимость равна 1010.

 

 

 

 

 

Задание 4

 

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

 

РЕШЕНИЕ:

Построим чертеж (см. чертеж), на котором отразим все ограничения-неравенства, включая условия неотрицательности и целочисленности. В итоге получаем множество допустимых планов, которое выглядит как ступенчатая заштрихованная фигура (см. чертеж). Вектор есть градиент функции, которую требуется максимизировать. Исходя из графических соображений, на данном множестве максимум достигается в точке (6; 0) [её координаты удовлетворяют неравенствам системы, а также условиям неотрицательности и целочисленности]. Итак, x₁ = 6 , x₂ = 0 , F_MAX = 24 - оптимальное решение.