ЗАДАНИЕ 6 . Постановка задачи математического программирования

В процессе принятия решений часто необходимо вербальное описание проблемы преобразовать в формальное описание задачи и затем использовать известный метод её решения.

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

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

Постановка задачи сводится к переводу словесного описания ситуации в формализованное, в котором определяется переменная, органичения и целевая функция.

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

Задача математического программирования состоит в нахождении отпимального (максимального или минимального) значения целевой функции, переменные которой принадлежат некоторой области допустимых значений. Наиболее наглядными являются задача линейного программирования (ЗЛП) и транспортная задача.

ЗЛП состоит в определении минимального или максимального значения целевой функции; целевая функция и ограничения и представляют собой линейные неравенства.

(F(х) = ) ®Max

i = 1….k

x_{j ³ 0,}

a_ij , b_i, c_i - заданные постоянные величины

Чтобы решить эту задачу, нужно найти такой вектор Х = (x_1, x_2,… x_к)

(набор переменных величин x_j), чтобы он доставлял максимальное значение целевой функции F (х)

 

Пример постановки ЗЛП.

На предприятии изготавливается два вида изделий из трёх видов материалов

a_{ij –} расход материала вида i на одно изделие j.

b_i - запас материала вида i

c_i - прибыль от одного изделия вида i.

 

Сформулировать ЗЛП, чтобы определить, сколько изделий каждого вида следует производить, чтобы максимизировать прибыль. Расход материалов представлен в Таблице.

 

Таблица

Расход материала вида i на одно изделие j

 

Изделие (j)	Вид материала (i)	Прибыль на одно изделие
1	2	3
1
2
Запас материалов

 

Решение

В соответствии с вопросом, сформулированным в задаче, в качестве переменной величины выступит объём производства изделий каждого вида. Тогда:

Х₁ - объём производства изделий 1-го вида

Х₂ - объём производства изделий 2-го вида

 

Постановка задачи ЛП:

22Х₁ + 14Х₂ ® мах (максимизировать совокупную прибыль от

производства изделий обоих видов)

5 Х₁ + 7 Х₂ £ 456 – ограничение на потребление материалов 1-го вида

2 Х₁ + 8 Х₂ £ 594 ограничение на потребление материалов 2-го вида

6 Х₁ + 4 Х₂ £ 872 ограничение на потребление материалов 3-го вида

Х_1, Х₂ ³ 0 - изделия должны производиться

 

 

Задания

Вариант 1.

 

В трёх цехах изготавливаются два вида изделий.

a_{ij –} загрузка j-го цеха при изготовлении изделий, %

c_i - прибыль от одного изделия вида i, руб.

Сформулировать ЗЛП, чтобы определить, сколько изделий каждого вида следует производить при возможно полной загрузке цехов, чтобы получить максимальную прибыль. Загрузка цехов представлена в Таблице.

Таблица

Загрузка цехов

 

Изделие (j)	№ цеха (i)	Цена изделия
1	2	3
1
2		1,2	5,1
Максимальная загрузка	100%	100%	100%

 

Вариант 2

Имеются три склада запчастей А₁, А₂, А₃ и три сервисных центра

Ц₁, Ц₂, Ц₃. На складах следующее число контейнеров: А₁= 14 А₂=10 А₃ =16; в

Транспортные затраты a_ij на перевозку одного компьютера со i –го склада в магазин j представлены в таблице:

	Ц1	Ц 2	Ц3
А1		4(a12)
А2
А3

 

Составить задачу линейного программирования (целевую функцию и ограничения)

Пояснение. В качестве переменной величины использовать Х_ij – число перевезённых компьютеров со i –го склада в магазин j

 

 

Вариант 3