10663

Решение задач линейного программирования

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа 13 Решение задач линейного программирования. Цель работы. Научиться решать одну из задач оптимизации: исходя из конкретной ситуации составить совокупность линейных ограничений в виде системы неравенств а также функцию цели. Для этой фун

Русский

2013-03-30

708 KB

4 чел.

Лабораторная  работа  13

Решение задач линейного программирования.

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

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

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

                          (1)

и доставляют данной функции

                                              (2)

наименьшее (или наибольшее) значение.

Здесь:

 -   называется  целевой функцией,

- условия  (1) – ограничениями,

- каждый набор переменных, удовлетворяющий (1), называ-ется допустимым решением,

- допустимое решение, минимизирующее или максимизирующее функцию  , называется оптимальным.  

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

Порядок выполнения работы.   

- переписать задание в соответствием со своим вариантом,

- исходя из условия, составить систему ограничительных неравенств,

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

- в координатной плоскости  построить все линии, входящие в систему неравенств,

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

- построить линию уровня  функции ,

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

- найти координаты    и   этой точки, соответствующей пересечению двух прямых,

- подставив эти координаты в функцию цели , найдем ее значение, которое должно соответствовать максимальному доходу (или минимальным затратам – в зависимости от содержания задачи),

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

- сделать выводы по работе.

Исходные  данные к работе.  

       Для  вариантов:  1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29.

Задача о выпуске продукции.  

 

    1.  Изготовление продукции двух видов   и   требует использования четырех видов сырья:    и  . Запасы сырья составляют соответст-венно    и   условных единиц.. Количество единиц сырья,  необхо-димое для изготовления единицы каждого из видов продукции известно и задается таблицей:

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=22.1

=1.8

=2.9

=14.3

=1.9

=1.0

=14.0

=0

=3.0

=17.2

=3.3

=0.2

Доход

=7.6

=4.9

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

        Для  вариантов:  2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30.

   Задача о рационе питания.

     2.   При откорме животное должно получить не менее    и   единиц питательных веществ видов    и   . Для составления рациона использу-ются два вида корма:    и   . Содержание количества единиц  питатель-ных веществ в каждом корме, а также стоимость  1 кГ корма приводятся в таблице:

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.6

=3.2

=1.2

=7.4

=1.1

=2.4

=13.1

=1.2

=6.5

Стоимость

=5.4

=7.1

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

3.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=38.2

=4.4

=6.2

=26.4

=4.1

=1.3

=30.3

=0

=5.9

=35.0

=5.9

=0

Доход

=16.2

=11.3

4.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=17.4

=5.7

=2.0

=15.2

=1.9

=3.8

=22.1

=2.1

=11.7

Стоимость

=7.9

=13.2

5.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=18.6

=1.7

=2.8

=12.4

=1.8

=0.8

=14.7

=0.2

=2.6

=17.2

=2.4

=0

Доход

=6.6

=4.7

6.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.2

=3.0

=1.1

=8.3

=1.2

=2.3

=12.1

=1.2

=6.3

Стоимость

=4.4

=6.3

7.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=24.4

=3.3

=2.4

=15.6

=2.4

=1.2

=16.1

=1.1

=3.6

=19.8

=3.6

=0.7

Доход

=4.9

=8.2

8.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=4.6

=1.6

=0.7

=4.1

=0.6

=1.1

=6.2

=0.7

=3.2

Стоимость

=1.8

=3.1

9.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=9.4

=1.3

=1.5

=6.6

=1.1

=0.6

=7.2

=0

=1.9

=8.9

=1.7

=0.1

Доход

=5.6

=7.9

10.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=34.8

=11.6

=4.1

=30.5

=3.8

=7.7

=41.3

=4.4

=23.1

Стоимость

=15.2

=27.1

11.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=19.2

=1.3

=1.5

=12.8

=2.7

=1.2

=14.6

=0

=3.1

=18.4

=2.9

=0

Доход

=8.8

=3.7

12.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=7.2

=2.6

=0.7

=6.4

=0.7

=1.9

=11.1

=0.8

=5.4

Стоимость

=3.7

=5.7

13.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=37.4

=4.7

=6.2

=28.1

=5.1

=1.6

=29.2

=0

=7.1

=33.3

=6.4

=0

Доход

=14.9

=11.2

14.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=14.1

=5.1

=1.4

=12.7

=1.3

=3.6

=21.4

=1.5

=11.2

Стоимость

=7.2

=12.1

15.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=6.6

=0.7

=1.2

=4.1

=0.8

=0.3

=5.1

=0

=1.2

=6.4

=1.1

=0

Доход

=2.7

=1.9

16.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=3.6

=1.3

=0.4

=3.2

=0.3

=0.9

=5.7

=0.4

=2.7

Стоимость

=1.9

=2.6

17.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=13.2

=1.5

=2.5

=8.6

=1.7

=0.7

=10.2

=0

=2.4

=12.4

=2.3

=0

Доход

=5.6

=3.7

18.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.1

=3.1

=1.3

=8.3

=1.2

=2.2

=11.9

=1.1

=6.4

Стоимость

=4.7

=6.9

19.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=4.7

=0.7

=0.7

=3.3

=0.6

=0.3

=3.6

=0

=0.9

=4.5

=0.8

=0

Доход

=2.9

=3.9

20.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=12.7

=4.4

=1.7

=11.5

=1.5

=3.1

=17.6

=1.5

=9.1

Стоимость

=6.6

=9.5

21.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=12.2

=1.6

=1.2

=7.8

=1.2

=0.6

=8.2

=0.5

=1.8

=9.6

=1.8

=0

Доход

=2.7

=4.1

22.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=6.4

=2.1

=0.8

=10.7

=0.8

=1.6

=8.8

=0.9

=4.6

Стоимость

=3.5

=4.7

23.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=19.1

=2.2

=3.1

=13.2

=2.1

=0.6

=15.2

=0

=2.7

=17.2

=2.8

=0

Доход

=7.4

=5.8

24.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=19.1

=6.5

=2.5

=21.7

=2.3

=4.7

=26.3

=2.4

=13.7

Стоимость

=10.1

=14.2

25.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=16.2

=1.7

=2.6

=11.0

=1.8

=0.9

=12.4

=0

=2.3

=15.6

=2.4

=0

Доход

=6.6

=4.2

26.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=9.6

=3.2

=1.2

=10.4

=1.1

=2.3

=13.2

=1.1

=6.8

Стоимость

=5.1

=7.1

27.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=21.4

=2.3

=3.5

=14.7

=2.1

=1.2

=17.2

=0

=3.3

=20.4

=3.4

=0

Доход

=8.3

=6.9

28.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=12.7

=4.4

=1.7

=11.5

=1.5

=3.1

=17.6

=1.6

=9.1

Стоимость

=6.6

=9.5

29.

Виды

сырья

Запасы сырья

Нормы расхода на единицу продукции

=10.7

=1.1

=1.7

=7.6

=1.0

=0.5

=8.1

=0

=1.7

=10.2

=1.8

=0

Доход

=6.6

=4.2

30.

Питательные

вещества

Требуемое

количество

питательных

веществ

Содержание питательных

веществ в кормах

=7.1

=2.6

=0.7

=6.8

=0.6

=1.8

=11.1

=0.8

=5.6

Стоимость

=3.6

=6.1

         Пример расчета.   

  1.  Цель работы:   решить данную задачу оптимизации методом линейного программирования.
  2.  Исходные данные:

При откорме животное должно получать не менее b1, b2 и b3 единиц питательных веществ видов:  V1, V2 и V3. Для составления рациона используют два вида корма:  K1 и K2. Содержание количества единиц питательных веществ в каждом корме, а также стоимость 1 кг корма приведены в таблице:

питательные

требуемое количество

Содержание питательных веществ в кормах

вещества

питательных веществ

К1

К2

V1

b1=4,6

a11=1,6

a12=0,7

V2

b2=4,1

a21=0,6

a22=1,1

V3

b3=6,2

a31=0,7

a32=3,2

Стоимость

c1=1,8

c2=3,1

Необходимо составить дневной рацион из кормов K1 и K2 нужной питательности, чтобы при этом затраты оказались минимальными.

  1.  Ограничительные условия вытекают из системы неравенств:

                                         

  1.  Функция цели:

                                        

    5.Строим многоугольник допустимых решений и линию уровня F=0:

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

выражаем               

подставляем    в другое уравнение и получаем, что

  

тогда       

7.Определяем   минимальное,  подставляя координаты точки  А в уравнение линии уровня:

8. Выводы: Выполняются студентом самостоятельно.


 

А также другие работы, которые могут Вас заинтересовать

37435. Організація обліку готової сільськогосподарської продукції 239.83 KB
  Визначити, класифікувати та описати порядок оцінки готової сільськогосподарської продукції; визначити основні завдання організації обліку готової сільськогосподарської продукції; визначити нормативно-правове регулювання обліку готової сільськогосподарської продукцції; визначити особливості документування господарсьих операцій повʼязаних з випуском готової сілльськогосподарської продукції...
37436. Управління пасажирським судном 233.5 KB
  Старший бортпровідник безпосередньо підкоряється помічникові капітана по пасажирській частині, керує роботою бортпровідників, днювальних, що обслуговують пасажирські приміщення, і забезпечує стан пасажирських приміщень у належному порядку.
37437. История России. Шпаргалка 228.68 KB
  Империя – это конгломерат народов, которые образуют экономическую, политическую и в зачатке культурную систему, где ведущая определяющая, объединяющая роль принадлежит одному или нескольким народам, в то время как остальные народы находятся в состоянии зависимости и подчинения, хотя и извлекают определенные выгоды из своего положения в рамках данного конгломерата.
37438. Икемділік ұғымы. Сұраныс пен ұсыныс икемділігі 154 KB
  Рыноктық экономика – бұл сұраныс пен ұсыныстың үздіксіз арақатынасы. Мұндай қарым-қатынасты қарапайым моделінің тууы, экономикалық ғылым тарихында үлкен маңызды дәуір болып саналады. Сол мезеттен бері екі ғасырдан астам уақыт өтсе де, рыноктық экономикамен теориялық танысу осыдан басталады. Өйткені осы модель арқылы барлық экономикалық процестер ашылып көрсетіледі.
37439. Финансовый мененджмент 212.87 KB
  Финансовый менеджмент– это управление финансово-хозяйственной деятельностью фирмы на основе использования современных методов. Основным лицом ответственным за достижение цели финансового менеджмента, является вице-президент по финансовым вопросам (заместитель директора по финансовым вопросам).
37440. Обеспечение единства измерений в стране. Государственный метрологический надзор. Цели надзора, сфера распространения. Виды метрологического надзора 19.86 KB
  Проверки проводят должностные лица Госстандарта России - главные государственные инспекторы и государственные инспекторы по обеспечению единства измерений, действующие на соответствующих территориях и аттестованные в установленном порядке.
37441. Виды и средства измерений. Виды эталонов. Стандартные образцы 19.55 KB
  Прямые измерения — это непосредственное сравнение физической величины с ее единицей. Например, при определении длины предмета с помощью линейки происходит сравнение искомой величины (количественного выражения значения длины) с мерой, т. е. единицей измерения.
37442. Факторы, сохраняющие качество товаров 16.91 KB
  Режим хранения - это совокупность условий, при которых товар сохраняет свое качество. Для каждого товара необходим определенный режим хранения, зависящий от его состава и свойств. При правильном режиме не только сохраняется качество, но и снижаются потери товаров.
37443. Потребительские свойства товаров. Общие понятия и номенклатура потребительских свойств 17.07 KB
  Свойства товаров, обусловливающие их пригодность удовлетворять определенные потребности населения и проявляющиеся в процессе эксплуатации или потребления, называют потребительскими. В совокупности потребительские свойства составляют качество.