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


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать неотразимый комплимент Как противостоять манипуляциям мужчин? Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?

Категории:

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






Решение задачи





Определим максимальное значение целевой функции 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
-3500 -3200 -1500

 

Итерация №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/2 5/4 1/4 190/4
 

 

X1 X2 X3 X4 X5 X6 св. чл.
1/2 5/4 1/4 190/4
1/2 -9/4 -5/4 165/2
11/2 -15/4 -7/4 243/2
-1450  

 

Итерация №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 св. чл.
159/100 41/100 -9/100 729/20
-191/100 -109/100 -9/100 1429/20
-15/22 -7/22 9/50 243/11
1886.36 413.64 263.64  

 



Оптимальный план можно записать так:

 

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

 

 








Date: 2015-12-12; view: 66; Нарушение авторских прав

mydocx.ru - 2015-2018 year. (0.014 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию