7.Примеры задач злп.

1. Задача о раскрое.

Листовой материал поступает на предпр-е виде стандартных форм из кот-х получают заготовки необх-х размеров. Все отходы после разделения идут в отход, кол-во отходов зависит от принятых вариантов раскроя. каждый вар-нт хар-тся кол-вом заготовок различного вида выкраиваемых из листа. Задача: составить оптим. план раскроя, т.е. указать сколько листов кроить по каждому вар-ту для получения необх-ого кол-ва заготовка каждого типа при мин-х отходах.При этом количество заготовок i типа получаемого из первого листа при использовании j варианта = a_ij количество отходов c_j. Пусть x_j>=0, количество листов раскраеваемых по варианту j. x – план раскроя. Каждую заготовку i надо выпускать в количестве не менее заданного, т.е. . Для получения оптим. полана необх-о, что бы суммарные отходы были мин-ны, т.е.

2. Задача об исп-нии ресурсов

Для изготовления 2х видов продукции р₁,р₂ исп-т 4 вида ресурсов

Вид ресурсов	запас	Количество единиц затраченных на изготовление единицы продукции
		Р1	Р2
S1	18	1	3
S2	16	2	1
S3	5	-	1
S4	21	3	-

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

Пусть х=(х₁,х₂) – опред-т объем выпускаемой продукции р₁,р₂ соотв-но. Из ограниченности запасов ресурсов следуют ограничения

S1: x₁+3x₂<=18; S2: 2x₁+x₂<=16; S3: x₂<=5; S4: 3x₁<=21

F(x₁,x₂)= 2x₁+3x₂ стремится к max

3. задача о составлении рациона

Есть 2 вида корма содержащие витамины, содержащие числа единиц питательного вещества в 1 кг. Каждого вида корма и необход. min питательных веществ

Питательные вещества	Необход min	Количество единиц затраченных на изготовление единицы продукции
		I	II
S1	9	3	1
S2	8	1	2
S3	12	1	6

Надо составить дневной рацион имеющий min стоимость в котором содержащие каждого вида min веществ было бы не менее установленного предела. х_ij – количественного j норма использ для приготовленного рациона.

S1: 3x₁+x₂>=9; S2: x₁+2x₂>=8; S3: x₁+6x₂>=12;

F(x₁,x₂)= 4x₁+6x₂ стремится к min

4. Транспортная задача.

8. Симплексный метод решения злп.

Исходя из эквивол-ти всех форм записи ЗЛП будем рассм-ть данный м-д для задачи канонич-ого вида на макс.- с'х→мах(мin) ; Ах=b ; x≥0

Обозначим: I – множ-во всех индексов, кот-ми пронумерованы координаты плана.План х назовем базисным, если: 1) (n-m) координат его = 0; 2) а остальным координатам соответствует сис-а из m лин.-нез. векторов условий матрицы А.

n-число видов продукции

m-число видов ресурсов и число ограничений задачи

х_j – свободные(небазисные) компоненты плана

Базис плана – совок-ть из m лин-нез векторов соотвеств-х базисному плану.

Баз. план наз. невырожденным, если все его баз. переменные не «-».\

Симпл. метод предполагает реализацию 3х эл-ов:

1. Определение первонач-ого допустимого баз. плана.

2. Переход к лучшему (не худшему ) баз. плану.

3. Проверка оптим-ти баз. плана. (симпл. таблица)

№оп.	хб	Сб	А0	Х1	Х2	Х3	…	хn	Θ
…	…	…	…	…	…	..	…	…	..

Последний столбец нужен для выбора разрешающей строки. Посл. строка табл. наз. оценочной или индексной (дельта j). Столбец х_б сод-т баз-е перем-е. Столбец С_б сод-т коэф-ты цел. фун-ии, стоящие п/д баз. перем-и . Столбец А₀ сод-т знач-ия баз. перем-х. В рабочей области нах. коэф-ты а_ij сис-ы ограничений при соотве-х перем-х.

Далее табл. преобразуется по опрeд. правилам:

1. если для некот. плана все оц-ки дельта j≥0, то такой план явл. оптим-ым и достигнут макс. ф-ии. Если критерии оптим-ти не вып-тся, то переходим к нехудшему плану

2. среди «-»х оценок находят макс-ое по модулю Столбец j₀ явл. разрешающим. Перем-ю с индексом j₀, соотв-ому разреш. столбцу следует ввести в базис.

3. Для определения перем-ой, выводимой из базиса находят симпл. отношение Θ=b_i/a_ij0, a_ij0>0

В общем случае симпл. отношение определяется след. обр.

=беск-ть, если b_i и a_i имеют разные знаки; если b_i=0., a_i<0; если a_i=0 ; и = 0, если b_i=0., a_i>0

Среди симпл. отношений определяется минимум.

Оно указывает на строку, с кот. нах-тся исключаемая из базиса перем-я x_j. Эта строка называется разрешающей. Элемент, стоящий на пересечении разреш. столбца и разреш. строки наз. разрешающим a_i0j0.

4. Переход к новой симпл. табл. осущ-тся путем преобразования: - меняется базис; - эл-ты разреш. строки нов. таблицы равны соответствующим эл-ам старой табл-ы, деленным на разреш. эл-нт. – все эл-ты разреш. столбца табл. равны 0, за искл. эл-нта a_i0j0=1. – все остальные эл-нты выч-тся с помощью правила прямоугольника