Математическая модель задачи составления производственного плана

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

{spoiler=Подробнее}

Задача 1. Некоторому заводу требуется составить оптимальный по реализации производственный план выпуска двух видов изделий при определенных возможностях четырех видов машин. План выпуска должен быть таким, чтобы от реализации выпушенной по этому плану продукции завод получил бы наибольшую прибыль. Оба вида изделий последовательно обрабатывается этими машинами. План должен учитывать, что 1-й вид машин ежедневно может обрабатывать эту продукцию в течение восемнадцать часов, 2-й  -  12 часов, 3 -й  - 12 часов, 4 - й - 9 часов. В следующей таблице указано время, необходимое для обработки каждого изделия этих двух видов указанными типами машин. Нуль означает, что изделия машинами данного вида не обрабатывается. Завод от реализации одного  изделия вида I получает 4 сума, а от реализации одного изделия вида II- 6 сума прибыли.

Построим математическую модель этой задачи. Пусть х₁ число изделий вида I, а х₂ - число изделий вида II . Так как машины каждого вида (1, 2, 3, 4) могут обрабатывать продукцию - не более 18, 12, 12, 9 часов соответственно, то приходим к следующий системы ограничений:

х₁ + х₂£18,

0,5х₁ + х₂£12,

х₁ £12,

х₂£9,                                    (1)

х₁³ 0,

х₂³ 0.

         Общая прибыль  F такова:

                                              F =4x₁+6x₂.                               (2)

Таким образом, построенная математическая модель наши задачи состоит из системы неравенств (1), на множестве решений которой надо найти наибольшее значение целевой функции (2).

Общем виде математическая модель задачи составления плана может быть записана так: на множестве решений системы ограничений

a₁₁x₁₊a₁₂x₂+ ... +a_1n x_n £ b₁,

           a₂₁x₁+a₂₂x₂+ ...+a_2n x₂  £ b₂

           .........................................

           a_k1x₁+a_k2x₂+...+a_kn  x_n£ b_k

           a_k+1,1x₁ +a_k+1,2x₂+...+a_k+1,nx_n=b_k+1

           ...................................................

           a_m1x₁+a_m2x₂+...+a_mnx_n=b_m

           x_i³0, i=1,2,...,n.

Найти такое, которое максимизирует значение целевой функции

F=c₁x₁+c₂x₂+...+c_nx_n.

Заметим, что: 1) ограничения системы имеют вид и неравенств, и уравнений; 2) требуется максимизировать значение целевой функции.

Математическая модель задачи составления смеси. Еще одним распространенным типом задач линейного программирования  является  задачи составления  смеси, например задача составления таких смесей нефтепродуктов, которые удовлетворяют определенным требованиям и оказываются наиболее дешевыми. Еще одним примером задачи  составления смеси может служить следующая задача: “Пусть дневная потребность в белках, жирах, углеводах , витаминах известна. Известно также содержание этих веществ в имеющих продуктах и цены единиц каждого продукта. Требуется составить такой рацион, который удовлетворяя дневной потребности в необходимых веществах , был бы наиболее дешевым”. Подобная задача часто возникает практически в любом колхозе и совхозе, занимающемся откормом животных. Рассмотрим конкретизацию этой задачи.

Задача 2. Требуется  составить смесь, содержащую три химических вещества А,В,С . Известно , что составленная смесь должна содержать вещества А не менее 6 единиц , вещества В не менее 8 единиц , вещества С не менее 12 единиц . Вещества А,В,С   содержатся в трех видах продуктов -I,II, III в концентрации, указанной в таблице:

Стоимость единицы продуктов I, II, III  различна: единица продукта  I стоит 2 сума , единица II- 3 сума , единица   III- 2,5 сума . Смесь надо составить так , чтобы стоимость используемых продуктов  была наименьшей.

Построим математическую модель задачи составления смеси. Число единиц продукта I, входящего в смесь, обозначим через х₁, продукта II -  через х₂, продукта - III через х₃ .

Составляемая смесь должна содержать вещество А, которое содержится во всех трех продуктах. На каждую единицу продукта I приходится 2 части концентрации вещества А. Следовательно, если использовано х₁ единиц продукта I, то в составляемой смеси будет 2х₁ частей вещества А. Если использовано х₂ единиц продукта II , то в смеси будет 1^. Х₂ частей вещества А. Наконец , если использовано х₃ частей вещества А. Так как общее количество вещества А в смеси должно быть не меньше 6, то

2х₁+х₂+3х₃³6 .

Смесь должна содержать и вещество В, которое так же содержится в трех продуктах. В каждой единице продукта I содержится 1 часть вещества В, следовательно, если используется х₁ единиц продукта В, то в смеси будет 1^.х₁ частей вещества В. Аналогично, если использовано х₂ единиц продукта II, то в смеси окажется 2х₂ частей вещества В. Если использовано х₃ единиц продукта В, то в смеси окажется 1,5х₃ частей вещества В.  Так как единиц , то получаем неравенство:

х₁+2х₂+1,5х₃³8.

Рассуждая аналогично относительно концентрации вещества С, получаем, что

3х₁+4х₂+2х₃³12.

Стоимость смеси слагается из 2х₁ сум. (стоимость использованного продукта I ) ,3х₂ сум.( стоимость продукта II ), 2,5х₃ сум. .( стоимость продукта  III ). Следовательно, общая стоимость смеси будет равна

2х₁+3х₂+2,5х_3.

Из условия задачи следует, что число единиц используемых продуктов всегда неотрицательно: х₁³0 ,  х₂³0 , х₃³0.

Таким образом, математическая модель задачи представлена системой линейных неравенств:

2х₁+х₂+3х₃³6,

х₁+х₂+1,5х₃³8,

3х₁+4х₂+2х₃³12,

х_i³0 , i-1,2,3,

на множестве решений которой надо найти наименьшее значение целевой функции

F=2х₁+3х₂+2,5х₃

Затем, что: 1) все ограничения системы (1)  имеют вид неравенства, 2) требуется минимизировать F.

{/spoilers}