Предприятию нужно перевести со склада по железной дороге изделия трех различных видов: Изделий I –го вида не более 640, изделий II-го вида не более 800, изделий III-го вида не более 860.
Подразделение железной дороги может для этой перевозки выделить специально оборудованные вагоны двух типов А и В. Для полной загрузки вагона следует помещать в него изделия всех трех видов. При этом в вагон типа А входят 1 изделий I-го вида, 5 изделий II-го вида, 3 изделий III-го вида; в вагон типа B входят 4 изделий I-го вида, 2 изделий II-го вида, 5 изделий III-го вида.
Экономия от перевозки груза в вагоне типа А составляет 20 руб., в вагоне типа В – 13 руб.
Сколько вагонов каждого типа следует выделить для перевозки, чтобы суммарная экономия от перевозки груза была наибольшей?
Задачу решить симплекс методом путем преобразования симплекс- таблиц и геометрическим методом.
Решение
4 640
II 5 2 800
III 3 5 860
Экономия 20 13
Обозначим: x1 (ед) – количество вагонов типа А; x2 (ед) – количество вагонов типа В; F (руб) – суммарная экономия от перевозки груза.
Совокупность неизвестных (х1, х2) называется планом производства.
Очевидно, должны соблюдаться условия неотрицательности: x1 x2 .
Составим ограничения по изделиям каждого вида. Для сырья I вида: х1+4х2≤640. Для сырья II вида: 5х1+2х2≤800. Для сырья III вида: 3х1+5х2≤860.
Суммарная экономия от перевозки груза F=20x1+13x2→max.
Составим математическую модель:
F=20x1+13x2→max.
х1+4х2≤640
5х1+2х2≤800
3х1+5х2≤860
x1 x2
Приведем математическую модель к каноническому виду. Это достигается введением в каждое неравенство дополнительных неотрицательных переменных: x3 x4 x5 . Их экономический смысл – недоиспользованное сырье каждого вида.
Получим:
F=20x1+13x2→max.
х1+4х2+х3=640
5х1+2х2+х4=800
3х1+5х2+х5=860
x1 x2
Составим симплекс-таблицу 1-го шага.
При этом опорным решением является ; х* = (0,0,640,800,860), F(x*)=0
Базис x1 x2 x3 x4 x5 B
x3 1 4 1 0 0 640
x4 5 2 0 1 0 800
x5 3 5 0 0 1 860
F -20 -13 0 0 0 0
В последней строке cj имеются две отрицательные оценки, значит, найденное решение не является оптимальным и его можно улучшить.
В качестве разрешающего столбца берем столбец при x1, т.к. он содержит максимальный по модулю отрицательный элемент в индексной строке. Для выбора разрешающей строки рассмотрим отношения и выберем минимальное среди них:
min (640 : 1 , 800 : 5 , 860 : 3 ) = 160,
что указывает навторую строку. Разрешающий элемент равен 5 (элемент, стоящий на пересечении строки при x4 и столбца при x1 ).
Вводим в столбец базисных переменных x1 и выводим x4 .
Составляем симплекс-таблицу 2-го шага
Базис x1 x2 x3 x4 x5 B
x3 0 18/5 1 -1/5 0 480
x1 1 2/5 0 1/5 0 160
x5 0 19/5 0 -3/5 1 380
F 0 -5 0 4 0 3200
При этом опорным решением является х* = (160,0,480,0,380), F(x*)=3200
В последней строке cj имеется отрицательная оценка, значит, найденное решение не является оптимальным и его можно улучшить.
Разрешающим столбцом является столбец с переменной x2 . Для выбора разрешающей строки рассмотрим отношения и выберем минимальное среди них
min (480 : 18/5 , 160 : 2/5 , 380 : 19/5 ) = 100
что указывает на третью строку
. На пересечении разрешающего столбца при x2 и разрешающей строки при x5 расположен разрешающий элемент и он равен 19/5 .
Составляем симплекс-таблицу 3-го шага.
Базис x1 x2 x3 x4 x5 B
x3 0 0 1 7/19 -18/19 120
x1 1 0 0 5/19 -2/19 120
x2 0 1 0 -3/19 5/19 100
F 0 0 0 61/19 25/19 3700
Этой таблице соответствует опорное решение: х*=(120, 100, 120, 0, 0).
Оно является оптимальным, т.к. все коэффициенты F –строки в таблице неотрицательны. Максимальное значение целевой функции:
F(x*)=3700.
Оно достигается при x1=120; x2=100. Дополнительные переменные при этом равны: x3=120; x4=0; x5=0. Это означает, что сырье второго и третьего видов используется полностью, а сырье первого вида остается не использованным в количестве 120 ед.
Ответ. Для перевозки нужно выделить 120 вагонов А и 100 вагонов В, чтобы получить максимальную экономию в размере 3700 руб.
Решение задачи геометрическим методом
Вернемся к исходной математической модели в симметричном виде:
F=20x1+13x2→max.
х1+4х2≤640
5х1+2х2≤800
3х1+5х2≤860
x1 x2
Каждому неравенству модели соответствует полуплоскость. Для графического изображения полуплоскостей строим их граничные прямые по двум произвольно выбранным точкам. Для этого задаем одну из переменных произвольно, а другую вычисляем из соответствующего уравнения.
Уравнения граничных прямых:
1) х1+4х2=640 (l1)
Если х1=0, то х2=160
Если х2=0, то х1=640
2) 5х1+2х2=800 (l2)
Если х1=0, то х2=400
Если х2=0, то х1=160
3) 3х1+5х2=860(l3)
Если х1=0, то х2=172
Если х2=0, то х1≈286.7
Строим прямые по найденным точкам в выбранной системе координат. Масштабы на осях выбираем, исходя из удобств построения.
Общая часть всех полуплоскостей, с учетом условий неотрицательности, образует замкнутый выпуклый многоугольник OABCD. В данной задаче это пятиугольник, отмеченный на чертеже желтым цветом.
Для нахождения оптимального плана обратимся к целевой функции
F=20x1+13x2→max.
На графике целевая функция изображается с помощью линий уровня:
F = C (const).
Придавая постоянной С различные значения, получим множество линий уровня
20х1+13х2=С
Построим нормальный вектор gradF, и перпендикулярно к нему через точку (0;0) проведем прямую
Задать вопрос
на новый заказ в Автор24.
