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

Вариант 9.

I.Задача 1

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

Задача №3:

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

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

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

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в)

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

Шаг первый:

Шаг второй:

Шаг третий:

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

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

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

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

2.Задача 3

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

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