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

Автор работы: Пользователь скрыл имя, 14 Ноября 2013 в 09:24, контрольная работа

Описание работы

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

Файлы: 1 файл

вариант 6.doc

— 126.00 Кб (Скачать файл)

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

 

ВАРИАНТ №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

 

 

РЕШЕНИЕ:

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

Пусть xi – план выпуска изделий 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

 

 

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

 x1 = 0 , x2 = 0 , x3 = 0 , x4 = 0 , y1 = 50 , y2 = 40 , y3 = 100

При этом Z = 0

 

Наличие в строке 4 хотя бы одного отрицательного числа означает неоптимальность текущего плана. По алгоритму мы должны из строки 4 выбрать «самый отрицательный» элемент. Это число -9,5 в столбце x3.. В этом столбце ищем опорный элемент по принципу минимального неотрицательного λi = bi / aij . Выбираем элемент в строке 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

 

 

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

 x1 = 0 , x2 = 0 , x3 = 8,333 , x4 = 0 ,  y1 = 41,667 , y2 = 23,333 , y3 = 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


 

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

 x1 = 15,625 , x2 = 0 , x3 = 3,125 , x4 = 0 ,  y1 = 0 , y2 = 18,125 , y3 = 0

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

 

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

x1 = 15,625 , x2 = 0 , x3 = 3,125 , x4 = 0

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

 

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


 

 

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

 

Требуется определить вектор U = {u1, u2, u3}

 

 

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

 

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

   (1)

 

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

 

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

 

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

 

u1 = 1,0625

u2 = 0

u3 = 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


 

РЕШЕНИЕ:

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

 

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

 

где

 

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

 

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

 

 

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

 

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

 , где Vi и Wj – т.н. потенциалы.

 

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

V1 + W3 = 2

V1 + W4 = 4

V2 + W1 = 3

V3 + W1= 10

V3 + W2 = 2

V3 + W4 = 7

 

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

V1 = 0

V2 = - 4

V3 = 3

W1 = 7

W2 = - 1

W3 = 2

W4 = 4

 

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

 

Получаем:

D11 = 8 – (0 + 7) = 1 > 0  

D12 = 7 – (0 + (-1)) = 8 > 0

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

D23 = 9 – (-4 + 2) = 11 > 0 

D24 = 8 – (-4 + 4) = 8 > 0  

D33 = 6 – (3 + 2) = 1 > 0    

 

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

 

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

 

 

 

 

 

Задание 4

 

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

 

РЕШЕНИЕ:

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

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