Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Решение задачи ⇐ ПредыдущаяСтр 6 из 6 Определим максимальное значение целевой функции F(X) = 3500 x1 +3200 x2 +1500 x3 при следующих условиях ограничений.
4 x1 + 2 x2 + 5 x3 <=190 5 x1 + 3 x2 + 4 x3 <=320 7 x1 + 9 x2 + 5 x3 <=454
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.
4x1 + 2x2 + 5x3 + 1x4 + 0x5 + 0x6 = 190 5x1 + 3x2 + 4x3 + 0x4 + 1x5 + 0x6 = 320 7x1 + 9x2 + 5x3 + 0x4 + 0x5 + 1x6 = 454
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Решим систему уравнений относительно базисных переменных: x4 , x5 , x6 Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,190,320,454) Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы. Переходим к основному алгоритму симплекс-метода.
Итерация №0 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю. Вычислим значения D i по строкам как частное от деления и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x1 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 . Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы:
Итерация №1 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты В качестве ведущего выберем столбец, соответствующий переменной x2, так как наибольший коэффициент по модулю. Вычислим значения D i по строкам как частное от деления и из них выберем наименьшее: Следовательно, 3-ая строка является ведущей Разрешающий элемент равен 5.5 и находится на пересечении ведущего столбца и ведущей строки Формируем следующую часть симплексной таблицы. Вместо переменной x в план 2 войдет переменная x2 Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x6 плана 1 на разрешающий элемент РЭ=5.5 На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x2 плана 2 записываем нули. Таким образом, в новом плане 2 заполнены строка x2 и столбец x2 . Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (5.5), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы: Конец итераций: найден оптимальный план Окончательный вариант симплекс-таблицы:
Оптимальный план можно записать так:
x1 = 729/20=36.45 x5 =1429/20= 71.45 x2 =243/11= 22.09
F(X) = 3500*36.45 + 3200*22.09 = 198281.82
|