Мгновенная связь через Вайбер или ВКонтакте в любое время
и на любом этапе заказа.
Общение с автором работ без посредников.
Опыт работы более 20 лет.
Помощь в решении ваших задач вы можете найти, отправив сообщение Вайбера или ВКонтакте Заполнение формы с личными данными и регистрация на сайте не нужна.
Телефон: 8(968)849-45-98

Симплекс-метод решения ЗЛП

Для решения задач линейного программирования предложено немало различных методов. Однако наиболее эффективным и универсальным среди них оказался симплекс-метод. При этом следует отметить, что при решении некоторых задач могут оказаться более эффективными другие методы. Симплекс-метод является основным и применимым к любой ЗПЛ в канонической форме.

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве , , , единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве  единиц, ресурса второго вида в количестве   единиц, ресурса третьего вида в количестве   единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве  ,  единиц, ресурсов второго вида в количестве    единиц, ресурсов третьего вида в количестве   единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно    тыс. руб.

  

Решение задачи

Построение модели

Через  обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.

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

Ограничения по материально-денежным ресурсам:

Кроме того, по смыслу задачи

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

Приведение к каноническому виду ЗЛП

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

Решение симплекс-методом

Заполняем симплексную таблицу.

Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.

Переход к следующей итерации осуществляем следующим образом: ведущий столбец находим:

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 7.

Теперь приступаем к составлению 1-й итерации: Вместо единичного вектора  вводим вектор .

В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.

Наличие в индексной строке 1-й итерации отрицательного числа -12/7 свидетельствует о том, что значение  можно увеличить. Это число определяет ключевой столбец. Находим ключевую строку, для этого определяем:

Разрешающим элементов является число . Вектор  выводим из базиса и вводим вместо него вектор . Получаем таблицу 2-й итерации.

БП

cБ

Ao

x1

x2

x3

x4

x5

x6

Симплексные

 

 

 

 

 8

 6

 4

 0

 0

 0

отношения

0

x4

 0

520

16

18

9

1

0

0

65/2

 

x5

 0

140

 7

7

2

0

1

0

20

 

x6

 0

810

9

2

1

0

0

1

90

 

fj - cj

0

-8

-6

-4

0

0

0

 

1

x4

 0

200

0

2

 31/7

1

-16/7

0

1400/31

 

x1

 8

20

1

1

2/7

0

1/7

0

70

 

x6

 0

630

0

-7

-11/7

0

-9/7

1

--

 

fj - cj

160

0

2

-12/7

0

8/7

0

 

2

x3

 4

1400/31

0

14/31

1

7/31

-16/31

0

 

 

x1

 8

220/31

1

27/31

0

-2/31

9/31

0

 

 

x6

 0

21730/31

0

-195/31

0

11/31

-65/31

1

 

 

fj - cj

7360/31

0

86/31

0

12/31

8/31

0

 

 

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

Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.

 

Двойственная задача ЛП

Запишем модель двойственной задачи.

Для построения двойственной задачи необходимо пользоваться следующими правилами:

1) если прямая задача решается на максимум, то двойственная — на минимум, и наоборот;

2) в задаче на максимум ограничения-неравенства имеют смысл , а в задаче минимизации — смысл .

3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;

4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;

5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;

6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство;

7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Транспонируем матрицу исходной задачи:

 

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

Решение двойственной задачи ЛП

Соответствие между переменными исходной и двойственной задачи:

|

|

|

|

|

|

На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования (выписываем из нижней строки):

Таким образом, наиболее дефицитным является ресурс первого вида. Его оценка максимальна и равна . Ресурс третьего вида является избыточным -его двойственная оценка равна нулю . Каждая дополнительно проданная единица товара 2-й группы будет снижать оптимальную прибыль на


Помощь в решении ваших задач по этому предмету вы можете найти, отправив сообщение в ВКонтакте, на Viber или заполнив форму. Стоимость решения домашней работы начинается от 150 р. за задачу (но не менее 300 р. за весь заказ). Подробное оформление. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 1000 р. за решение билета. Подробнее...


@100task.ru 2009-2017 Москва Спб НН