Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
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
В качестве начальной допустимой базы можно взять B0 = <4, 5, 6>. Ей будет соответствовать следующая таблица.

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
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то ведущий столбец выбирают по минимальному отрицательному числу в последней строке.
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 по строкам как частное от деления: и из них выберем наименьшее:

Следовательно, 1-ая строка является ведущей. Вместо переменной x4 в план войдет переменная x2. Разделим 1-ую строку на 0.2 и прибавим к последней строке, а затем вычтем из всех остальных строк.
Представим расчет каждого элемента в виде таблицы:
Bx1x2x3x4x5x6
1100 / 0.2 = 55000.1 / 0.2 = 0.5 0.2 / 0.2 = 10.4 / 0.2 = 2 1 / 0.2 = 50 / 0.2 = 0 0 / 0.2 = 0
Таким образом, очередной базис равен B0= <2, 5, 6>.
5500 0.5 1 2 5 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по строкам как частное от деления: и из них выберем наименьшее:

Следовательно, 2-ая строка является ведущей. Вместо переменной x5в план войдет переменная x1. Разделим 2-ую строку на 0.04 и прибавим к последней строке, а затем вычтем из всех остальных строк.
Представим расчет каждого элемента в виде таблицы:
Bx1x2x3x4x5x6
10 / 0.04 = 2500.04 / 0.04 = 10 / 0.04 = 0-0.02 / 0.04 = -0.5-0.1 / 0.04 = -2.51 / 0.04 = 250 / 0.04 = 0
Таким образом, очередной базис равен B1= <2, 1, 6>.
Последняя строка не содержит отрицательных элементов. Найден оптимальный план.
Окончательный вариант таблицы:
5375 0 1 2.25 6.25 -12.5 0
250 1 0 -0.5 -2.5 25 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) = 3*250 + 5*5375 = 27625
Примечание:
1. Число операций в симплекс-методе не превосходит n!/((n-m)!*m!)
2. Решение х системы уравнений, в котором все небазисные переменные равны 0, называется базисным решение.
3. Если все компоненты базисного решения неотрицательны, то оно называется допустимым базисным решение или опорным планом.

Пример. Собственник располагает четырьмя видами ресурсов. Это, например, денежные средства, производственные помещения, оборудование, сырье. Ресурсы необходимо распределить между шестью видами предприятий. Предприятия различаются по экономическим условиям деятельности: месту расположения, системе налогообложения, стоимости электроэнергии, оплате труда и т. д., в связи , с чем имеют разные издержки производства. Относительные уровни издержек заданы в таблице.
Распределение ресурсов по предприятиям сопряжено с необходимостью ряда ограничений, которые могут быть описаны системой четырех уравнений с шестью неизвестными.
Смысл первого уравнений в нашем примере в том, что ресурс вида 1, общий ресурс которого составляет 16 единиц, может размещаться в количестве четырех единиц на предприятии первого типа и одной единицы – на предприятии четвертого типа. Аналогично раскрывается смысл второго и последующих уравнений. Последнее условие говорит о том, что число предприятий не может быть отрицательным. Необходимо определить, какое количество предприятий каждого типа следует иметь, чтобы общие издержки были минимальными.

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

Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Налоговый вычет на обучение
√ 120 тыс. руб. - максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя
Подробнее
Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Курсовые на заказ