|
b>Постановка задачи На звероферме могут выращиваться норки, выдры и нутрии. Для обеспечения нормальных условий их выращивания используется 3 вида кормов. Количество корма каждого вида, которое должны получать зверьки в среднем приведено в таблице: |
| Количество единиц корма, которое ежедневно должны получать | | | Вид корма | Норка | Выдра | Нутрия | Общее количество корма | | I | 4 | 2 | 5 | 190 | | II | 5 | 3 | 4 | 320 | | III | 7 | 9 | 5 | 454 | | Прибыль от реализации одной шкурки, руб. | 150 | 320 | 350 | | |
В таблице указано общее количество корма каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки зверька. Определить, сколько зверьков каждого вида следует выращивать на звероферме, чтобы прибыль от реализации шкурок была максимальной.Алгоритм решения задач симплекс - методом1) Поставленная описательная задача переводится в математическую форму (целевая функция и ограничения).2) Полученное математическое описание приводят к канонической форме.3) Каноническую форму приводят к матричному виду.4) Ищут первое допустимое решение. Для этого матрица должна быть правильной. Матрица в ЗЛП называется правильной, если она содержит минимум m правильных (базисных) столбцов, где m - число строк в матрице. Столбец в канонической ЗЛП называется правильным (базисным), если все его элементы равны нулю, кроме единственного равного единице.5) Если матрица не является правильной, то ее нужно сделать таковой с помощью искусственного базиса. Для этого в матрицу нужно дописать столько базисных столбцов, чтобы их общее количество вместе с уже имеющимися базисными столбцами составляло m. После этого переходят к пункту 6. Если искусственный столбец выходит из базиса, то его удаляют из матрицы. Если удалены все искусственные столбцы, то получено первое допустимое решение. Если искусственные элементы не удается вывести из базиса, то система не имеет решений.6) Строят последовательность матриц. Нужно определить ведущий столбец, ведущую строку и ведущий элемент. Элемент, соответствующий ведущей строке, удаляется из базиса, а на его место ставят элемент, соответствующий ведущему столбцу. Составляют уравнение пересчета матрицы, выполняют пересчет, а затем проверяют его результаты на оптимальность. Если решение не оптимально, то заново ограничивают ведущий элемент, ведущую строку и ведущий столбец.Признаком оптимальности решения является наличие в векторе решений только отрицательных или нулевых коэффициентов при всех ограничениях.Ответ записывается следующим образом:- Каждому отрицательному коэффициенту в векторе решения ставится в соответствие нулевой коэффициент для соответствующей переменной в ответе.- Для каждого нулевого коэффициента в векторе решения ставится в соответствие значение свободного члена из строки, содержащей единицу в столбце данной переменной.- Фиктивные переменные в ответе не учитываются.Ведущим может быть назначен любой столбец, удовлетворяющий одному из условий:1) Первый столбец, содержащий положительный элемент в векторе решений.2) Столбец, содержащий наибольший положительный элемент в строке решения.3) Если столбец удовлетворяет условию max(Cj min bj/aij) при решении на max, и min(Cj min bj/aij) при решении задач на min.Cj - коэффициент целевой функции в столбце j, aij - коэффициент в столбце j и строке i.Решение задачиОпределим максимальное значение целевой функции 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) Поскольку задача решается на максимум, то ведущий столбец выбирают по максимальному отрицательному числу и индексной строке. Все преобразования проводят до тех пор, пока не получатся в индексной строке положительные элементы. Переходим к основному алгоритму симплекс-метода. |
X1 | X2 | X3 | X4 | X5 | X6 | св. чл. | | 4 | 2 | 5 | 1 | 0 | 0 | 190 | | 5 | 3 | 4 | 0 | 1 | 0 | 320 | | 7 | 9 | 5 | 0 | 0 | 1 | 454 | | -3500 | -3200 | -1500 | 0 | 0 | 0 | 0 | | |
Итерация №0 Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты В качестве ведущего выберем столбец, соответствующий переменной x1, так как наибольший коэффициент по модулю. Вычислим значения D i по строкам как частное от деления и из них выберем наименьшее: Следовательно, 1-ая строка является ведущей Разрешающий элемент равен 4 и находится на пересечении ведущего столбца и ведущей строки Формируем следующую часть симплексной таблицы. Вместо переменной x в план 1 войдет переменная x1 Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=4 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x1 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 . Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы: |
X1 | X2 | X3 | X4 | X5 | X6 | св. чл. | | 1 | 1/2 | 5/4 | 1/4 | 0 | 0 | 190/4 | | 5 | 3 | 4 | 0 | 1 | 0 | 320 | | 7 | 9 | 5 | 0 | 0 | 1 | 454 | | 3500 | 3200 | 1500 | 0 | 0 | 0 | | | |
|
X1 | X2 | X3 | X4 | X5 | X6 | св. чл. | | 1 | 1/2 | 5/4 | 1/4 | 0 | 0 | 190/4 | | 0 | 1/2 | -9/4 | -5/4 | 1 | 0 | 165/2 | | 0 | 11/2 | -15/4 | -7/4 | 0 | 1 | 243/2 | | 0 | -1450 | 2875 | 875 | 0 | 0 | | | |
Итерация №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 | X2 | X3 | X4 | X5 | X6 | св. чл. | | 1 | 0 | 159/100 | 41/100 | 0 | -9/100 | 729/20 | | 0 | 0 | -191/100 | -109/100 | 1 | -9/100 | 1429/20 | | 0 | 1 | -15/22 | -7/22 | 0 | 9/50 | 243/11 | | 0 | 0 | 1886.36 | 413.64 | 0 | 263.64 | | | |
Страницы: 1, 2, 3, 4
| 
