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

Пример решения симплекс-методом в столбцовой форме записи

(Существуют и другие формы записи симплекс-метода)

Решим прямую задачу линейного программирования симплексным методом, с использованием столбцовой формы (через калькулятор).
Определим максимальное значение целевой функции F(X) = 3x1+5x2+4x3 при следующих условиях-ограничений.
0.1x1+0.2x2+0.4x3≤1100
0.05x1+0.02x2+0.02x3≤120
3x1+x2+2x3≤8000
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
0.1x1 + 0.2x2 + 0.4x3 + 1x4 + 0x5 + 0x6 = 1100
0.05x1 + 0.02x2 + 0.02x3 + 0x4 + 1x5 + 0x6 = 120
3x1 + 1x2 + 2x3 + 0x4 + 0x5 + 1x6 = 8000
Переходим к столбцовой форме симплекс-метода. Выразим каждую переменную через небазисные.
x0 = 0-3(-x1)-5(-x2)-4(-x3)+0(-x4)+0(-x5)+0(-x6)
x1 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 1100+0.1(-x1)+0.2(-x2)+0.4(-x3)+1(-x4)+0(-x5)+0(-x6)
x5 = 120+0.05(-x1)+0.02(-x2)+0.02(-x3)+0(-x4)+1(-x5)+0(-x6)
x6 = 8000+3(-x1)+1(-x2)+2(-x3)+0(-x4)+0(-x5)+1(-x6)
Данной системе соответствует таблица T0.


0

-1

0

0

0

0

0

0

0

-1

0

0

0

0

0

0

0

-1

0

0

0

1100

0.1

0.2

0.4

1

0

0

120

0.05

0.02

0.02

0

1

0

8000

3

1

2

0

0

1

0

-3

-5

-4

0

0

0

В качестве начальной допустимой базы можно взять B0 = <4, 5, 6>.
Поскольку задача решается на максимум, то ведущий столбец выбирают по минимальному отрицательному числу в последней строке.

0

-1

0

0

0

0

0

0

0

-1

0

0

0

0

0

0

0

-1

0

0

0

1100

0.1

0.2

0.4

1

0

0

120

0.05

0.02

0.02

0

1

0

8000

3

1

2

0

0

1

0

-3

-5

-4

0

0

0

В качестве направляющего выберем столбец, соответствующий переменной x2.
Вычислим значения Di по строкам как частное от деления.

и из них выберем наименьшее:

Чтобы теперь выразить все переменные через небазисные, в выражении для x4 выразим x2 и подставим полученное выражение во все остальные равенства.
x2 = 5500+0.5x1+5x4+2x3+5x4+0x5+0x6
После приведения подобных получим:
x0 = 27500-0.5(-x1)+0(-x2)+6(-x3)+25(-x4)+0(-x5)+0(-x6)
x1 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x2 = 5500+0.5(-x1)+0(-x2)+2(-x3)+5(-x4)+0(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x5 = 10+0.04(-x1)+0(-x2)-0.02(-x3)-0.1(-x4)+1(-x5)+0(-x6)
x6 = 2500+2.5(-x1)+0(-x2)+0(-x3)-5(-x4)+0(-x5)+1(-x6)
Представим в виде таблицы T1:

0

-1

0

0

0

0

0

5500

0.5

0

2

5

0

0

0

0

0

-1

0

0

0

0

0

-1

0

0

0

0

10

0.04

0

-0.02

-0.1

1

0

2500

2.5

0

0

-5

0

1

27500

-0.5

0

6

25

0

0

Таким образом, очередная база равна B1 = <2, 5, 6>. Небазисные переменные следующие: N1 = <1, 3, 4>

0

-1

0

0

0

0

0

5500

0.5

0

2

5

0

0

0

0

0

-1

0

0

0

0

0

-1

0

0

0

0

10

0.04

0

-0.02

-0.1

1

0

2500

2.5

0

0

-5

0

1

27500

-0.5

0

6

25

0

0

В качестве направляющего выберем столбец, соответствующий переменной x1.
Вычислим значения Di по строкам как частное от деления.

и из них выберем наименьшее:

Чтобы теперь выразить все переменные через небазисные, в выражении для x5 выразим x1 и подставим полученное выражение во все остальные равенства.
x1 = 250+25x5+0x2+-0.5x3+-2.5x4+25x5+0x6
После приведения подобных получим:
x0 = 27625+0(-x1)+0(-x2)+5.75(-x3)+23.75(-x4)+12.5(-x5)+0(-x6)
x1 = 250+0(-x1)+0(-x2)-0.5(-x3)-2.5(-x4)+25(-x5)+0(-x6)
x2 = 5375+0(-x1)+0(-x2)+2.25(-x3)+6.25(-x4)-12.5(-x5)+0(-x6)
x3 = 0+0(-x1)+0(-x2)-1(-x3)+0(-x4)+0(-x5)+0(-x6)
x4 = 0+0(-x1)-1(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x5 = 0-1(-x1)+0(-x2)+0(-x3)+0(-x4)+0(-x5)+0(-x6)
x6 = 1875+0(-x1)+0(-x2)+1.25(-x3)+1.25(-x4)-62.5(-x5)+1(-x6)
Представим в виде таблицы T2:

250

0

0

-0.5

-2.5

25

0

5375

0

0

2.25

6.25

-12.5

0

0

0

0

-1

0

0

0

0

0

-1

0

0

0

0

0

-1

0

0

0

0

0

1875

0

0

1.25

1.25

-62.5

1

27625

0

0

5.75

23.75

12.5

0

Таким образом, очередная база равна B2 = <2, 1, 6>. Небазисные переменные следующие: N2 = <3, 4, 5>
Последняя строка не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант таблицы:

250

0

0

-0.5

-2.5

25

0

5375

0

0

2.25

6.25

-12.5

0

0

0

0

-1

0

0

0

0

0

-1

0

0

0

0

0

-1

0

0

0

0

0

1875

0

0

1.25

1.25

-62.5

1

27625

0

0

5.75

23.75

12.5

0

Оптимальный план можно записать так:
x2 = 5375
x1 = 250
x6 = 1875
F(X) = 5*5375 + 3*250 + 0*1875 = 27625
Примечание:
1. Для предотвращения зацикливания используется правило Бленда.
2. Столбец s, строка r и элемент trs называются направляющими.
3. Матрица T = t(ij) называется столбцовой симплекс-таблицей, соответствующей перестановке N.

Перейти к онлайн решению своей задачи

Транспортная задача
Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1234b
112436
243858
3276310
a4688 
Решить онлайн
Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Нелинейное программирование
Метод Лагранжа
Метод множителей Лагранжа
Решить онлайн
Курсовые на заказ