Обозначения искомых переменных. Графический метод оптимизации. Применение симплекс-метода для решения задач линейного программирования

Страницы работы

Фрагмент текста работы

Вариант 9.

I.Задача 1

Линейного программирования (количество переменных n = 2).

№ вар

Содержательная

постановка

Исход.

данные

9

3

3

 

Задача №3:

Для производства двух видов проката А и В используется два сорта руды, причем закупки сырья ограничены возможностями поставщиков. Известна цена 1 т проката каждого вида, а также норма расхода руды каждого вида на производство проката и имеющиеся запасы руды. Найти оптимальный план производства проката, при котором обеспечивается максимальный доход от его реализации, если известен доход фирмы от реализации 1 т проката А и В (таблица П.3).

Исходные данные для задачи 3.

Вариант 3

Запасы сырья, т.

Стоимость проката

у.е./т.

Сырье

Норма расхода

сырья, т/т.

А

В

Руда 1

4500

А

500

Руда 1

5

9

Руда 2

4200

В

600

Руда 2

6

7

Введем обозначения искомых переменных:

Va – объем проката А;

Vв – объем  проката В.

Математическая модель имеет вид:

Целевая функция

F = 500×Vа + 600×Vв à max.

Система ограничений

5×Vа + 9×Vв £ 4500    (1.1)

6×Vа + 7×Vв £ 4200     (1.2)

Vа ³ 0

Vв ³ 0

Графический метод оптимизации

Отобразим графически на плоскости неравенство 5×Vа + 9×Vв £ 4500, для этого перейдем  к уравнению вида:

5×Vа + 9×Vв = 4500

Которое представим графически прямой (1) на рис. 1. по точкам (Vа=900, Vв=0) и (Vа=0, Vв=500).

Аналогичные построения проведем для неравенства  6·Vа + 7·Vв ≤ 4200

(Vа=700, Vв=0) и (Vа=0, Vв=600)  прямая (2).

Рис. 1.

Граничные условия соответствуют двум дополнительных неравенствам, которые определяют не отрицательность переменных Vа и Vв.

Координаты всех точек многоугольника ABCO имеют такие значения Vа и Vв, которые удовлетворяют системе неравенств (1.1) - (1.2) и образуют область допустимых решений.

Построение  графика целевой функции.

Для графического представления целевой функции зададимся произвольным значением F=378000 и построим линию (3), которая называется линией уровня целевой функции (рис. 1):

F = 500×Vа + 600×Vв = 360000                           

по точкам (Vа=0,Vв=600) и (Vа=720, Vв=0)

Возможное увеличение целевой функции связано с удалением прямой от начало координат. Стрелка на рис. 1. указывает направление возрастания F. Максимума она достигает в вершине B многоугольника ABCO.

Таким образом, получено решение: оптимальный план производства проката, при котором обеспечивается максимальный доход от его реализации

Vа = 320 т. и Vв =320 т.  F = 352000 у.е.

На основании рассмотренного примера можно сделать вывод: оптимальным  решением всегда являются координаты вершины области допустимых решений.

Применение симплекс-метода для решения задач линейного программирования.

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

F' = - 500×Vа - 600×Vв à min

5×Vа + 9×Vв + V1 = 4500

6×Vа + 7×Vв + V2 = 4200

где V1,V2 - в данном случае определяют разницу между располагаемым и потребляемым ресурсами, т.е. запас ресурса.

При выполнении курсовой работы подробнее остановимся на табличной реализации симплекс-метода, поскольку табличный способ реализации симплекс-метода предполагает выполнение ряда однотипных операций, связанных с преобразованием таблиц специального вида. Эти действия легко алгоритмизуются и используются как основа в комплексах программ на ЭВМ.

На первом этапе необходимо преобразовать математическую  модель, таким образом, чтобы выразить базисные переменные через свободные. Поскольку в опорном решении базисные переменные соответствуют V1, V2, а свободные Vа = 0, Vв = 0, то система примет вид:

V1  =  4500   -  (5×Vа + 9×Vв)

V2  =     4200   -  (6×Vа + 7×Vв)                  

F'  =      0    -  (500×Vа + 600×Vв)

Аналогичное представление будет соответствовать каждому шагу табличного симплекс-метода и достаточно наглядно его можно представить с помощью симплекс-таблицы,  структура которой может быть различной. Будем использовать следующий вид таблицы.

Шаг первый:

Целевая функ-

Свободные члены

Свободные переменные

ция, базис

уравнений

-Vа

-Vв

F`

0

4500×(-66)=-297000

500

5×(-66)=-330

600×(-l)

600×(-0,11)=-66

V1

4500×l

 495

5×l

0,55

9

l=1/9=0.11      

V2

4200

4500×(-0,77)=-3465

6

5×(-0,77)=-3,85

7×(-l)

7×(-0,11)=-0,77      

Шаг второй:

Целевая функ-

Свободные члены

Свободные переменные

ция, базис

уравнений

-V1

-Vв

F`

-297000

735×(-78)=-57330             

170(-l)

170(-l)=-78

-66

-0,77×(-78)=60

495

735×(-0,25)=-184                  

0,55(-l)

               0,55(-l)= -0,25                 

0.11

 -0,77(-0,25)=0,19                    

V2

735×l

735×l=338

2,15

l=1/2,15=0.46      

-0,77×l

 -0,77×l= -0,35  

Шаг третий:

Целевая функ-

Свободные члены

Свободные переменные

ция, базис

уравнений

-V1

-V2

F`

-350330

-78(-l)        

-78(-l)=169

-6

311

-0,25(-l)

-0,25(-l) =0,542                

0,3

Vв

338×l

338×l=734

0.46    

l=1/0,46=2,17

-0,35×l

-0,35×l=-0,76  

Полученное решение (столбец свободных членов) является допустимым и оптимальным, исходя из представленных выше правил анализа симплекс-таблиц.

Отсюда оптимальное  решение,  соответствующее  min F ' (max F) имеет вид:  Va = 311 т - объём проката А;

Vв = 338 т  – объём проката В.

Максимальная стоимость  отпущенной  электроэнергии F = 350330 тыс.рублей, что полностью совпадает с  решением полученным графическим способом.

2.Задача 3

Линейного программирования (количество переменных n = 4)

Задача №3: Районная энергосистема включает в себя 4 ТЭС. В качестве топлива на ТЭС могут использоваться бурый уголь, каменный уголь, газ, мазут. Известны запасы каждого вида топлива и удельный расход топлива

Похожие материалы

Информация о работе