Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
ММО / лр по ммо 3.doc
Скачиваний:
19
Добавлен:
22.03.2015
Размер:
164.86 Кб
Скачать

Тема: Решение задач линейного программирования симплекс-методом

  1. Цель работы

1.1 Закрепить знания построения математической модели задачи ЛП

    1. Научится строить первый опорный план задачи ЛП

    2. Научится находить оптимальное решение задачи ЛП симплекс-методом

2. Теоретические сведения

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

2.1 Алгоритм симплекс-метода

Алгоритм симплексного метода состоит:

  1. Составление первого опорного плана.

а) Симплексная таблица начального опорного решения методом cимплексного метода при стремлении целевой функции к максимуму.

Коэффициенты целевой функции

c1

c2

cn

0

0

0

0

План

Базисные переменные

Значения

базисных переменных

х1

х2

xn

xn+1

xn+2

….

xn+m

zi

1

xn+1

xn+2

……

xn+m

b1

b2

…..

bm

а11

а21

аm1

a12

a22

am2

а1n

а2n

аmn

1

0

0

0

1

0

0

0

1

Индексная строка

F(X)

0

- c1

- c2

- cn

0

0

0

0

При стремлении целевой функции к минимуму опорное решение находится методом М- базиса.

Коэффициенты целевой функции

C *1

C *2

C*n

0

0

0

0

План

Базисные переменные

Значения

базисных переменных

х1

х2

xn

y1

y2

….

ym

zi

1

y1

y2

……

ym

b1

b2

…..

bm

а11

а21

аm1

a12

a22

am2

а1n

а2n

аmn

1

0

0

0

1

0

0

0

1

Индексная строка

F(X)

M(b1+…+bm)

-C *1

-C *2

-C* n

0

0

0

0

Для нахождения значений C *i надо переменные уi выразить через основные переменные (в уравнениях ограничителях) и подставить в целевую функцию.

    1. Проверка плана (решения) на оптимальность. Если все коэффициенты последней строки симплексной таблицы (F(X)) при решении на максимум неотрицательны, то план (решение) оптимален. Если хотя бы одно значение индексной строки меньше нуля, то план не оптимален, и его можно улучшить. (При решении ЗЛП на минимум целевой функции признаком оптимального плана являются отрицательные значения коэффициентов индексной строки) симплексной таблицы. Переходим к следующему этапу.

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

  2. Построение нового опорного плана. Разделить элементы ведущей строки предыдущей таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы значения , соответствующие введенной в базис переменной (на месте разрешающего элемента появится 1). А в остальные клетки ведущего столбца, включая и строку f , записываем нули.

Остальные новые элементы нового плана находятся по правилу прямоугольника НЭ = СЭ - (А∙В)/РЭ,

где НЭ- новый элемент, СЭ- старый элемент, РЭ- разрешающий элемент, А и В –элементы старого плана образующие прямоугольник с элементами СЭ и РЭ

Далее возвращаемся ко второму этапу - проверке на оптимальность.

Пример

Коммерческое предприятие реализует три группы товаров (А,В,С). плановые нормативы затрат ресурсов на 1 т. руб. товарооборота ,доход от продажи товаров на 1 т. руб. товарооборота , а так же объем ресурсов заданы. Определить плановый объем продаж и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

Виды ресурсов

Нормы затрат на 1т. руб. товарооборота.

объем ресурсов

А

В

С

Рабочее время продавцов

Площадь торговых залов

Площадь складских помещений

Доход

0,1

0,05

3

3

0,2

0,02

1

5

0,4

0,02

2

4

110

20

800

максимальный

Запишем математическую модель :

х1, х23 - количество продаваемых товаров;

Доход ( целевая функция ) определяется

F(X)= max(3 х1+5 х2+4 х3)

При условии

х1≥0; х2≥0; х3≥0;

и ограничениях

0,1х1+ 0,2х2+ 0,4х3≥1100

0,05х1+0,02х2+0,02х3≤120

1+ х2+ 2х3≤8000

Для построения первого опорного плана приведем запись ОЗЛП в канонической форме

F(X)= max(3 х1+5 х2+4 х3)

При условии

х1≥0; х2≥0; х3≥0;

и ограничениях

0,1х1+ 0,2х2+ 0,4х34 =1100

0,05х1+0,02х2+0,02х3+ х5 =120

1+ х2+ 2х3+ х6 =8000

Запишем математическую модель в векторном виде

F(X)=max(C∙X), где С=(3 5 4 0 0 0 ) – вектор-строка из коэфф. Целевой функции

х1

х2

Х= х3 - вектор-столбец переменных

х4

х5

х6

при условии вектор Х ≥0

и ограничениях А*Х=Р0,

где матрица

0,1 0,2 0,4 1 0 0 1100

А= 0,05 0,02 0,02 0 1 0 , Р0 = 120

3 1 2 0 0 1 8000

Находим первый опорный план

Базисные переменные: х3; х4; х5.

Свободные переменные: х1=0; х2=0; х3=0;

В этом случае значения базисных переменных равны значениям свободных членов. Построим таблицу

Коэффициенты целевой функции

3

5

4

0

0

0

План

Базисные переменные

Значения

базисных переменных

х1

х2

х3

х4

х5

х6

zi

1

х4

x5

x6

1100

120

8000

0,1

0,05

3

0,2

0,02

1

0,4

0,02

2

1

0

0

0

1

0

0

0

1

5500

6000

8000

Индексная строка

F(X)

0

- 3

- 5

-4

0

0

0

Первый опорный план не оптимален, т.к. в индексной строке находятся отрицательные коэффициенты. Значит будем строить новый план.

За ведущий столбец выбираем столбец с максимальным по модулю отрицательным элементом индексной строки (-5). Переменная х2 переходит из свободных в базисные.

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

Минимальное значение z определяет ведущую строку. Базисная переменная х4 переходит в свободные. Разрешающий элемент равен 0.2.

Формируем второй план таблицы.

Новые значения ведущей строки равны значению старого элемента деленного на разрешающий элемент.

Новые значения ведущего столбца равны нулю (включая и инд.строку), кроме элемента находящегося на пересечении ведущего столбца и ведущей строки. (Он равен 1).

Остальные элементы находятся по правилу прямоугольника

НЭ = СЭ - А∙В/РЭ

Например для элемента на пересечении х5 и х1 НЭ=0,05-0.01*0.02/0,2=0,04 и т.д.

План

Базисные переменные

Значения

базисных переменных

х1

х2

х3

х4

х5

х6

zi

2

х2

х5

x6

5500

10

2500

0,5

0,04

2,5

1

0

0

2

-0,02

0

5

-0,1

-5

0

1

0

0

0

1

11000

250

1000

Индексная строка

F(X)

27500

- 0,5

0

6

0

0

0

Этот план не оптимален. По вышеописанному алгоритму строим следующий план решения

План

Базисные переменные

Значения

базисных переменных

х1

х2

х3

х4

х5

х6

zi

3

х2

х1

x6

5375

250

1875

0

1

0

1

0

0

2,25

-0,5

1,25

5

-0,1

-5

6,25

-2,5

1,25

0

0

1

Индексная строка

F(X)

27625

0

0

5,75

23,75

12,5

0

При третьей итерации (приближении) получаем оптимальный план.

Следовательно фирма должна продавать 250 ед. товара А , 5375 ед. товара В , товар С не реализуется. Доход получат при этом максимальный – 27625. Оказывается недоиспользована площадь складских помещений на 1875 м2.

Индексная строка свободных переменных 3-го плана (х345) имеет ненулевые элементы. Это говорит о том , что данный план линейной задачи является единственным.

3. Задание

Выбрать одну задачу из приведенных ниже и выполнить следующие этапы по ее решению:

- записать математическую модель ЗЛП

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

- сделать выводы по полученным результатам.

Задача 1.

Предприниматель арендовал технологическую линию де­ревообрабатывающих станков для изготовления вагонки. Магазин «Стройматериалы» заказал комплекты из трех элементов: две ва­гонки длиной 2 м и одной вагонки длиной 1,25 м. Поставщик за­возит на грузовом автомобиле доски толщиной 20 мм, шириной 100 мм и длиной по 6,5 м — 200 шт. и длиной по 4 м — 50 шт.

Рассчитайте, как распилить доски, чтобы продать максималь­ное количество комплектов?

Задача 2.

Составьте дешевый вариант 1 т кормовой смеси в соответ­ствии с требованиями, представленными в следующей таблице:

Питательные вещества

Требования

% от веса

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

Люцерновая мука

Сухая барда

Рыбная мука

Соевый шрот

Белок

Не менее 35

17

25

60

45

Жиры

Не менее 1,5

2

5

7

0,5

Клетчатка

Не более 8

25

3

1

6,5

Вес

1 т

1

1

1

1

Стоимость руб. за 1 т

?

70

90

150

100

Задача 3

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

Вещества

Содержание питательных веществ в 1 кг фруктов

Нормы потребления, г

клубника

яблоки

смородина

Р1

3

2

1

30

Р2

1

3

4

70

Р3

0

0

5

40

Р4

1

0

1

50

Цена, руб. за 1 кг

1,0

0,5

0,8

Задача 4.

Сформируйте вариант образования бензина АИ-80 и АИ-95, который обеспечивает максимальный доход от продажи, если имеется 5 т смеси 1-го сорта и 30 т смеси 2-го сорта. На изго­товление бензина АИ-80 идет 60% смеси 1-го сорта и 40% смеси 2-го сорта, на изготовление бензина АИ-95 идет 80% смеси 1-го сор­та и 20% смеси 2-го сорта. Реализуется 1 т бензина АИ-80 за 5000 руб., а 1 т АИ-95 - за 6000 руб.

Задача 5.

Фирма производит два безалкогольных широко популяр­ных напитка «Колокольчик» и «Буратино». Для производства 1 л «Ко­локольчика» требуется 0,02 ч работы оборудования, а для «Бурати­но» - 0,04 ч, а расход специального ингредиента на них составляет 0,01 кг и 0,04 кг на 1 л соответственно. Ежедневно в распоряжении фирмы 16 кг специального ингредиента и 24 ч работы оборудования. Доход от продажи 1 л «Колокольчика» составляет 0,25 руб., а «Бура­тино» - 0,35 руб.

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

Задача 6.

Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для произ­водства одной детали типа В — 2 чел.-ч. Производственная мощ­ность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства детали типа А уходит 2 кг полимерного материала и 5 кг листового материала, а для про­изводства одной детали типа В — 4 кг полимерного материала и 3 кг листового металла. Еженедельные запасы каждого материала -по 10 000 кг. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук.

Определите, сколько деталей каждого вида следует производить, чтобы обеспечить максимальный доход от продажи за неделю, если доход от продаж одной детали типа А и В составляет соответствен­но 1,1 руб. и 1,5 руб.

Задача 7.

Брокеру биржи клиент поручил разместить 100 000 долл. США на фондовом рынке, сформировать портфель с ценными бумагами, чтобы получить максимальные годовые проценты с вло­женного капитала. Выбор ограничен четырьмя возможными объ­ектами инвестиций-акций А, В, С, Д, которые позволяют получить доход в размерах соответственно 6%, 8%, 10% и 9% годовых от вло­женной суммы. При этом клиент поручил не менее половины ин­вестиций вложить в акции А и В. С целью обеспечения ликвидно­сти не менее 25% общей суммы капитала нужно поместить в акции Д. Учитывая прогноз на изменение ситуации в будущем, в акции С можно вложить не более 20% капитала. Специфика налогообложе­ния указывает на необходимость вложения в акции А не менее 30% капитала.

Определите распределение инвестиций капитала, обеспечива­ющего максимальный годовой процентный доход.

Задача 8.

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

Судно

1

2

Пассажировместимость, чел.

2000

1000

Горючее, т

12000

7000

Экипаж, чел.

250

100

В месяц выделяется 60 000 т горючего. Потребность в рабочей силе не превышает 700 человек.

Определите количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн руб., а II типа - 10 млн руб. в месяц.

Задача 9.

Фирма производит и продает столы и шкафы из древеси­ны хвойных и лиственных пород. Расход каждого вида в кубомет­рах на каждое изделие задан в таблице.

Вид изделия

Расход древесины, м3

Цена изделия, тыс. руб.

Хвойные

Лиственные

Стол

0,15

0,2

0,8

Шкаф

0,3

0,1

1,5

Запасы древесины

80

40

Определите оптимальное количество столов и шкафов, которое следует поставлять на продажу для получения максимального дохо­да фирмы.

9

Соседние файлы в папке ММО