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

Пример 1.1

Имеются стержни, длиной 5 м. Их нужно разрезать на заготовки 2-х видов: заготовки А – длиной 1,5 м и заготовки В – длиной 0,8 м для производства 20 изделий. На каждое изделие требуется две длинноватых заготовки (А) и три маленьких (В). Найти число стержней, которое нужно разрезать каждым из вероятных методов, чтоб сделать необходимое Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой число изделий и минимизировать отходы.

Решение

Сначала, перебрав все вероятные методы, построим карту раскроя 1-го стержня:

Метод Количество заготовок А (по 1,5 м) Количество заготовок В (по 0,8 м) Отходы, м
I - 0,5
II 0,4
III 0,3
IV - 0,2

Для производства 20 изделий будет нужно заготовок А: 20´2 = 40 шт. и заготовок В: 20´3 = 60 шт.

1) Введем переменные. Обозначим Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой за – количество стержней, которые будут разрезаны I методом, – II методом, – III методом, – IV методом.

2) Мотивированная функция Z – отходы. Ее будем минимизировать. Найдем отходы, приобретенные при разрезании стержней:

отходы, приобретенные при разрезании стержней I методом,

потому что 5 3·1,5 = 0,5;

отходы, приобретенные при разрезании стержней II методом,

потому что 5 2·1,5 2·0,8 = 0,4;

отходы, приобретенные при разрезании стержней III методом Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой,

потому что 5 1·1,5 4·0,8 = 0,3;

отходы, приобретенные при разрезании стержней IV методом,

потому что 5 6·0,8 = 0,2.

Тогда .

3) Составим систему ограничений задачки.

а) Ограничение на заготовки А.

При разрезании стержней I методом получим заготовок А,

стержней II методом – заготовок А, стержней III методом – заготовок А, при разрезании стержней IV методом заготовок А не появляется Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой. Таким макаром, всего получим заготовок А, что по условию задачки должно быть более 40, другими словами .

б) Аналогично получим ограничение на заготовки В:

.

в) Составим ограничения на экономический смысл переменных. Потому что количество стержней может быть только неотрицательным числом, то и – целые.

Итак, математическая модель данной задачки имеет Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой вид:

;

Пример 1.2

Предприятие за 10 часов должно произвести 31 единицу продукции вида П1 и 36 единиц продукции вида П2. Для производства продукции каждого вида может быть применено оборудование А1 либо А2.

Производительность оборудования этих групп различна и определяется величиной ед./ч, а цена 1 часа работы оборудования составляет усл. ден. ед./ч , где Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой i – индекс, отличающий вид оборудования, а j – вид продукции. Требуется найти лучший план работы групп оборудования в протяжении 10 часов, при котором будет выполнен план выпуска продукции с малой себестоимостью.

5, 3, 4, 6,

8, 7, 4, 2.

Решение

Для наглядности составим таблицу:

Продукция П1 Продукция П2 Припас времени, ч
Оборудование А1 ед./ч усл. ден. ед./ч ед Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой./ч усл. ден. ед./ч
Оборудование А2 ед./ч усл. ден. ед./ч ед./ч усл. ден. ед./ч
План производства, ед.

1) Обозначим за – время работы оборудования Аi по выпуску продукции Пj, .

2) Мотивированная функция будет представлять собой издержки на выпуск продукции, которые нужно минимизировать. Потому что издержки по выпуску продукции Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой Пj на оборудование Аi составляют , то мотивированная функция будет иметь вид:

, т. е. .

3) Составим систему ограничений.

а) Ограничение на выпуск продукции П1.

На оборудовании А1 будет произведено единиц продукции П1.

На оборудовании А2 будет произведено единиц продукции П1.

Таким макаром всего продукции П1 будет произведено , что по условию должно Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой быть равно 31, другими словами получим ограничение

, либо .

б) Аналогично получим ограничение по выпуску продукции П2:

, либо .

в) Ограничение на время работы оборудования А1.

Время работы оборудования А1 по выпуску обоих видов продукции не превосходит плановый период 10 ч, как следует, ограничение будет иметь вид: .

г)Аналогично получим ограничение на время работы оборудования А Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой2: .

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

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

;

Пример 1.3

Предприятие может выпускать продукцию 2-ух видов: П1 и П2. При всем этом употребляется три вида ресурсов: время работы оборудования, сырье и электроэнергия Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой. Нормы расхода, припасы ресурсов и прибыль от реализации единицы продукции представлены в таблице:

Ресурсы Нормы расхода на единицу продукции Припас ресурса
П1 П2
Время работы оборудования, ч Сырье, кг Электроэнергия, кВтч.
Прибыль от единицы продукции, руб.

Отыскать лучший план выпуска продукции.

Решение

Введем переменные:

, – объем выпускаемой продукции П1 и Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой П2 соответственно, единиц.

Z – прибыль от реализации всей выпущенной продукции.

Математическая модель данной задачки будет иметь вид:

;

Способы решения задач линейного программирования подвергнутся рассмотрению ниже.

Задачки

1.1.1

Нужно за 24 часа сделать наибольшее количество изделий, общая себестоимость которых не должна превосходить 2000 руб., используя при всем этом два станка. Производительность первого станка составляет 5 изделий в час Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой, второго – 6 изделий в час. Себестоимость 1-го изделия, сделанного на первом станке, составляет 9 руб., на втором станке – 10 руб. Составить математическую модель выпуска продукции на обозначенных станках.

1.1.2

Цех может выпускать 2 вида продукции, создание которых характеризуется последующими данными:

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

В планируемом месяце имеется 100 часов рабочего времени и 60 кг металла. Продукции I вида должно бать выпущено более 25 изделий. Составить математическую модель задачки выпуска продукции с наибольшей прибылью от реализации.

1.1.3

Завод должен переслать 1000 деталей в ящиках 2-ух типов. Ящик I типа вмещает Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой 70 деталей, ящик II типа – 40 деталей. Цена пересылки 1-го ящика I типа составляет 30 руб., II типа – 20 руб. Для пересылки можно использовать менее 12 ящиков I типа. Составить математическую модель задачки пересылки всех деталей с меньшими затратами

1.1.4

Имеются путевки в дома отдыха 3-х видов: на 7, 12 и 20 дней. Цена их 100 руб., 150 руб. и 250 руб. соответственно Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой. Организация планирует закупить 21 путевку и издержать менее 3000 руб. Составить математическую модель задачки определения подходящего числа путевок каждого вида, чтоб общее число дней отдыха по всем путевкам оказалось большим.

1.1.5

Для рекламирования собственной продукции компания может использовать радио, телевиденье и публичный транспорт. Цена одной минутки рекламы на радио составляет 3 усл. ден Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой. ед., а на телевиденье – 50 усл. ден. ед., в публичном транспорте – 2 усл. ден. ед. Объемы продаж растут от рекламы на радио, телевиденье и в публичном транспорте в соотношении 2:30:1. Компания может использовать за месяц менее 10 минут эфирного времени на телевиденье и менее 100 минут на радио. На всю рекламу компания запланировала Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой издержать за месяц менее 900 усл. ден. ед. Составить математическую модель задачки действенного вложения в рекламу денег.

1.1.6

Необходимо перевести по стальной дороге 20 огромных и 150 малых контейнеров, используя при всем этом малое количество вагонов. Вес малого контейнера составляет 2 тонны, а огромного – 5 тонн. Грузоподъемность вагона – 60 тонн, недогрузка вагонов не допускается. Составить Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой математическую модель задачки перевозки всех контейнеров.

1.1.7

Из пт S в пункт T нужно перевести 250 ед. оборудования типа I, 120 – типа II, 340 – типа III на автомобилях вида А, В, С и D. Количество оборудования сразу вмещаемого на определенный автомобиль и издержки на одну поездку каждого автомобиля приведены в таблице:

Тип оборудования Количество оборудования Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой вмещаемого на автомобиль
А В С D
I II III
Издержки, руб.

Составить математическую модель задачки перевозки оборудования с наименьшими затратами.

1.1.8

Цех может выпускать 3 вида продукции, создание которых характеризуется последующими данными:

Продукция Время на создание ед. продукции, ч Количество металла на ед. продукции, кг Прибыль от реализации ед. продукции, руб Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой.
I вид II вид III вид

В планируемом месяце имеется 500 часов рабочего времени и 700 кг металла. Составить математическую модель задачки выпуска продукции с наибольшей прибылью от реализации.

1.1.9

Предприятие за 8 часов должно выпустить 25 единиц продукции вида П1 и 35 единиц продукции вида П2. Для производства продукции каждого вида Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой может быть применено оборудование А1 либо А2.

Производительность оборудования А1 по выпуску продукции П1 составляет 4 ед./ч, а по выпуску продукции П2 – 5 ед./ч., цена 1 часа работы оборудования А1 составляет 15 руб. Производительность оборудования А2 по выпуску продукции П1 составляет 3 ед./ч, а по выпуску продукции П2 – 2 ед./ч., цена 1 часа Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой работы оборудования А2 составляет 7 руб. Составить математическую модель задачки выпуска запланированной продукции с малой себестоимостью.

1.1.10

В плановом году строй организации городка перебегают к сооружению домов типов Д1, Д2, Д3 и Д4. Данные о количестве квартир различного типа в каждом из обозначенных типов домов, их плановая себестоимость приведены в Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой таблице:


Тип квартиры Тип дома
Д1 Д2 Д3 Д4
Однокомнатная Двухкомнатная Трехкомнатная Четырехкомнатная
Плановая себестоимость, ден. ед.

Годичный план ввода жилой площади составляет соответственно 1000, 1300, 1500 и 300 квартир обозначенных типов. Составить математическую модель задачки выполнения плана ввода квартир (а может быть, и его перевыполнения) с малой себестоимостью.

1.1.11

Нужно за 8 часов сделать 200 изделий, используя при Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой всем этом три станка. Производительность первого станка составляет 10 изделий в час, второго – 12 изделий в час, третьего – 9 изделий в час. Себестоимость 1-го изделия, сделанного на первом станке, составляет 3 руб., на втором станке – 2,8 руб., на 3-ем станке – 2,5 руб. Составить математическую модель задачки выпуска продукции на обозначенных станках с малой себестоимостью.

1.1.12

На Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой создание поступило 100 стержней длиной 1м, которые нужно разрезать на заготовки А длиной 0,3м и заготовки В длиной 0,2м. Для производства 1-го изделия требуется 1 заготовка А и 3 заготовки В. Составить математическую модель задачки раскроя стержней для производства наибольшего количества изделий.

1.2. Формы записи задач линейного программирования

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

где – данные действительные числа.

Симметричной (стандартной) формой записи ЗЛП именуется задачка максимизации мотивированной функции (1.3) при ограничениях вида (1.4) и (1.7) либо задачка минимизации мотивированной функции (1.3) при ограничениях вида (1.6) и (1.7), т. е.

либо

где – данные действительные числа.

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

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

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

2) Переход от неравенства вида « £ » к неравенству вида « ³ » (и напротив) также осуществляется умножением начального неравенства на (–1).

3) Переход от неравенства к равенству осуществляется введением дополнительной неотрицательной переменной. Так если в начальной модели , то, вводя , получим , а если в начальной модели , то, вводя Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой , получим , где .

4) При переходе от равенств к неравенствам можно управляться последующим: хоть какое уравнение эквивалентно системе 2-ух неравенств:

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

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

Пример 1.4

Пусть математическая модель задачки имеетследующий вид:

;

Записать для данной модели

а) ОЗЛП,

б) симметричную форму,

в) каноническую форму.

Решение

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

Тогда ОЗЛП будет иметь вид:

;

либо (раскрыв скобки):

;

Направьте внимание, что в ОЗЛП число переменных на одну возросло.

б) Для составления симметричной формы воспользуемся приобретенной ОЗЛП (т.к. в симметричной форме также на все переменные должно быть наложено условие неотрицательности). Чтоб Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой получить все ограничения вида « ³ » (т.к. мотивированная функция на минимум) нужно ограничение (1.9) помножить на (–1) (правило 2), а ограничение-равенство (1.10) поменять за ранее 2-мя ограничениями-неравенствами (правило 4):

откуда, умножив 2-ое ограничение системы на (–1), получим ограничение (1.11) вида « ³ ». Таким макаром, симметричная форма будет иметь вид:

;

где .

Направьте внимание, что в симметричной форме Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой возросло число ограничений (за счет подмены 1-го ограничения-равенства 2-мя ограничениями-неравенствами) и число переменных (за счет подмены одной переменной хоть какого знака на разность 2-ух неотрицательных переменных).

в) Для составления канонической формы воспользуемся приобретенной ОЗЛП (т.к. в канонической форме также на все переменные должно быть наложено условие Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой неотрицательности). Чтоб получить все ограничения вида « = » нужно из ограничений-неравенств (1.8 – 1.9) получить эквивалентные ограничения-равенства. Согласно правилу 3 для этого от левой части ограничения (1.8) отнимем новейшую неотрицательную переменную , а к левой части ограничения (1.9) прибавим новейшую неотрицательную переменную . Таким макаром, каноническая форма будет иметь вид:

;

где .

Пример 1.5

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

;

Записать для данной модели

а) ОЗЛП,

б) симметричную форму,

в) каноническую форму.

Решение

а) Чтоб все переменные задачки были неотрицательны, представим , где и .

Тогда ОЗЛП будет иметь вид:

;

где .

б) Для составления симметричной формы воспользуемся приобретенной ОЗЛП. Симметричная форма будет иметь вид:

;

где .

в) Для составления канонической формы воспользуемся приобретенной Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой ОЗЛП. Каноническая форма будет иметь вид:

;

где .

Задачки

Записать для данной модели (1.2.11.2.6)

а) ОЗЛП,

б) симметричную форму,

в) каноническую форму.

1.2.1 ; 1.2.3 ; 1.2.5 ; 1.2.2 ; 1.2.4 ; 1.2.6 ;

1.3. Геометрическая интерпретация и графический способ решения задач линейного программирования с 2-мя переменными

Графическим способом можно решать любые задачки линейного программирования с 2-мя переменными.

Пусть дана задачка

где – данные действительные числа.

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

Каждое из ограничений-неравенств (1.13,1.15,1.16) системы задает на плоскости некую полуплоскость. Каждое из ограничений-равенств (1.14) системы задает на плоскости некую прямую. И полуплоскость и ровная – выпуклые огромного количества. Т.к. скрещение хоть какого числа выпуклых множеств является выпуклым обилием, то область допустимых решений (ОДР) задачки является Рассмотрим приемы, позволяющие переходить от одной формы записи задачи к другой выпуклым обилием.

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

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

Область допустимых решений хоть какой задачки имеет менее 2-ух опорных прямых, на одной из которых может находиться среднее решение (рис. 1.1 – 1.2).

Рис. 1.1


rasstavte-pravilnie-prioriteti.html
rasstoyanie-do-etapa-320m.html
rasstoyanie-i-polozhenie-otnositelno-drug-druga.html