Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Решение задачи симплекс-методом.
|
|
Для приведения системы к каноническому виду введем балансные неизвестные х3 , х4 , х5.
35x1+70x2+х3 =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 тыс.руб.