На странице представлен фрагмент
Реши любую задачу с помощью нейросети.
Для изготовления компота двух видов используются яблоки, вишни и сливы. Определить план выпуска продукции, при котором будет достигнута максимальная прибыль, исходные данные задачи приведены в таблице.
Фрукты Запасы фруктов Количество фруктов для изготовления одной банки компота, в кг
1 2
Яблоки 6000 1,6 0,8
Вишни 5000 0,4 0
Сливы 5400 0 1,2
Цена одной
банки, руб.
60 50
Решение.
Составим математическую модель задачи.
Необходимо спланировать объем производства продукции так, чтобы прибыль была максимальной. Поэтому переменными являются:
х1- количество компота вида 1;
x2 – количество компота вида 2.
Суммарная прибыль от производства равна
z=60х1+50×2.
Целью является определение среди всех допустимых значений x1, х2 таких, которые максимизируют суммарную прибыль, т. е. целевую функцию z. Перейдем к ограничениям, которые налагаются на x1, х2.
Объем производства продукции не может быть отрицательным, следовательно: x1, x2≥0.
Расход фруктов для производства двух видов компота не может превосходить максимально возможный запас сырья, следовательно:
1,6×1+0,8×2≤6000,
0,4×1+0x2≤5000,
0x1+1,2×2≤5400
Таким образом, математическая модель данной задачи имеет следующий вид:
z=60х1+50×2→ max
1,6×1+0,8×2≤6000 0,4×1+0x2≤50000×1+1,2×2≤5400×1, x2≥0
Заметим, что данная модель является линейной, т. к. целевая функция и ограничения линейно зависят от переменных.
Решим задачу графическим методом.
z=60х1+50×2→ max
1,6×1+0,8×2≤6000 0,4×1+0x2≤50000×1+1,2×2≤5400×1, x2≥0
Построим область допустимых решений, т.е. решим графически систему неравенств.
Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
1,6×1+0,8×2≤600, 0,4×1≤5000, 1,2×2≤5400
Границей неравенства 1,6×1+0,8×2≤6000 является прямая1,6×1+0,8×2=6000, построим ее по двум точкам:
Х1 0 3750
Х2 7500 0
Произвольная точка (0; 0) удовлетворяет неравенству 1,6×1+0,8×2≤600, поэтому областью решения неравенства является область, в которой находится точка (0; 0). Полуплоскость решения обозначена стрелкой.
Границей неравенства 0,4×1≤5000 является прямая
0,4×1=5000 или x1=12500
Произвольная точка (0; 0) удовлетворяет неравенству0,4×1≤5000 , поэтому областью решения неравенства является область, в которой находится точка (0; 0). Левая полуплоскость решения обозначена стрелкой.
Границей неравенства 1,2×2≤5400 является прямая
1,2×2=5400 или x2=4500
Произвольная точка (0; 0) удовлетворяет неравенству1,2×2≤5400 , поэтому областью решения неравенства является область, в которой находится точка (0; 0). Нижняя полуплоскость решения обозначена стрелкой.
Пересечением полуплоскостей будет являться область, координаты точек которой удовлетворяют условию неравенств системы ограничений задачи. Не забудем про ограничения x1, x2≥0: условия неотрицательности переменных ограничивают область допустимых решений первым квадрантом. Имеем многоугольник решений ОАВС.
Рассмотрим целевую функцию задачи: z=60х1+50×2→ max.
Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление возрастания функции Z(X). Начало вектора – точка (0; 0), конец – точка (60; 50). Для удобства построения вектора- градиента, построим вектор, соноправленный с {60, 50}, который “удобно” изобразить в масштабе построенного изображения, пусть это будет вектор {2400, 2000}
Строим прямую 2400х1+2000×2=const – линию уровня функции Z(X), перпендикулярную вектору-градиенту. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта “зеленая” прямая. Она пересекает область в точке В, которая получена в результате пересечения прямых
1,6×1+0,8×2=6000 и x2=4500.
Тогда ее координаты удовлетворяют уравнениям этих прямых.
Составим систему уравнений:
1,6×1+0,8×2=6000 ,x2=4500.
Итак, x2=4500,×1=1500.
Таким образом, максимальное значение целевой функции:
z=60∙1500+50∙4500=315000
Итак, x1=1500, x2=4500, zmax=315000
Решим задачу симплекс-методом.
В начале приведем задачу
z=60х1+50×2→ max
1,6×1+0,8×2≤6000 0,4×1+0x2≤50000×1+1,2×2≤5400×1, x2≥0
к канонической форме. Для этого от системы неравенств перейдем к системе линейных уравнений, введя дополнительные переменные х3, x4, x5 и перепишем условие задачи:
z=60х1+50×2→ max
1,6×1+0,8×2+x3=6000 0,4×1+0x2+x4=50000×1+1,2×2+x5=5400×1, x2,x3,x4,x5≥0
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
A=1.60.810060000.40010500001.20015400
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x3,x4,x5. Полагая, что свободные переменные равны 0, получим первый опорный план:
X = (0,0,0, 6000,5000,5400)
Базисное решение называется допустимым, если оно неотрицательно.
Составим симплекс-таблицу:
Первая симплекс-таблица
Базис Свободные члены Свободные переменные
X1 X2 X3 X4 X5
X3 6000 1.6 0.8 1 0 0
X4 5000 0.4 0 0 1 0
X5 5400 0 1.2 0 0 1
Индексная строка 0 -60 -50 0 0 0
Индексная строка есть результат вычитания из нуля коэффициентов перед свободными переменными.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ключевого выберем столбец, соответствующий переменной x1 (при отыскании максимума выбирается наименьший отрицательный элемент в индексной строке – это -60).
Компоненты вектора свободных членов делятся на положительные элементы ключевого столбца и из них выбирается наименьшее.
Вычислим значения Di по строкам как частное от деления: bi / ai1 и из них выберем наименьшее:
min (6000:1.6 , 5000:0.4) = min (3750,12500)=3750
Следовательно, первая строка является ведущей.
Разрешающий элемент равен 1.6, он находится на пересечении ключевого столбца и ключевой строки.
Вместо переменной x3 в план войдет переменная x1.
Каждый элемент ключевой строки делится на разрешающий элемент. Полученные частные являются элементами ключевой строки следующей таблицы.
Ключевой столбец в новой таблице – нули, за исключением разрешающего элемента.
Остальные элементы рассчитываются по схеме (выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент):
Эн = ЭС – (Э1х Э2)/ ЭР
Эн – новый элемент, ЭС – старый элемент, Э1 – элемент ключевой строки, Э2 – элемент ключевого столбца, ЭР – разрешающий элемент.
Получаем новую симплекс-таблицу:
Вторая симплекс-таблица
Базис Свободные члены Свободные переменные
X1 X2 X3 X4 X5
X1 3750 1 0.5 0.63 0 0
X4 3500 0 -0.2 -0.25 1 0
X5 5400 0 1.2 0 0 1
Индексная строка 225000 0 -20 37.5 0 0
В столбце свободных членов все элементы положительны, то полученное решение является допустимым.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В качестве ключевого выберем столбец, соответствующий переменной x2 (наименьший отрицательный элемент в индексной строке – это -20). Компоненты вектора свободных членов делим на положительные элементы ключевого столбца и из них выбираем наименьшее:
min (3750:0.5 , 5400:1.2) = min (7500,4500)=4500
Следовательно, третья строка является ведущей.
Разрешающий элемент равен 1,2, он находится на пересечении ключевого столбца и ключевой строки.
Вместо переменной x5 в план войдет переменная x2.
Получаем новую симплекс-таблицу:
Третья симплекс-таблица
Базис Свободные члены Свободные переменные
X1 X2 X3 X4 X5
X1 1500 1 0 0.63 0 -0.42
X4 4400 0 0 -0.25 1 0.17
X2 4500 0 1 0 0 0.83
Индексная строка 315000 0 0 37.5 0 16.67
Среди значений индексной строки нет отрицательных. Поэтому таблица определяет оптимальный план задачи. Т.е. полученное решение максимизирует целевую функцию. При этом оптимальным планом будут величины:
х1=1500, х2=4500 (они свободные), x4 = 4400 (она базисная), целевая функция:
z=60х1+50×2=60∙1500+50∙4500=315000
Из этой таблицы также следует, что базисная переменная х4=4400.
Это означает, что имеется резерв ресурсов сырья “Вишни” в количестве 4400 кг, что свидетельствует о его излишках.
Решим задачу с помощью MS Excel.
На рабочем листе введем числовые данные задачи. Для оптимального решения, которое появится после вычислений, отведены ячейки B8:В9. Ячейка В11 зарезервирована для вычисления значения целевой функции, ячейки F3:F5 – для левых частей ограничений.
В режиме отображения формул заполненная таблица имеет вид:
Поскольку ячейки оптимального решения B8:В9 не содержат данных, значение расхода сырья и целевой функции пока 0.
Подключим надстройку Excel «Поиск решения» (если она отсутствует на ленте «Данные»). Кнопка «Office», параметры Excel, Надстройки, Перейти и в диалоговом окне выбираем «Поиск решения»:
В результате на ленте «Данные» в группе «Анализ» появилась соответствующая надстройка:
Выбираем команду «Поиск решения» и в появившееся диалоговое окно вводим данные, при этом ограничения удобнее задавать в виде диапазонов:
Нажимаем ОК, затем “Выполнить”. После нажатия кнопки «Выполнить» открывается окно «Результаты поиска решения», которое сообщает, что решение найдено. Сохраняем его:
Часть выполненной работы
Купить уже готовую работу
Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.