Задача 5 (задача портового флота)

Лабораторная работа №5. Решение задачи линейного программирования, ее графическая интерпретация и обобщенная транспортная задача

Задания

1. Решить задачи в соответствии с номером варианта. Варианты заданий по частям 1 и 2 приведены в таблице:

Таблица 1. Варианты заданий

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

3. На листе 2 рабочей книги Excel решить задачу части 2. . Установить размеры массива исходных данных в соответствии с вариантом, пересчитать результат. Изменить исходные данные, пересчитать результат

Задача 1

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

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

Таблица 2. Исходные данные

Указание: Из условия задачи следует, что грузоподъемность одного буксирного воза на линии А составляет 2×(300+n₁*100)+1×(500+n₁*100)+4*( 600+n₁*100)+0×(800+n₁*100) т., а на линии В она равна 2×(300+n₁*100)+2×(500+n₁*100)+0*(600+n₁*100)+4×(800+n₁*100) т (вычислить с помощью =СУММПРОИЗВ()). Если запланировать x₁ на линию А и x₂ возов на линию В, то добьемся общей грузоподъемности

Z=3600 x₁ + 4800 x₂ т.

Это – целевая функция, которую нужно максимизировать.

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

2x₁+2x₂≤20

x₁+2x₂≤14

4x₁+0x₂≤27

0x₁+4x₂≤24

Кроме того, очевидно, что x₁≥0, x₂≥0.

Задача 2

Автосборочный цех, выпускающий как легковые, так и грузовые автомобили, имеет в своем составе четыре цеха: кузнечно-прессовый, цех двигателей, сборочный легковых машин и сборочный грузовых машин, производительности которых (за месяц) указаны в таблице. Прибыль предприятия (в ден. ед.) от реализации одной грузовой машины – 250n₁; и одной легковой – 300n₂.

Таблица 3. Исходные данные

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

Указание: Если планировать месячный выпуск x₁ грузовых и x₂ легковых машин, то предприятие получит прибыль

Z=250 x₁ + 300 x₂.

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

Первое неравенство получено из таких соображений. Если кузнечно-прессовый цех выпускает x₂ легковых машин в месяц, то он на это затрачивает такую долю своей месячной производительности, которая выражается дробью x₂/32. Кроме того, цех работает на выпуск x₁ грузовых машин и затрачивает на это еще такую долю своей месячной производительности, которая выражается дробью x₁/53; сумма этих долей, очевидно, не превышает 1. Из тех же соображений составлено второе неравенство. Третье и четвертое неравенства непосредственно следуют из данных о производительности сборочных цехов.

К этим неравенствам, конечно, надо присоединить условие неотрицательности параметров управления: x₁≥0, x₂≥0.

Задача 3

На некотором направлении пароходство должно перевезти четыре груза в количествах, нижние пределы которых указаны в таблице 4. Для осуществления этих перевозок выделено два судна. Исходя из условий наилучшего использования грузоподъемности и грузовместимости и учитывая требования совместимости и грузовой специализации, каждое из выделенных судов может принять одновременно определенное количество каждого груза, указанное в таблице. Там же указаны эксплуатационные расходы выделенных судов (за рейс).

Таблица 4. Исходные данные

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

Указание: Если мы будем планировать для судна I x₁ рейсов, а для судна II x₂ рейсов, то понесем суммарные расходы (в руб.)

Z=20000x₁ + 21000x₂

Это – целевая функция, которую надо минимизировать.

При планируемом числе рейсов удастся перевезти (4000 x₁ + 3000 x₂) т. груза А, (2000 x₁ + 3000 x₂) т. груза Б, (0 x₁ + 4000 x₂) т. груза В и (3000 x₁ + 0 x₂) т. груза Г. Имея в виду указанные в таблице нижние пределы заданного объема перевозок по каждому ограничению, получаем неравенства ограничений:

4000 x₁ + 3000 x₂≥30000

2000 x₁ + 3000 x₂≥12000

4000 x₂≥4000

3000 x₁≥4000

По этим неравенствам следует строить область ограничений.

Задача 4

За время Т=3 ед. (например, 3 мес.) необходимо перевезти на линии 1 – 18000т+1000 n₁, а на линии 2 – 48000 т+1000 n₂. грузов. Для этих перевозок можно использовать суда двух типов, для которых известны провозные способности и эксплуатационные расходы, указанные в таблице.

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

Таблица 5. Исходные данные

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

x₁₁ – время работы судов I типа на линии 1;

x₁₂ – время работы судов I типа на линии 2;

x₂₁ – время работы судов II типа на линии 1;

x₂₂ – время работы судов II типа на линии 2.

При таком плане эксплуатационные расходы составят сумму (в тыс. руб.):

Z=10 x₁₁ + 15 x₁₂ + 24 x₂₁ + 30 x₂₂,

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

Ограничения задачи запишутся в виде следующих соотношений:

x₁₁ + x₁₂≤3

x₂₁ + x₂₂ ≤3

3 x₁₁ + 9x₂₁ =18

16 x₁₂ + 30x₂₂ =48,

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

К этим ограничениям добавляется требование неотрицательности параметров управления:

x₁₁ ≥ 0; x₁₂ ≥ 0; x₂₁ ≥ 0; x₂₂ ≥ 0.

Полученная задача линейного программирования имеет четыре параметра управления, и для того, чтобы ее можно было представить на плоскости, надо свести ее к задаче с двумя переменными. Это можно сделать, выразив, например, из двух последних ограничений – равенств переменные x₂₁ и x₂₂ через переменные x₁₁ и x₁₂. Тогда после простейших вычислений получим задачу:

Z= 2 x₁₁ - x₁₂ +96→ min

x₁₁ + x₁₂≤3

5 x₁₁ + 8 x₁₂ ≥ 9

x₁₁≤6

x₁₂ ≤3

x₁₁≥0; x₁₂ ≥ 0.

Задача 5 (задача портового флота)

В составе портового флота имеется m типов судов, которые используются для перевозок пассажиров на n пригородных линиях. Число судов i-того типа равно a_i (i=1, 2,…m), а среднесуточное число пассажиров, которых надо перевозить на j-той линии, равно b_j (j=1, 2, …n). Суточная провозная способность i того типа судна на j-той линии равна p_ij (пассажиров), а соответствующие эксплуатационные расходы равны c_ij (руб.)

Требуется найти такую расстановку судов по линиям, при которой достигается минимум эксплуатационных расходов.

Обозначая через x_ij число судов i-того типа, которые назначаются для перевозок на j-той линии, получаем, что суточные расходы будут:

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

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

К этому надо присоединить требования неотрицательности: xij≥0.

Таблица 6. Числовые значения для решения распределительной задачи