Лабораторная работа5 задание


Лабораторная работа №5. Решение задачи линейного программирования, ее графическая интерпретация и обобщенная транспортная задача
Задания
Решить задачи в соответствии с номером варианта. Варианты заданий по частям 1 и 2 приведены в таблице:
Таблица SEQ Таблица \* ARABIC 1. Варианты заданий
Последняя цифра номера зачетки Часть 1 Часть 2
Номер задачи Размер исходного массива
Задача 1 Задача 5 5 x 4
Задача 2 Задача 6 4 x 5
Задача 3 Задача 7 7 x 6
Задача 4 Задача 5 5 x 7
Задача 1 Задача 6 5 x 8
Задача 2 Задача 7 5 x 6
Задача 3 Задача 5 6 x 7
Задача 4 Задача 6 6 x 4
Задача 1 Задача 7 6 x 5
Задача 2 Задача 5 6 x 6
Для части 1 выполнить графическое изображение многоугольника ограничений на плоскости. Построить график целевой функции, проходящий через точку оптимального решения.
На листе 2 рабочей книги Excel решить задачу части 2. . Установить размеры массива исходных данных в соответствии с вариантом, пересчитать результат. Изменить исходные данные, пересчитать результат
Задача 1
Для осуществления буксирно-баржевых перевозок на двух линиях А и В портовый флот располагает определенным числом барж четырех типов. По условиям эксплуатации буксирный воз для каждой линии должен состоять из определенного набора барж разных типов.
Требуется распределить имеющиеся баржи по линиям А и В так, чтобы общая грузоподъемность возов была наибольшей. Исходные данные указаны в таблице.
Таблица SEQ Таблица \* ARABIC 2. Исходные данные
Тип баржи Грузоподъемность баржи Состав буксирного воза Количество имеющихся барж
Линия АЛиния ВI 300+n1*100 2 2 20+n2
II 500+n1*100 1 2 14+n2
III 600+n1*100 4 0 27+n2
IV 800+n1*100 0 4 24+n2
Указание: Из условия задачи следует, что грузоподъемность одного буксирного воза на линии А составляет 2(300+n1*100)+1(500+n1*100)+4*( 600+n1*100)+0(800+n1*100) т., а на линии В она равна 2(300+n1*100)+2(500+n1*100)+0*(600+n1*100)+4(800+n1*100) т (вычислить с помощью =СУММПРОИЗВ()). Если запланировать x1 на линию А и x2 возов на линию В, то добьемся общей грузоподъемности
Z=3600 x1 + 4800 x2 т.
Это – целевая функция, которую нужно максимизировать.
Имеем ограничения по числу барж каждого типа, их можно записать в виде неравенств:
2x1+2x2≤20
x1+2x2≤14
4x1+0x2≤27
0x1+4x2≤24
Кроме того, очевидно, что x1≥0, x2≥0.
Задача 2
Автосборочный цех, выпускающий как легковые, так и грузовые автомобили, имеет в своем составе четыре цеха: кузнечно-прессовый, цех двигателей, сборочный легковых машин и сборочный грузовых машин, производительности которых (за месяц) указаны в таблице. Прибыль предприятия (в ден. ед.) от реализации одной грузовой машины – 250n1; и одной легковой – 300n2.
Таблица SEQ Таблица \* ARABIC 3. Исходные данные
Цех Месячный выпуск машин, тыс.штук
Грузовых Легковых
Кузнечно-прессовый53,000 32,0
Двигателей 61,6 33,0
Сборочный грузовых машин 18,0+ n1 -
Сборочный легковых машин - 26,0+ n2
Требуется составить месячный план выпуска легковых и грузовых машин, обеспечивающий достижение максимальной прибыли.
Указание: Если планировать месячный выпуск x1 грузовых и x2 легковых машин, то предприятие получит прибыль
Z=250 x1 + 300 x2.
Это – целевая функция, которую нужно максимизировать. Ограниченные производственные мощности цехов приводят к неравенствам:

Первое неравенство получено из таких соображений. Если кузнечно-прессовый цех выпускает x2 легковых машин в месяц, то он на это затрачивает такую долю своей месячной производительности, которая выражается дробью x2/32. Кроме того, цех работает на выпуск x1 грузовых машин и затрачивает на это еще такую долю своей месячной производительности, которая выражается дробью x1/53; сумма этих долей, очевидно, не превышает 1. Из тех же соображений составлено второе неравенство. Третье и четвертое неравенства непосредственно следуют из данных о производительности сборочных цехов.
К этим неравенствам, конечно, надо присоединить условие неотрицательности параметров управления: x1≥0, x2≥0.
Задача 3
На некотором направлении пароходство должно перевезти четыре груза в количествах, нижние пределы которых указаны в таблице 4. Для осуществления этих перевозок выделено два судна. Исходя из условий наилучшего использования грузоподъемности и грузовместимости и учитывая требования совместимости и грузовой специализации, каждое из выделенных судов может принять одновременно определенное количество каждого груза, указанное в таблице. Там же указаны эксплуатационные расходы выделенных судов (за рейс).
Таблица SEQ Таблица \* ARABIC 4. Исходные данные
Груз Количество груза, которое надо перевезти (не менее), т. Количество груза, перевозимое за 1 рейс, т.
на судне I на судне II
А 30000 4000 3000
Б 12000+100* n1* n2 2000 3000
В 8000+1000 n1 - 5000
Г 8000+1000 n2 3000 -
Эксплуатационные расходы 20000+100* n1 21000+ 100*n2
Требуется составить план, обеспечивающий перевозку предъявленных грузов с наименьшими расходами.
Указание: Если мы будем планировать для судна I x1 рейсов, а для судна II x2 рейсов, то понесем суммарные расходы (в руб.)
Z=20000x1 + 21000x2
Это – целевая функция, которую надо минимизировать.
При планируемом числе рейсов удастся перевезти (4000 x1 + 3000 x2) т. груза А, (2000 x1 + 3000 x2) т. груза Б, (0 x1 + 4000 x2) т. груза В и (3000 x1 + 0 x2) т. груза Г. Имея в виду указанные в таблице нижние пределы заданного объема перевозок по каждому ограничению, получаем неравенства ограничений:
4000 x1 + 3000 x2≥30000
2000 x1 + 3000 x2≥12000
4000 x2≥4000
3000 x1≥4000
По этим неравенствам следует строить область ограничений.
Задача 4
За время Т=3 ед. (например, 3 мес.) необходимо перевезти на линии 1 – 18000т+1000 n1, а на линии 2 – 48000 т+1000 n2. грузов. Для этих перевозок можно использовать суда двух типов, для которых известны провозные способности и эксплуатационные расходы, указанные в таблице.
Требуется составить план работы судов, обеспечивающий выполнение заданного объема перевозок в указанное время с минимальными эксплуатационными расходами.
Таблица SEQ Таблица \* ARABIC 5. Исходные данные
Тип судна Провозные способности судов в единицу времени на линии 1, тыс. Т. Эксплуатационные расходы судов за единицу времени, тыс. Руб.
на линии 1 на линии 2 на линии 1 на линии 2
I 6 16 10 15
II 9 30 24 30
Указание: В качестве параметров управления выберем время, назначенное судну каждого типа для работы на каждой из линий, так что намечаемый план работы судов будет состоять из следующих величин:
x11 – время работы судов I типа на линии 1;
x12 – время работы судов I типа на линии 2;
x21 – время работы судов II типа на линии 1;
x22 – время работы судов II типа на линии 2.
При таком плане эксплуатационные расходы составят сумму (в тыс. руб.):
Z=10 x11 + 15 x12 + 24 x21 + 30 x22,
которая составляет целевую функцию, ее надо минимизировать.
Ограничения задачи запишутся в виде следующих соотношений:
x11 + x12≤3
x21 + x22 ≤3
3 x11 + 9x21 =18
16 x12 + 30x22 =48,
где первые два выражают требование выполнить перевозки в заданное время, а последние два выражают требование выполнить заданный объем перевозок на каждой линии.
К этим ограничениям добавляется требование неотрицательности параметров управления:
x11 ≥ 0; x12 ≥ 0; x21 ≥ 0; x22 ≥ 0.
Полученная задача линейного программирования имеет четыре параметра управления, и для того, чтобы ее можно было представить на плоскости, надо свести ее к задаче с двумя переменными. Это можно сделать, выразив, например, из двух последних ограничений – равенств переменные x21 и x22 через переменные x11 и x12. Тогда после простейших вычислений получим задачу:
Z= 2 x11 - x12 +96→ min
x11 + x12≤3
5 x11 + 8 x12 ≥ 9
x11≤6
x12 ≤3
x11≥0; x12 ≥ 0.Задача 5 (задача портового флота)
В составе портового флота имеется m типов судов, которые используются для перевозок пассажиров на n пригородных линиях. Число судов i-того типа равно ai (i=1, 2,…m), а среднесуточное число пассажиров, которых надо перевозить на j-той линии, равно bj (j=1, 2, …n). Суточная провозная способность i того типа судна на j-той линии равна pij (пассажиров), а соответствующие эксплуатационные расходы равны cij (руб.)
Требуется найти такую расстановку судов по линиям, при которой достигается минимум эксплуатационных расходов.
Обозначая через xij число судов i-того типа, которые назначаются для перевозок на j-той линии, получаем, что суточные расходы будут:

Эту функцию надо минимизировать. При этом ограничения по числу судов каждого типа запишутся в виде неравенства:

а ограничения, вытекающие из заданных объемов перевозок, будут

К этому надо присоединить требования неотрицательности: xij≥0.
Таблица SEQ Таблица \* ARABIC 6. Числовые значения для решения распределительной задачи
Судно Провозная способность, тыс. Пассажиров в сутки Число судов
на линии 1 на линии 2 на линии 3 на линии 4 1 0,8 0,6 1,5 0,7 24
2 2,3 2,2 2,0 1,9 16
3 1,2 0,9 0,8 1,0 15
4 1,2 1,0 0,9 0,8 9
Объем перевозок, тыс. пассажиров 30 17 18 17 Судно Эксплуатационные расходы, тыс. руб. в сутки Число судов
на линии 1 на линии 2 на линии 3 на линии 4 1 0,4 0,5 0,9 1,0 24
2 2,5 2,1 2,5 2,0 16
3 0,8 1,0 1,4 2,0 15
4 1,2 1,6 1,5 1,0 9
Задача 6 (о специализации судоремонтных предприятий)
На морском бассейне имеется n судоремонтных заводов. Необходимо решить вопрос о наиболее рациональном распределении m типов судов [в каждом типе аi единиц (i=1, 2, …, m)] для ремонта на этих заводах.
Пусть сij – расходы (в руб.) на ремонт одного судна типа i на заводе номер j. Обозначим через xij число судов i-го типа, которые планируется ремонтировать на j-м заводе. Тогда суммарные расходы на ремонт всех судов выразятся следующим образом:

Это целевая функция, ее надо минимизировать.
Составляя ограничения, нужно, прежде всего, учесть необходимость отремонтировать все суда:

Производственные мощности каждого завода можно учесть на основании таких соображений. Пусть τj- число суток (или смен) работы j-го завода, которое завод может выделить в течение планируемого периода на ремонт судов данного бассейна, а tij- время, необходимое для ремонта одного судна i-го типа на j=м заводе.
Тогда условие, ограничивающее загрузку каждого из заводов, запишутся в виде неравенства:

Произвести модификацию и использовать таблицу из задачи 1 для решения этой задачи.
Задача 7 (о распределении вагонов под погрузку)
Одно из важных условий взаимодействия морского и железнодорожного транспорта заключается в рациональном регулировании вагонного парка в пределах портового узла, т.е. в рациональном распределении вагонов разных типов (крытых, полувагонов, платформ с разным числом осей и различной грузоподъемностью и т.д.) под различные грузы.
Допустим, что порт обеспечивается вагонами m типов для погрузки n различных грузов. Число вагонов i-го типа равно ai (i=1, 2, …, m), а количество j-го груза, предъявленного к отправлению, равно bj (j=1,2, … n). Известно, что грузоподъемность одного вагона i-го типа при его загрузке j-м грузом равна pij, а норма времени при погрузке j-го груза на вагон i-го типа – tij.
Если обозначить через xij число вагонов i-го типа, планируемых под j-й груз, то эту задачу следует рассматривать как задачу о минимизации суммарного времени погрузки всех предъявленных грузов. Это время будет:

и функцию z надо минимизировать при ограничениях:


xij≥0, которые выражают ограниченность числа вагонов каждого типа и необходимость отправить все грузы.
Замечание. Если вагоны i-го типа не подходят для погрузки j-го груза, то это можно отразить, выбрав соответствующий коэффициент tij сколь угодно большим числом.
Примечание. Исходные данные для задач 6 и 7 можно выбирать произвольно, согласно их смыслу.

Приложенные файлы

  • docx 19349996
    Размер файла: 47 kB Загрузок: 0

Добавить комментарий