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

Пример нахождения максимума функции симплексным методом

Здесь рассмотрен пример решения калькулятором в виде симплексной таблицы. Существуют и другие формы записи симплекс-метода

Пример №1. Предприятие выпускает 3 вида продукции А1, A2 и A3, для производства которых используется сырье трех видов. На изготовление единицы изделия А1 требуется затратить сырья каждого вида а11,а12,а13 кг соответственно, а для единицы изделия A2-a21,a22,a23 кг. Производство обеспечено сырьем каждого вида в количестве P1,P2,P3 кг. Стоимость единицы изделия А1 составляет С1 руб., А2 составляет С2 руб., а единицы изделия A3- С3 руб. Требуется составить план производства изделий А1, A2 и A3, обеспечивающий максимальную стоимость продукции. Решить:
А) геометрически;
В) симплекс-методом.
{a1j}={0.1;0.2;0.4}
{a2j}={0.05;0.02;0.02}
{a3j}={3;1;2}
P1=1100,P2=120,P3=8000
C1=3,C2=5,C3=4

Решение.
Математическая модель задачи:
0.1x1+0.2x2+0.4x3 ≤ 1100
0.05x1+0.02x2+0.02x3 ≤ 120
3x1+x2+2x3 ≤ 8000
3x1+5x2+4x3 → max
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных: x4,x5,x6
Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (1100,120,8000)

План Базис В x1 x2 x3 x4 x5 x6 min
1 x4 1100 0.1 0.2 0.4 1 0 0 5500
x5 120 0.05 0.02 0.02 0 1 0 6000
x6 8000 3 1 2 0 0 1 8000
Индексная строка F(X1) 0 -3 -5 -4 0 0 0 0
2 x2 5500 0.5 1 2 5 0 0 11000
x5 10 0.04 0 -0.02 -0.1 1 0 250
x6 2500 2.5 0 0 -5 0 1 1000
Индексная строка F(X2) 27500 -0.5 0 6 25 0 0 0
3 x2 5375 0 1 2.25 6.25 -12.5 0 11000
x1 250 1 0 -0.5 -2.5 25 0 250
x6 1875 0 0 1.25 1.25 -62.5 1 1000
Индексная строка F(X3) 27625 0 0 5.75 23.75 12.5 0 0

Итерация №0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: и из них выберем наименьшее:
Следовательно,1-ая строка является ведущей. Разрешающий элемент равен 0.2 и находится на пересечении ведущего столбца и ведущей строки. Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=0.2. На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ





















Итерация №1
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления и из них выберем наименьшее:

Следовательно,2-ая строка является ведущей
Разрешающий элемент равен 0.04 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x5 в план 2 войдет переменная x1.
Строка, соответствующая переменной x1 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=0.04
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x1 плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
Конец итераций: найден оптимальный план
Оптимальный план можно записать так: x2 = 5375, x1 = 250, x6 = 1875. F(X) = 27625

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

Пример №2. Наиболее эффективным для хозяйства является выращивание трех культур: озимой пшеницы, проса, гречихи. Ожидаемый уровень урожайности этих культур, себестоимость центнера продукции, нормы внесен6ия удобрений и затраты труда в расчете на единицу продукции, приведенные в соответствии с ожидаемым уровнем урожайности, заданы таблицей. Известны и наиболее вероятные цены фактической реализации центнера продукции.
Критерий оптимальности – максимум прибыли от реализации данных видов продукции.

Введем систему обозначений:
Х1 – искомая площадь посева озимой пшеницы (га);
Х2 – искомая площадь посева проса (га);
Х3 – искомая площадь посева гречихи (га).

Ограничения:
1. Общая площадь посева культур (га)
Х123≤2000
2. Затраты труда (чел.-дни)
Если за единицу измерения неизвестных принят 1 га, то соответственно необходимо рассчитать все нормативы на эту единицу. Затраты труда даны по условию задачи в расчете на 1 ц продукции , но, зная урожайность , легко пересчитать нормативы затрат труда в расчете на 1 га посева. Таким образом ограничение запишется так:
40x1 + 50x2 + 45x3 ≤ 14600
3. Расход минеральных удобрений (ц д.в.)
0.8x1 + 0.6x2 + x3 ≤ 1600

Целевая функция:
Поскольку в качестве критерия оптимальности выступает максимум прибыли, то необходимо рассчитать соответствующие коэффициенты данной целевой функции. В расчете на 1 га прибыль составит соответственно: (11.6-6)*30, (8-7)*18,(30-11)*15 рублей. Прибыль = выручка - себестоимость.
Целевая функция задач при этом будет выглядеть так:
(11.6-6)*30x1 + (8-7)*18x2 + (30-11)*15x3 = max

Таким образом математическая модель задачи выглядит так:
Х123≤2000
9,6Х1+7Х2+7,2Х3≤14600
0,6Х1+0,4Х2+0,8Х3≤1600
Z=168Х1+18Х2+285Х3=max

Далее решается согласно алгоритму симплексного метода.

Поиск наибольшего значения

1. Для изготовления цемента двух видов используется сырье трех видов. Запасы сырья известны и равны соответственно: 264, 136 и 266 т. Количество сырья каждого вида, необходимое для производства единицы цемента первого вида соответственно равны:  12, 4 и 3. Для цемента второго вида: 3, 5 и 14. Прибыль от реализации цемента первого вида составляет 6 у.е., от цемента второго вида  - 4 у.е. Составить план, обеспечивающий наибольшую прибыль производству:
а) записать математическую модель;
б) решить задачу графическим методом;
в) решить задачу симплекс-методом;
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.

Решение:
а) математическая модель;
x1 – производство цемента первого вида;
x2 – производство цемента второго вида;
12x1 + 3x2 ≤ 264
4x1 + 5x2 ≤ 136
3x1 + 14x2 ≤ 266
x1 ≥ 0, x2 ≥ 0
Целевая функция:
6x1 + 4x2 → max
б) решим задачу графическим методом;
Необходимо найти максимальное значение целевой функции F = 6X1+4X2 => max, при системе ограничений:
12x1+3x2≤264 (1)
4x1+5x2≤136 (2)
3x1+14x2≤266 (3)
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).


Обозначим границы области многоугольника решений.
Рассмотрим целевую функцию задачи F = 6X1+4X2 => max.
Построим прямую, отвечающую значению функции F = 0: F = 6X1+4X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.
Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых 1 и 2, то ее координаты удовлетворяют уравнениям этих прямых: 12x1+3x2≤264 4x1+5x2≤136
Решив систему уравнений, получим:
x1 = (264-3x2)/12
4(264-3x2)/12+5x2 = 136
x1 = 19, x2 = 12
Откуда найдем максимальное значение целевой функции: F(X) = 6*19 + 4*12 = 162
Таким образом, чтобы получить максимальную прибыль необходимо выпускать 19 т. цемента 1-го вида, и 12 т. цемента 2-го вида.

в) решить задачу симплекс-методом;
Решим прямую задачу линейного программирования  симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 6x1+4x2 при следующих условиях-ограничений.
12x1+3x2≤264
4x1+5x2≤136
3x1+14x2≤266
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
12x1 + 3x2 + 1x3 + 0x4 + 0x5 = 264
4x1 + 5x2 + 0x3 + 1x4 + 0x5 = 136
3x1 + 14x2 + 0x3 + 0x4 + 1x5 = 266
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,264,136,266)

ПланБазисВx1x2x3x4x5
0x3264123100
x413645010
x5266314001
Индексная строкаF(X0)0-6-4000
Переходим к основному алгоритму симплекс-метода.
ПланБазисВx1x2x3x4x5min
1x326412310022
x41364501034
x526631400188.67
Индексная строкаF(X1)0-6-40000
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Diпо строкам как частное от деления и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей
Разрешающий элемент равен 12 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x3в план 1 войдет переменная x1
Строка, соответствующая переменной x1в плане 1, получена в результате деления всех элементов строки x3плана 0 на разрешающий элемент РЭ=12
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
ПланБазисВx1x2x3x4x5min
2x12210.250.08330088
x44804-0.33331012
x5200013.25-0.250115.09
Индексная строкаF(X2)1320-2.50.5000
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Diпо строкам как частное от деления и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей
Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки
Формируем следующую часть симплексной таблицы.
Вместо переменной x4в план 2 войдет переменная x2
Строка, соответствующая переменной x2в плане 2, получена в результате деления всех элементов строки x4плана 1 на разрешающий элемент РЭ=4
На месте разрешающего элемента в плане 2 получаем 1.
В остальных клетках столбца x2  плана 2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2.
Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
ПланБазисВx1x2x3x4x5
3x119100.1042-0.06250
x21201-0.08330.250
x541000.8542-3.311
Индексная строкаF(X3)162000.29170.6250

Оптимальный план можно записать так: x1 = 19, x2 = 12, x5 = 41; F(X) = 6*19 + 4*12 = 162
г) к исходной задаче записать двойственную и решить ее, используя соотношение двойственности и решение исходной.
Составим двойственную задачу к прямой задаче.
12y1+4y2+3y3≥6
3y1+5y2+14y3≥4
264y1+136y2+266y3 => min
y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Решение двойственной задачи дает оптимальную систему оценок ресурсов.
Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи.
Из первой теоремы двойственности следует, что Y = C*A-1.
Составим матрицу A из компонентов векторов, входящих в оптимальный базис.

Определив обратную матрицу А-1 через алгебраические дополнения, получим:

Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных .
Тогда Y = C*A-1 =
Оптимальный план двойственной задачи равен: y1 = 0.29, y2 = 0.62, y3 = 0
Z(Y) = 264*0.29+136*0.62+266*0 = 162
2. На трех станциях отправления сосредоточен однородный груз, который следует перевезти в четыре пункта назначения, имеющих потребность в этом грузе. Стоимость перевозок единицы груза от каждой станции до каждого пункта назначения считается известной и содержится в таблице. Требуется составить такой план перевозок, при котором их общая стоимость окажется минимальной.
Решить транспортную задачу методом потенциалов.

Посмотреть решение

Требуются авторы студенческих работ!
  • регулярный поток заказов;
  • стабильный доход
Подробнее
Учебно-методический
  • курсы переподготовки и повышения квалификации;
  • вебинары;
  • сертификаты на публикацию методического пособия
Подробнее
Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
Курсовые на заказ