Номер варианта заданий соответствует списочному номеру студента
Лабораторная работа № 1
Решение задачи линейного программирования графическим методом
Цель: научиться решать задачи линейного программирования графическим методом; уметь давать экономическую интерпретацию полученного решения.
Теоретическая часть
Задача
Найти X1 и X2 удовлетворяющие системе неравенств:
(37)
условиям неотрицательности: X1≥0, X2≥0, (38)
для которых функция: R=C1X1+C2X2 (39)
достигает максимума.
Решение.
Построим в системе прямоугольных координат Х1ОХ2 область допустимых решений задачи. Для этого, заменяя каждое из неравенств (37) равенством, строим соответствующую ему граничную прямую ai1x1+ai2x2≤bi (i=1,2,…,r) (рис.17).
рис. 17
Эта прямая делит плоскость Х1ОХ2 на две полуплоскости, для координат X1, X2 любой точки А одной полуплоскости выполняется неравенство: ai1x1+ai2x2≤bi , а для координат X1, X2 любой точки В другой полуплоскости противоположное неравенство: ai1x1+ai2x2≥bi .
Координаты любой точки граничной прямой удовлетворяют уравнению:
ai1x1+ai2x2=bi .
Для определения, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно "испытать" одну какую-либо точку (проще всего точку О (0,0 )). Если при подстановке ее координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже (рис.17) штриховкой.
|
|
Неравенствам X1≥0 и X2≥0 также соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.
На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.
Общая часть (пересечение) всех этих полуплоскостей будет представлять собой область допустимых решений данной задачи. При построении области допустимых решений в зависимости от конкретного вида системы ограничений (неравенств) на переменные может встретиться один из четырех случаев (рис.18):
Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет.
Область допустимых решений изображается одной точкой А, что соответствует единственному решению системы.
Область допустимых решений ограниченная, изображается в виде выпуклого многоугольника. Допустимых решений множество.
Область допустимых решений неограниченная, в виде выпуклой многоугольной области. Допустимых решений множество
|
|
Рис.18
Графическое изображение целевой функции R=C1X1+C2X2 при фиксированном значении R определяет прямую, а при изменении R - семейство параллельных прямых с параметром R.
Вектор, перпендикулярный ко всем этим прямым, показывает направление возрастания R .
Для всех точек, лежащих на одной из прямых, функция R принимает одно определенное значение, поэтому указанные прямые называются линиями уровня для функции R (рис.19).
Рис.19.
Задача отыскания оптимального решения системы неравенств (37), для которого целевая функция R (39) достигает максимума, геометрически сводится к определению в области допустимых решений точки, через которую пройдет линия уровня, соответствующая наибольшему значению параметра R.
Если область допустимых решений есть выпуклый многоугольник» то экстремум функции R достигается по крайней мере в одной из вершин этого многоугольника.
Если экстремальное значение R достигается в двух вершинах, то же экстремальное значение достигается в любой точке на отрезке, соединяющем эти две вершины. В этом случае говорят, что задача имеет альтернативный оптимум.
В случае неограниченной области экстремум функции R либо не существует, либо достигается в одной из вершин области, либо имеет альтернативный оптимум.
|
|
Пример.
Найти X1 и X2 , удовлетворяющие системе неравенств:
(40)
условиям неотрицательности: X1≥0, X2≥0, для которых функция R=2X1+3X2 достигает максимума.
Решение.
1. Заменим каждое из неравенств равенством и построим граничные прямые (рис.20)
рис.20
2. Определим полуплоскости, соответствующие данным неравенствам (40) путем "испытания" точки (0,0). Покажем направления полуплоскостей штриховкой (рис .21). С учетом неотрицательности X1 и Х2 получим область допустимых решений данной задачи в виде выпуклого многоугольника ОАВДЕ.
рис.21
3. В области допустимых решений находим оптимальное решение, строя вектор который показывает направление возрастания R (рис.21).
Оптимальное решение соответствует точке В, координаты которой можно определить либо графически, либо путем совместного решения двух уравнений, соответствующих граничным прямым АВ и ВД, т.е.
Х1 - Х2 = -4 ,
X1 + Х2 = 8 .
Ответ: X1=2, X2 = 6, Rmax=22.
Практическая часть
Номер варианта заданий соответствует списочному номеру студента
|
|
Задание № 1. Решить графически задачу линейного программирования
Вариант 1
Решить графически ЗЛП: Z = 4х1 + 6х2 ® min (max)
3х1 + х2 ³ 9
х1 +2х2 ³ 8
х1 + 6х2 ³ 12
х1 ³0, х2 ³0
Вариант 2
Решить графически ЗЛП: Z = 3х1 + 3х2 ® max (min)
х1 + х2 £ 8
2х1 – х2 ³ 1
х1 –2х2 £ 2
х1 ³ 0, х2 ³ 0
Вариант 3
Решить графически ЗЛП: F(x) = 2x1 – 5x2 → min(max)
х1 + 2х2 10
х1 + 2х2 2
2х1 + х2 10
х1 0, х2 0
Вариант 4
Решить графически ЗЛП: Z = x1 – 10x2 → min(max)
х1 – 0,5х2 ≥ 0
х1 – 5х2 ≥ 0
хi ³ 0, i = 1,2.
Вариант 5
Решить графически ЗЛП: Z= - 2x1 + 5x2 → min(max)
7х1 + 2х2 ≥ 14
5х1 +6х2 ≤ 3
3х1 + 8х2 ≥ 2
хi ³ 0, i = 1,2
Вариант 6
Решить графически ЗЛП: Z = 3х1 + х2 ® max(min)
х1 + х2 £ 8
2х1 – х2 ³ 1
х1 –2х2 £ 2
х1 ³ 0, х2 ³ 0
Вариант 7
Решить графически ЗЛП: Z = 2х1 + 3х2 ® max(min)
3х1 + 3х2 £ 6
х1 + х2 ³ 1
х1 ³ 0, х2 ³ 0
Вариант 8
Решить графически ЗЛП: Z = 2х1 + 3х2 ® max(min)
3х1 + 2х2 ³ 6
х1 + 4х2 ³ 4
х1 ³ 0, х2 ³ 0
Вариант 9
Решить графически ЗЛП: Z = х1 + 3х2 ® max(min)
х1 + 4х2 ³ 4
х1 + х2 £ 6
х2 £ 2
х1 ³ 0, х2 ³ 0
Вариант 10
Решить графически ЗЛП: Z = 3х1 – 4х2 ® max(min)
х1 – 2х2 ³ 6
х1 + 2х2 ³ 0
х1 £ 6
х1 ³ 0, х2 ³ 0
Вариант 11
Решить графически ЗЛП: Z = - 2х1 + 5х2 ® max(min)
7х1 + 2х2 ³ 14
3х1 + 8х2 ³ 24
5х1 + 6х2 £ 30
х1 ³ 0, х2 ³ 0
Вариант 12
Решить графически ЗЛП: Z = 3х1 – 2х2 ® max(min)
7х1 + 2х2 ³ 14
- х1 + 2х2 ³ 2
7х1 + 10х2 £ 28
х1 ³ 0, х2 ³ 0
Вариант 13
Решить графически ЗЛП: Z = 2х1 – 10х2 ® max(min)
х1 – х2 ³ 0
х1 – 5х2 ³ - 5
х1 ³ 0, х2 ³ 0
Вариант 14
Решить графически ЗЛП: Z = х1 – 10х2 ® max(min)
х1 – х2 ³ 0
х1 – 5х2 ³ - 5
х1 ³ 0, х2 ³ 0
Вариант 15
Решить графически ЗЛП: Z = х1 + х2 ® max(min)
х1 + 2х2 £ 10
х1 + 2х2 ³ 2
2х1 + х2 £ 10
х1 ³ 0, х2 ³ 0
Задание № 2. Составить экономико-математическую модель задачи. Решить задачу геометрически. Дать экономический анализ.
Вариант № 1
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 1 | 8 |
S2 | 1 | 4 | 20 |
S3 | 1 | 0 | 5 |
Прибыль (ден.ед) | 1 | 2 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 2
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 5 | 35 |
S2 | 2 | 1 | 16 |
S3 | 1 | 0 | 6 |
Прибыль (ден.ед) | 2 | 3 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 3
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 4 | 28 |
S2 | 1 | 1 | 10 |
S3 | 1 | 0 | 7 |
Прибыль (ден.ед) | 3 | 5 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 4
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 6 | 24 |
S2 | 1 | 2 | 12 |
S3 | 1 | 0 | 8 |
Прибыль (ден.ед) | 1 | 1 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 5
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 3 | 30 |
S2 | 2 | 3 | 36 |
S3 | 1 | 0 | 9 |
Прибыль (ден.ед) | 2 | 4 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 6
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 4 | 36 |
S2 | 3 | 2 | 38 |
S3 | 1 | 0 | 10 |
Прибыль (ден.ед) | 1 | 1 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 7
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 4 | 36 |
S2 | 5 | 3 | 44 |
S3 | 1 | 0 | 7 |
Прибыль (ден.ед) | 2 | 3 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 8
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 2 | 15 |
S2 | 1 | 3 | 21 |
S3 | 1 | 0 | 5 |
Прибыль (ден.ед) | 2 | 5 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 9
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 2 | 8 | 48 |
S2 | 1 | 2 | 14 |
S3 | 1 | 0 | 6 |
Прибыль (ден.ед) | 2 | 7 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 10
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 5 | 35 |
S2 | 2 | 3 | 27 |
S3 | 1 | 0 | 7 |
Прибыль (ден.ед) | 1 | 1 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 11
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 7 | 63 |
S2 | 2 | 1 | 22 |
S3 | 1 | 0 | 9 |
Прибыль (ден.ед) | 2 | 3 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 12
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 7 | 56 |
S2 | 2 | 1 | 21 |
S3 | 1 | 0 | 8 |
Прибыль (ден.ед) | 2 | 3 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 13
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 3 | 30 |
S2 | 3 | 1 | 26 |
S3 | 1 | 0 | 7 |
Прибыль (ден.ед) | 1 | 1 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 14
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 3 | 1 | 12 |
S2 | 1 | 2 | 9 |
S3 | 1 | 0 | 4 |
Прибыль (ден.ед) | 2 | 2 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Вариант № 15
Сырье | Продукция | Запасы сырья (в кг) | |
А | В | ||
S1 | 1 | 6 | 42 |
S2 | 1 | 1 | 12 |
S3 | 1 | 0 | 8 |
Прибыль (ден.ед) | 1 | 2 |
Предприятие выпускает два вида продукции А и В, для производства которых используется сырье трех видов S1, S2 и S3. При заданной технологии количество сырья, необходимое для изготовления единицы каждого из видов продукции, известно (см. таблицу):
Требуется составить план производства изделий А и В, обеспечивающий максимальную прибыль от готовой продукции.
Дата добавления: 2018-04-05; просмотров: 137; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!