Задача составления оптимального графика ремонта инструмента (стр. 2 из 5)

В конце

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

При этом надо учесть, что инструмент, который возвратится из ремонта в конце

го (в данном случае 6-го дня) и позже, уже не понадобится. Поэтому еще за дней (в данном случае три дня) до конца программы не следует сдавать его в обычный ремонт, т.е.

и за

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

За весь срок выполнения производственной программы будет куплено

инструментов и израсходовано на это рублей; будет сдано в обычный ремонт инструментов и израсходовано рублей; будет сдано в срочный ремонт инструментов и израсходовано на это рублей.

Тем самым задача заключается в минимизации общей стоимости издержек

при ограничениях

и условиях

Для конкретных числовых значений целевая функция выглядит:

, при ограничениях:

x_j

0 ( j = 1(1)5 );

y_j

0 ( j = 1(1)2 );

z_j

0 ( j = 1(1)3 );

u_j

0 ( j = 1(1)6 );

Для удобства решения x_j ( j=0(1)5 ); y_j ( j=1(1)2 ); z_j ( j=1(1)3 ); u_j ( j=1(1)6 ) заменим на x_k, где k=1(1)17. Ограничения примут вид:

x_k

0 ( k = 1(1)17)

Для решения задачи методом искусственных переменных добавим в ограничения и целевую функцию переменные x₁₈, x₁₉, x₂₀, x₂₁, x₂₂:

,

при ограничениях:

x_k

0 ( k = 1(1)22)

3. Краткие сведения о методе решения задачи

3.1 Табличный симплекс-метод

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

A_1x1+...+A_nx_n+e₁x_n+e₁x_n+1+…+e_mx_n+m=A₀=[a_i0],

где

. - единичный базис, a_i0 ≥ 0

для всех i = 1, 2,..., n. Применим одну итерацию метода полного исключения к расширенной матрице ограничений A_p=[A₁, ., A_n, e₁, ., e_m, A₀].

Преобразование Гаусса называют симплексным преобразованием, когда направляющий элемент определяют по следующим правилам:

a) направляющий столбец j выбирают из условия, что в нем имеется хотя бы один положительный элемент;

б) направляющую строку i выбирают так, чтобы отношение

было минимально при условии, что a_ij>0.

При таком преобразовании в базис вводится вектор A_j и выводится вектор А_i. Теперь надо определить, как выбрать вектор, вводимый в базис, чтобы при этом значение целевой функции увеличилось.

Для этого используют так называемые оценки векторов ∆_j:

(2.2.21)

где I_б - множество индексов базисных векторов; x_ij- определяют из условия

(2.2.22)

Величины {∆_j} равны симплекс-разностям для переменных {x_j} с противоположным знаком. Следовательно, для того чтобы значение целевой функции увеличилось, необходимо выбрать направляющий столбец А_j с наибольшей по модулю отрицательной оценкой, то есть