Оставить заявку:

Написать ВКонтакте
Viber: +375293830001
Отправить заявку на
e-mail

Телефон:
+375-29-383-00-01

Пример решения задачи. Симплексный метод решения ЗЛП

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

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

 

рубашка 1

рубашка 2

рубашка 3

Запасы

нитки (м.)

1

9

3

96

пуговицы (шт.)

20

10

30

640

ткань (

1

2

2

44

Прибыль (р.)

2

5

4

 

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

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

Через  и  количество рубашек 1-го, 2-го и 3-го вида, предназначенных к выпуску.

Тогда ограничения на ресурсы будут иметь следующий вид:

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

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

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

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

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

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

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

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

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

ведущий столбец соответствует

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

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

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

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

Ключевой столбец для 1-й итерации соответствует

Находим ключевую строку, для этого определяем:

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

Ключевой столбец для 2-й итерации соответствует

Находим ключевую строку, для этого определяем:

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

БП

cБ

Ao

x1

x2

x3

x4

x5

x6

Симплексные

 

 

 

 

 2

 5

 4

 0

 0

 0

отношения

0

x4

 0

96

1

 9

3

1

0

0

32/3

 

x5

 0

640

20

10

30

0

1

0

64

 

x6

 0

44

1

2

2

0

0

1

22

 

Fj - cj

0

-2

-5

-4

0

0

0

 

1

x2

 5

32/3

1/9

1

1/3

1/9

0

0

32

 

x5

 0

1600/3

170/9

0

80/3

-10/9

1

0

20

 

x6

 0

68/3

7/9

0

 4/3

-2/9

0

1

17

 

Fj - cj

160/3

-13/9

0

-7/3

5/9

0

0

 

2

x2

 5

5

-1/12

1

0

1/6

0

-1/4

--

 

x5

 0

80

 10/3

0

0

10/3

1

-20

24

 

x3

 4

17

7/12

0

1

-1/6

0

3/4

204/7

 

Fj - cj

93

-1/12

0

0

1/6

0

7/4

 

3

x2

 5

7

0

1

0

1/4

1/40

-3/4

 

 

x1

 2

24

1

0

0

1

3/10

-6

 

 

x3

 4

3

0

0

1

-3/4

-7/40

17/4

 

 

Fj - cj

95

0

0

0

1/4

1/40

5/4

 

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

Необходимо шить 24 рубашки 1-го вида, 7 рубашек 2-го вида и 3 рубашки 3-го вида.  При этом получаемая прибыль будет максимальна и составит 95 руб.

Сохранить ссылку на страницу в социальной сети:

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

Методы оптимальных решений. Решение задач недорого

Последнее обновление сайта:
18.09.2017
@mathminsk.com
2008-2017 Минск