Заказ работы

Заказать
Каталог тем

Заказ научной авторской работы

Задача линейного программирования

Типовыми задачами линейного программирования являются: транспортная задача, задача использования и планирования производственных мощностей, задача составления смесей, задача распределения и планирования обеспечивающих ресурсов, задача составления плана производства, задача раскроя тканей, задача планирования смен и расписаний, задача покрытий и некоторые другие задачи [12, 13, 32, 47, 58]. Все эти задачи в конечном итоге оказываются той или иной модификацией транспортной задачи и решаются с использованием симплекс-метода; различия состоят в смысловой интерпретации и в конкретной форме целевых функций и ограничений.

Кратко изложим общую постановку и метод решения задачи линейного программирования: найти минимум  линейной целевой функции

                                                           n

Q ( X )          =          S      Rj * Xj

                                                           j = 1

при выполнении условий (линейных ограничений)

                        n

        S Ai j * Xj  = Bi   ;        i = 1, 2,..., m

                        j=1

 

                        Xj >= 0 ;                   j = 1, 2,..., n

 

                   Bi  >= 0;               i = 1, 2,..., m.

 

Точка  X  ( X1,  X2,...,  Xn ),  удовлетворяющая всем условиям, называется допустимой точкой; множество всех допустимых точек называется допустимой областью. Допустимая область (если она непуста и ограничена) является выпуклым многогранником в многомерном пространстве, при этом минимум линейной целевой функции достигается на границе допустимой области (в одной из вершин многогранника). Задача линейного программирования может быть записана в матричной форме

Q ( X )        =       < R,X >      ==>   min,

A X            =       B,

X                =>     0.

где A есть прямоугольная матрица размера    m x n ,  m < n    и  ранга m. Считая, что базисный  минор ранга  m  занимает  m  первых (левых) столбцов, называем переменные X1 – Xm базисными, а остальные переменные – свободными. Приведя базисный минор (методом последовательных исключений Жордана-Гаусса) к единичной матрице, получаем

 

n

Xi      +       S       aij*Xj          =       0Bi ;   i=1,…,m

J=m+1

 

 Обнулив свободные переменные, решаем линейную систему уравнений и получаем частное решение, называемое базисным

 

0X      =       [ 0B1   , …,   0Bm, 0, …, 0 ]

Если базисное решение удовлетворяет ограничениям, то оно называется допустимым.         Каждому из        возможных наборов базисных переменных соответствует свое базисное решение. Каждому допустимому базисному решению соответствует своя вершина многогранника. Перебор вершин эквивалентен перебору базисных решений.

 Выражая целевую функцию через свободные переменные, получаем канонический вид ЗЛП, соответствующий допустимому базисному решению:

                                                                                              n

Q ( X )          =          Q (0X )        +       S      pj * Xj  ==>        

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


* поля отмеченные звёздочкой, обязательны для заполнения!

Тема работы:*
Вид работы:
контрольная
реферат
отчет по практике
курсовая
диплом
магистерская диссертация
кандидатская диссертация
докторская диссертация
другое

Дата выполнения:*
Комментарии к заказу:
Ваше имя:*
Ваш Е-mail (указывайте очень внимательно):*
Ваш телефон (с кодом города):

Впишите проверочный код:*    
Заказ курсовой диплома или диссертации.

Горячая Линия


Вход для партнеров