Задачи линейного программирования

Министерство  образования и науки РФ

Государственное образовательное учреждение

высшего профессионального образования

ВлГУ

Кафедра СК 
 

Отчет по лабораторным работам 

на тему:

Задачи  линейного программирования

по дисциплине:

Численные методы в строительстве

Вариант № 9. 
 
 
 
 
 
 
 

Выполнил:

ст. гр. ЗСв-210

И.А. Тимофеев

Проверил:

В.А. Репин 
 
 
 
 
 

Владимир, 2011

Цель  работы:

      Изучить и освоить методику составления  математической модели задач линейного  программирования, решения задачи на компьютере, анализировать полученное решение.

 Краткая теоретическая часть:

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

      Целевая функция является функцией проектных  параметров, а ограничение существует в виде системы линейных уравнений  или неравенств.

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

• транспортная задача;
• составление оптимального производственного плана;
• задача составления смеси;
• задача оптимального раскроя материала;
• задача застройки жилого квартала.

      Рассмотрим  математические модели транспортной задачи, задачи составления оптимального производственного  плана и задачи оптимального раскроя  материала.

Ход работы:

Задача  № 1. Транспортная задача.

      Условие: три потребителя обслуживаются четырьмя поставщиками. Производительность каждого поставщика соответственно составляет 80, 85, 75, 60 т. Потребность потребителей соответственно 120,150,130 т. Стоимость перевозки единицы объема товара к 1, 2, 3-ему потребителю от каждого поставщика составляет:

      от  поставщика-1  6, 2, 8 финансовых единиц (ф.е.);

      от  поставщика-2  2, 5, 3 ф.е.;

      от  поставщика-3  4, 10, 6 ф.е.;

      от  поставщика-4  8, 7, 6 ф.е.

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

      Решение: математическая модель задачи. 
 

          Пусть - количество товара в т, перевозимого от i-го поставщика к j-ому потребителю.

    Общая производительность поставщика в товаре меньше общей потребности потребителей. Добавляю в задачу условного поставщика V, которому в качестве «предложения» приписываются излишки «спроса». Тарифы на перевозку до условного потребителя будут равны нулю.

 

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

F = 6x₁₁ + 2x₁₂ + 8x₁₃ + 2x₂₁ + 5x₂₂ + 3x₂₃ + 4x₃₁ + 10x₃₂+

+ 6x₃₃ + 8x₄₁ + 7x₄₂ + 6x₄₃ + 0x₅₁ + 0x₅₂ + 0x₅₃ ® min                         

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

    x₁₁ + x₁₂ + x₁₃.

    Эта сумма равна 80, поскольку вывозится вся смесь.

    x₁₁ + x₁₂ + x₁₃ = 80.

    Аналогично  для поставщика-2, поставщика-3 и поставщика-4 получаю:

    x₂₁ + x₂₂ + x₂₃ = 85

    x₃₁ + x₃₂ + x₃₃ = 75

    x₄₁ + x₄₂ + x₄₃ = 60

    x₅₁ + x₅₂ + x₅₃ = 100.

    Потребители, в свою очередь, получают товар от каждого поставщика.

    Так как потребность каждого из потребителей полностью удовлетворяется количеством товара, полученного от поставщика-1, поставщика-2, поставщика-3,поставщика-4, поставщика-5 то:

                              x₁₁ + x₂₁ + x₃₁ + x₄₁ + x₅₁ = 120,

                              x₁₂ + x₂₂ + x₃₂ + x₄₂ + x₅₂ = 150,

                              x₁₃ + x₂₃ + x₃₃ + x₄₃ + x₅₃ = 130.

    Переменные неотрицательны, так как с экономической точки зрения обратные перевозки не имеют смысла, поэтому х_ij ³ 0. отсюда имеем:

       x₁₁ + x₁₂ + x₁₃ = 80,

    x₂₁ + x₂₂ + x₂₃ = 85,

    x₃₁ + x₃₂ + x₃₃ = 75,

    x₄₁ + x₄₂ + x₄₃ = 60,

    x₅₁ + x₅₂ + x₅₃ = 100,

                              x₁₁ + x₂₁ + x₃₁ + x₄₁ + x₅₁ = 120,

                              x₁₂ + x₂₂ + x₃₂ + x₄₂ + x₅₂ = 150,

                              x₁₃ + x₂₃ + x₃₃ + x₄₃ + x₅₃ = 130

                              х_ij ³ 0; i = 1, 2, 3; j = 1, 2, 3, 4, 5. 

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

    Решение данной задачи с использованием табличного процессора MS Excel.

      Вывод: решена транспортная задача открытого типа, оптимальный план поставки товара заключается в доставке от поставщика №1 к потребителю №2 – 80 т, от поставщика №2 к потребителю №1 – 45 т, к №3 – 40 т, от поставщика № 3 к потребителю №1 – 75 т, от поставщика №4 к потребителю №3 – 60 т, при этом, общие затраты на перевозку всего товара составят 1030 ф.е. 

      Задача  № 2. Составление  оптимального производственного  плана.

      Условие: заводу требуется составить оптимальный производственный план по выпуску четырех видов изделий при определенных возможностях пяти видов машин, на которых последовательно обрабатываются эти изделия. Важным является получение заводом максимальной прибыли.

      Существуют  следующие технические условия на обработку этих изделий: 1-й вид машин имеет предел времени беспрерывной работы в течение 78 часов; 2-й – в течение 86 часов; 3-й – в течение 95 часов; 4-й – в течение 108 часов; 5-й – в течение 126 часов. Продолжительность обработки каждого вида изделия на каждом из вдов машин представлена в виде таблицы.

      От  реализации выпускаемой продукции завод получает прибыль.

      Решение: математическая модель приведенной задачи. Обозначу за х₁ количество изделий, которых нужно выпустить, продукции 1-го вида, за х₂ – количество изделий продукции 2-го вида, за х₃ – количество изделий продукции 3-го вида, за х₄ – количество изделий продукции 4-го вида.