Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Решение задачи симплекс-методом.






Для приведения системы к каноническому виду введем балансные неизвестные х3 , х4 , х5.

35x1+70x23 =2450

50x1+40x2 + х4 =2000 (1.5)

80x1+35x2 + х5=2800

10х1+15х2 =F

Составим симплекс таблицу:

Таблица 1.

Базисные переменные Оценки пер-х Переменные Свободные члены Контр. столбец
х1 х2 х3 х4 х5
х3               2450× 0=0
х4               2000× 0=0
х5               2800× 0=0
F             F  
х2   1/2   1/70        
х4       -4/7        
х5   125/2   -1/2        
F   5/2   -15/70     F-525  
х2       5/210 -1/60      
х1       -4/210 1/30      
х5       29/42 -25/12      
F       -1/6 -1/12   F -575  

 

Шаг 1. В столбцы 1-6 и строки 1-4 записываем коэффициенты при неизвестных и свободные члены системы (1.5). В столбце базисных переменных записываем их обозначения. Так как к началу решения оценки базисных переменных неизвестных даем им значения равные нулю. Оценки свободных переменных (количество выпускаемой продукции) принимаются равными их значениям в целевой функции. Решение задачи линейного программирования в симплексной таблице находится в столбце свободных членов, то есть решения на первом шаге выглядит как:

х1 =x2=0; x3=2450; x4=2000; x5=2800

Контрольный столбец служит для проверки правильности решения и представляет собой произведения коэффициентов столбца свободных членов на оценки соответствующих переменных. Сумма этих произведений дает значение целевой функции, в данном случае F (x)=0

Ведущий столбец – 2 (т.е максимальное значение целевой функции -15, которое принадлежит 2му столбцу), ведущая строка – 1 (т.е. при делении коэффициентов в столбце свободных членов на соответствующие коэффициенты ведущего столбца, минимальное значение 35, принадлежащее 1 строке).

Шаг 2. Переход к новому опорному плану осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса.

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

Остальные коэффициенты пересчитываются по методу Жордана – Гаусса, т.е. по правилу прямоугольника следующим образом:

35 70

50=50 - (35× 40)/70 = 30

50 40

Шаг 3. Аналогично заполняется таблице на 3 шаге. Получаем, что в этой таблице все коэффициенты в строке целевой функции отрицательные или равные нулю, т.е. полученный план оптимален, т.е. нет ни одной переменной, введение которой в план увеличилось бы значение целевой функции в 575 тыс.руб.

 

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал