Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

Поиск первоначального опорного плана

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

-4x1-3x2-2x3+x4=-33
-3x1-2x2-x3+x5=-23
-x1-x2-2x3+x6=-12
xi≥0, i=1,6
F = 20х1 + 20х2 + 10х3 → min.

Запишем задачу в симплекс-таблицу (табл. 1).

Таблица 1

Базисное решение, соответствующее базису {x4, x5, x6} и равное (0; 0; 0; -33; 23; -12), не является допустимым ввиду отрицательности х4 < 0, x5 < 0, x6 < 0.

Сформулируем правило нахождения допустимого опорного плана.
Если в столбце свободных членов есть отрицательные элементы, выберите из них наибольший по модулю, а в его строке - любой отрицательный. Взяв этот элемент в качестве разрешающего пересчитайте таблицу по прежним правилам 2-5.
Если в полученной таблице все элементы столбца свободных членов стали положительны либо 0, то данное базисное решение можно взять в качестве первоначального опорного плана. Далее симплекс-методом дорешать задачу. Если в столбце свободных членов не все элементы неотрицательны, то еще раз воспользоваться этим правилом.
Проведем этот шаг для задачи о рационе. В качестве разрешающей строки табл. 1 нужно выбрать первую. А разрешающим элементом выберем, к примеру, элемент -4.

Таблица 2

базисные -х4 -х2 -х3 свободные
х1 1/4 3/4 ½ 33/4
х5 -3/4 1/4 ½ 7/4
х6 -1/4 -1/4 -3/2 -15/4
F 5 5 0 165
Заметим, что переменная х1 вошла в базис вместо х4, все вычисления осуществлялись по правилу 2-5. В правом столбце еще остался отрицательный элемент, воспользуемся правилом еще раз. Строка переменной х6 - разрешающая, а в качестве разрешающего элемента возьмем, к примеру, 3/2, здесь есть некоторая возможность выбора.

Таблица 2

базисные -х4 -х2 -х6 свободные
х1 -1/3 2/3 1/3 7
х5 -5/6 1/6 1/3 ½
х3 1/6 1/6 -2/3 5/2
F 5 5 0 165
Полученный базисный план х* = (х1, х2, х3, х4, х5, х6) = (7, 0, 5/2, 0, 1/2, 0) является допустимым и, к тому же, оказывается оптимальным, т.к. в индексной строке нет отрицательных элементов. Оптимальное значение целевой функции равно F* = 165. Действительно,
F = 20х1 + 20х2 + 10х3 = 20 · 7 + 0 + 10·5/2 = 140 + 25 = 165.

В этой задаче не пришлось улучшать найденный первоначальный опорный план, т.к. он оказался оптимальным. Иначе, мы должны были вернуться к III этапу.

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

Задача. Предприятие располагает тремя видами сырья и намеревается выпускать четыре вида продукции. Коэффициенты в таблице 3.12 указывают затраты соответствующего вида сырья на единицу определенного вида продукции, а также прибыль от реализации единицы продукции и общие запасы ресурсов. Задача: найти оптимальный план производства продукции, при котором будет обеспечена максимальная прибыль.

Таблица 3

Виды продукции →

Виды сырья ↓

I

II

III

IV

Запасы ресурсов

1

5

0,4

2

0,5

400

2

0

5

1

1

300

3

1

0

1

1

100

Прибыль

3

5

4

5

 

Составим математическую модель. Пусть х1, х2, х3, х4 - количество продукции I, II, III, IV вида соответственно в плане. Тогда количество используемого сырья и его запасы выразятся в неравенствах:
5x1+0.4x2+2x3+0.5x4≤400
5x2+x3+x4≤300
x1+x3+x4≤100
x1≥0, x2≥0, x3≥0, x4≥0
F = 3x1+5x2+ 4x3+ 5x4 → max.

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

Приведем задачу к канонической форме и к специальному виду, введя дополнительные переменные х5, х6, х7 в каждое из неравенств.
Очевидно, что, если первого ресурса необходимо для производства плановой продукции 5х1 + 0,4х2 + 2х3 + 0,5х4, то х5 обозначает просто излишки первого ресурса как разность между имеющимся запасом и требуемым для производства. Аналогично х6 и х7. Итак, дополнительные перемены задачи ЛП обозначают излишки сырья, времени, других ресурсов, остающихся в производстве данного оптимального плана.

Запишем задачу в таблицу 4, предварительно выписав ее каноническую форму:
5x1+0.4x2+2x3+0.5x4+x5=400
5x2+x3+x4+x6=300
x1+x3+x4+x7=100
xi≥0, i=1,7
-F = -3x1-5x2-4x3-5x4 → min.

I этап. Это задача специального вида, базис составляют переменные {х5, х6, х7}, правые части уравнений неотрицательны, план х = (0, 0, 0, 0, 400, 300, 100) - опорный. Он соответствует симплекс-таблице.

Таблица 4

базисные

-х1

-х2

-х3

-х4

свободные

х5

5

0,4

2

0,5

400

х6

0

5

1

1

300

х7

1

0

1

1 ←

100

-F

-3

-5

-4

-5 ↑

0

II этап. Проверим план на оптимальность. Так как в индексной F-строке есть отрицательные элементы, то план неоптимален, переходим к III этапу.

III этап. Улучшение опорного плана. Выберем в качестве разрешающего столбца четвертый, но могли бы выбрать и второй, т.к. в обоих (-5). Остановившись на четвертом, выберем в качестве разрешающего элемента 1, т.к. именно на нем достигается минимум соотношений . С разрешающим элементом 1 проводим преобразование таблицы по правилам 2-5 (табл. 5).

Таблица 5

Полученный план опять неоптимален, т.к. в F-строке есть отрицательный элемент -5. этот столбец разрешающий.

В качестве разрешающего элемента выбираем 5, т.к. .

Пересчитываем еще раз таблицу. Заметим, что пересчет удобно начинать с индексной строки, т.к. если в ней все элементы неотрицательны, то план оптимален, и чтобы его выписать, достаточно пересчитать столбец свободных членов, нет необходимости вычислять "внутренность" таблицы (табл. 6).

Таблица 6

базисные

-х1

-х6

-х3

-х7

свободные

х5

 

 

 

 

334

х2

 

 

 

 

40

х4

 

 

 

 

100

-F

1

1

1

4

700

План оптимален, т.к. в индексной строке нет отрицательных элементов, выписываем его.

IV этап. Базисные переменные {x5, x2, x4} принимают значения из столбца свободных членов, а свободные переменные равны 0. Итак, оптимальный план х* = (0, 40, 0, 100, 334, 0, 0) и F* = 700. Действительно, = 3х1 + 4х3 + 5х2 + 5х4 = 5 · 40 + 5 · 100 = 700. Т. е. для получения максимальной прибыли в 700 руб. предприятие должно выпускать изделия II вида в количестве 40 штук, IV - вида в количестве 100 штук, изделия I и III вида производить невыгодно. При этом сырье второго и третьего вида будет израсходовано полностью, а сырья первого вида останется 334 единицы (х5  = 334, х6 = 0, х7 = 0).

Учебно-методический
√ курсы переподготовки и повышения квалификации
√ вебинары
√ сертификаты на публикацию методического пособия
Подробнее
Библиотека материалов
√ Общеобразовательное учреждение
√ Дошкольное образование
√ Конкурсные работы
Все авторы, разместившие материал, могут получить свидетельство о публикации в СМИ
Подробнее
Инвестиции с JetLend

Удобный сервис для инвестора и заемщика. Инвестируйте в лучшие компании малого бизнеса по ставкам от 16,9% до 37,7% годовых.
Подробнее
Курсовые на заказ