yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->            1.3. Задача об использовании мощностей (задача о загрузке оборудования).

Исследование операций

            1.3. Задача об использовании мощностей (задача о загрузке оборудования).

            Предприятию задан план выпуска продукции по времени и номенклатуре. Требуется за время Т выпустить n1 , n2 ,…, nк единиц продукции по номенклатуре Р1, Р2, , … , Рк. Продукция производится на станках S1, S2,…, Sm. Для каждого станка известна производительность aij – количество единиц продукции Рj, которое можно произвести на станке Si в единицу времени.

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

            Экономическо-математическая модель задачи.

         Обозначим хij – время , в течении которого станок Si загружен изготовлением продукции Рj.

            i = 1, 2, … , m ;   j = 1, 2, … , к.

            Так как время работы каждого станка ограничено и не превышает Т, то имеют место неравенства

                                                                                  (1.13)

            Для выполнения плана выпуска по номенклатуре необходимо чтобы выполнялись следующие равенства

                                                                     (1.14)

            Кроме этого быть xij ≥ 0                                                                                (1.15)

            Затраты на производство всей продукции выразятся функцией

                                                                                       (1.16)

            Нужно найти такое решение х (х11, x12 , …, xmk), удовлетворяющее системам (1.13), (1.14) и условию (1.15), при котором функция цели (1.16) принимает минимальное значение.

 

 

2. Cистема m линейных уравнений с n переменными

 

            В задачах Л.П. принципиальное значения имеют системы линейных уравнений, в которых число переменных n больше числа уравнений m .

                                                                                (2.1)

                                   n > m

            Если все уравнения независимы, то ранг матрицы, составленной из коэффициентов при неизвестных, равен числу уравнений r = m. Тогда при условии совместности системы (когда ранг матрицы системы равен рангу расширенной матрицы) поскольку n > m = r, система имеет бесконечное множество решений.

            При поиске этих решений определяют группы m переменных, которые называют основными или базисными. Число групп базисных переменных определяется из условия неравенства нулю определителя, составленного из коэффициентов при этих неизвестных. Число групп базисных переменных не превышает числа сочетаний из n элементов по m, т.е. .

            Остальные m-n переменных называются неосновными или свободными.

            Решение, полученное при условии, что все свободные переменные равны нулю, называются базисным решением. Базисное решение может быть допустимым или недопустимым. Допустимым базисным решением (его ещё называют опорным планом) есть решение, в котором значения всех переменных неотрицательны. Недопустимым является базисное решение, в котором значение хотя бы одной переменной отрицательное.

Пример 2.1

            Для системы уравнений 

            найти:

1) все группы базисных переменных;

2) бесконечное множество решений, для одной из групп базисных переменных;

3) все базисные решения;

4) допустимые и недопустимые базисные решения.

1. Определим общее число возможных групп основных (базисных) переменных.

            Возможные группы основных переменных следующие 

х1,х2х1,х3х1,х4х2,х3х2,х4х3,х4;

            Среди этих групп переменных базисными будут те, для которых определители, составленные из коэффициентов при этих неизвестных не равны нулю.

Для группы х1, х2                                                          Для группы х1, х3

                                                    

 

Для группы х1, х4                                                          Для группы х2, х3

                                                   

 

Для группы х2, х4                                                          Для группы х3, х4

                                                             

Таким образом, из 6 возможных групп базисных переменных только три группы, составленные из переменных х1,х2; х1,х3х1,х4, являются таковыми.

 

2. Найдём бесконечное множество решений для группы базисных переменных х1,х2.

В системе уравнений разделяем переменные. Слева от знака равенства оставляем базисные переменные, справа записываем неосновные переменные и свободные члены уравнений.

;

Т.к. х3 и х4 – свободные переменные, положим х3 = с1; х4 = с2.

Тогда  , , , , где ,

 

3.Найдём базисные решения.

Базисное решение для группы базисных переменных х1 и х2 ищется при условии, что х3 = 0, х4 = 0.

; ;  – 1-е  базисное решение.

Базисное решение для группы базисных переменных х1 и х3. ищется при условии, что х2 = 0, х4 = 0.

; ;  – 2-е  базисное решение.

Базисное решение для группы базисных переменных х1 и х4 ищется при условии, что х2 = 0, х3 = 0.

; ;  – 3-е  базисное решение.

4. Допустимыми базисными решениями являются точки  и , недопустимым-.

 

 

 

6