[OR1-Modeling] Lecture 2: Linear Programming #2 Elements of a mathematical program (1)
0:01
Chúng ta đang nói về lập trình tuyến tính. Và lập trình tuyến tính là quá trình lập kế hoạch và giải quyết các chương trình tuyến tính.
We are talking about linear programming. And linear programming is the process of formulating and solving linear programs.
0:09
Vậy nên lập trình tuyến tính hoặc các chương trình tuyến tính, chúng được viết tắt là LP.
So either linear programming or linear programs, they are abbreviated as LP.
0:14
Vậy từ ngữ cảnh, bạn sẽ thấy liệu chúng ta đang nói về lập trình tuyến tính hay một chương trình.
So from the context, you will see whether we are talking about linear programming or a program.
0:21
Một chương trình tuyến tính thực sự là một loại chương trình toán học đặc biệt với một số loại thuộc tính tuyến tính.
A linear program is actually a special type of mathematical program with some kind of linear property.
0:29
Vậy trước tiên hãy giới thiệu một số khái niệm về các chương trình toán học trước khi chúng ta thu hẹp xuống các chương trình tuyến tính.
So let's first introduce some concepts of mathematical programs before we narrow down to linear programs.
0:39
Vậy cho mỗi chương trình toán học, chúng ta cần biết rằng
So for each mathematical program, we need to know that
0:42
nó được cấu thành từ ba yếu tố cơ bản, hàm mục tiêu, các ràng buộc, và các biến quyết định được gọi là như vậy.
it is composed by three basic elements, the objective function, the constraints, and the so-called decision variables.
0:52
Về cơ bản, một chương trình là để đưa ra một số quyết định.
Basically, a program is to make some decisions.
0:56
Vậy nên phải có một số biến, một số số lượng mà chúng ta muốn quyết định.
So there must be some variables, some quantities that we want to decide.
1:01
Số lượng sản xuất, giá của sản phẩm của bạn, mức tồn kho, và vân vân.
The production quantity, the price of your product, the inventory level, and so on and so on.
1:07
Vậy những x1, x2, cho đến xn, tất cả đều là số thực, và chúng ta gọi chúng là các biến quyết định.
So these x1, x2, up to xn, they are all real numbers, and we call them the decision variables.
1:16
Các biến mà bạn muốn chọn giá trị. Về cơ bản, bạn có một hàm mục tiêu.
The variables that you want to choose values. Basically, you have an objective function.
1:22
Bạn muốn tối thiểu hóa một số lượng nào đó. Ví dụ, bạn muốn tối thiểu hóa tổng chi phí để sản xuất sản phẩm của bạn.
You want to minimize some quantity. For example, you want to minimize the total cost for making your products.
1:30
Trong trường hợp đó, hàm mục tiêu f của bạn có thể chuyển đổi các quyết định x1, x2 cho đến xn thành một số lượng nào đó.
In that case, your objective function f can convert your decisions x1, x2 up to xn to some quantities.
1:40
Vậy ví dụ, x1, x2 có thể là số lượng sản xuất cho sản phẩm 1, sản phẩm 2, và vân vân.
So for example, x1, x2 may be the production quantity for your product 1, product 2, and so on.
1:46
F tính toán tổng chi phí bạn cần phải trả. Và sau đó có một số ràng buộc.
F calculates the total cost you need to pay. And then there are several constraints.
1:53
Bạn có gi của những giá trị x này nhỏ hơn hoặc bằng bi.
You have gi of these x values less than or equal to bi.
1:59
Thông thường, điều đó có nghĩa là tất cả các quyết định của bạn có thể được chuyển đổi thành một số lượng,
Typically, that means all your decisions may be converted to a quantity,
2:06
như lượng tài nguyên tiêu thụ cho một tài nguyên cụ thể, lượng thời gian bạn cần để thực hiện tất cả các sản xuất và vân vân.
like the resource consumption amount for a particular resource, the amount of time you need to spend to do all the productions and so on.
2:16
Và có thể có một số ràng buộc mà bạn cần phải đáp ứng.
And there may be some constraints that you need to satisfy.
2:20
Bạn bị giới hạn và bạn không thể làm bất cứ điều gì bạn thích vì tài nguyên có hạn, thời gian có hạn, hoặc có một số quy định.
You are limited and you cannot do whatever you like because the resource is limited, time is limited, or there are some regulations.
2:30
Được rồi, vì vậy về mặt kỹ thuật, chúng tôi thường sử dụng M và N để biểu thị số lượng ràng buộc và số lượng biến.
Okay, so technically we typically use M and N to denote the number of constraints and the number of variables.
2:39
Được rồi, không phải lúc nào cũng vậy, nhưng thường thì chúng tôi làm như vậy. Vậy khi chúng tôi nói rằng họ là n biến, chúng tôi có thể gọi chúng là x1, x2 cho đến xn.
Okay, not always, but typically we do that. So when we say they are n variables, we may call them x1, x2 up to xn.
2:48
Như chúng tôi đã đề cập, chúng là các giá trị quyết định có giá trị thực. Chúng là các giá trị thực.
As we mentioned, they are real valued decision values. They are real values.
2:53
Chúng tôi không nói về các giá trị phức, ảo
We don't talk about complex values, imaginary
2:56
các giá trị, vì chúng tôi cơ bản muốn áp dụng OR để thực hành các quyết định về hàng tồn kho, quyết định sản xuất, quyết định giá cả, quyết định đầu tư, và nhiều thứ khác.
values, because we basically want to apply OR to practice inventory decisions, production decisions, pricing decisions, investment decisions, and so on.
3:09
Tất cả những điều này đều là giá trị thực. Trong một số trường hợp, chúng tôi có thể muốn viết tắt các ký hiệu.
All these are real values. In some cases, we may want to abbreviate the notations.
3:16
Vì vậy, chúng tôi có thể viết x như một tập hợp của tất cả các biến quyết định này.
So we may write x as a collection of all these decision variables.
3:22
Trong trường hợp đó, chúng tôi sẽ nói x của bạn là một vector các biến quyết định hoặc một vector quyết định.
In that case, we would say your x is a vector of decision variables or a decision vector.
3:30
Ở đây, tôi cần dành một chút thời gian để nói về ký hiệu. khi bạn thấy các giá trị hoặc biến được đưa vào một cặp dấu ngoặc vuông như thế này.
Here, I need to spend some time to talk about the notation. when you see values or variables are put into a pair of square brackets like this.
3:42
Dấu ngoặc vuông có nghĩa là một ma trận.
Square brackets means a matrix.
3:45
Vì vậy, khi bạn đưa các thứ vào một ma trận như thế này,
So when you put things into a matrix like this,
3:50
thì bạn biết đây là một ma trận 3 x 2.
then you know this is a 3 by 2 matrix.
3:54
Vì vậy, nếu bạn chỉ có một cột, điều này trở thành, ví dụ, vector cột 3 x 1.
So if you only have one column, this becomes, for example, 3 by 1 column vector.
4:01
OK, vì vậy khi bạn đưa các thứ vào một cặp dấu ngoặc vuông, bất cứ điều gì bạn đưa vào, đó là kết quả.
OK, so when you put things into a pair of square brackets, whatever you put it, it is the outcome.
4:09
Dù đó là một vector cột hay một vector hàng, tùy thuộc vào bạn.
Either it's a column vector or it's a row vector, it's up to you.
4:14
Khi chúng ta nói về các vector trong lĩnh vực OR, thường thì chúng ta mặc định nói rằng tất cả các vector đều là vector cột.
When we are talking about vectors in the field of OR, typically we by default say all the vectors are column vectors.
4:23
OK, theo mặc định, tất cả các vector đều là vector cột.
OK, by default, all the vectors are column vectors.
4:28
Vì vậy, khi chúng ta muốn tạo ra vector x, chúng ta đưa tất cả các số này, tất cả các biến x này vào một cột để nó tạo thành một vector cột.
So when we want to create the vector x, we put all these numbers, all these x variables into a column so that it forms a column vector.
4:41
Nhưng vì nếu bạn luôn viết các vector vào các cột, nó sẽ chiếm nhiều không gian và đôi khi không dễ đọc.
But because if you always write vectors into columns, it's going to spend a lot of space and sometimes it's not so easy to read.
4:50
Vì vậy, thỉnh thoảng, chúng tôi có thể viết chúng và đưa chúng vào một cặp dấu ngoặc đơn.
So from time to time, we may write them and put them into a pair of parentheses.
4:57
OK, dấu ngoặc đơn. Vì vậy, nếu bạn viết điều gì đó trong dấu ngoặc đơn,
Okay, parentheses. So if you write something in parentheses,
5:03
Cơ bản, chúng tôi biết bạn đang nói về các vector, và chúng tôi biết bạn đang nói về các vector cột.
Basically, we know you are talking about vectors, and we know you are talking about column vectors.
5:09
Vì vậy, hai ký hiệu mà chúng tôi cung cấp thực sự là giống nhau.
So the two notations that we provide are actually identical.
5:14
Nếu chúng được đưa vào dấu ngoặc vuông, thì bạn cần đưa chúng vào các cột để bạn có một vector cột.
If they are put into square brackets, then you need to put them into columns so that you have a column vector.
5:24
Nhưng khi bạn đưa chúng vào một cặp dấu ngoặc đơn, thường thì chúng tôi viết nó như một hàng, nhưng bạn biết đó là một vector cột.
But when you put them into a pair of parentheses, typically we write it like a row, but you know it is a column vector.
5:34
OK, vì vậy đối với những hàm đó, f và g, tất cả chúng đều chuyển đổi
OK, so for those functions, f and g , all of them are converting
5:41
các biến quyết định đã kiếm được thành một số lượng mà bạn quan tâm.
earned decision variables into a quantity that you care.
5:46
Số lượng tiêu thụ tài nguyên, số người bạn cần thuê, tổng chi phí bạn cần trả, tổng số tiền bạn kiếm được, đại loại như vậy.
The amount of resource consumption, the number of people you need to hire, the total cost you need to pay, the total amount of money you earn, something like that.
5:54
Tất cả chúng đều, một lần nữa, là các hàm có giá trị thực.
They are all, again, real valued functions.
5:59
Cuối cùng, chúng ta biết rằng tất cả các biến này đều là giá trị thực, và đây là sự thật mặc định.
Finally, we know that all these variables are real values, and this is by default the fact.
6:07
Vì vậy, thường thì chúng ta không thực sự ghi lại xj trong tập hợp các số thực, vì điều này có phần thừa.
So typically we don't really write down xj in the set of real numbers, because this is somewhat redundant.
6:15
Vì vậy, chúng ta không làm điều đó thường xuyên. Đây có thể là trang cuối cùng để bạn thấy ký hiệu cụ thể.
So we don't do that typically. This may be the last page for you to see the specific notation.
6:23
Vì vậy, chúng tôi đã đề cập với bạn rằng nói chung, chúng tôi có thể viết
So we mentioned to you that in general, we may write
6:26
Vậy tại sao điều này lại chung chung? Điều này là bởi vì nếu bạn có một hàm tối đa hóa, nếu bạn muốn tối đa hóa tổng doanh thu của mình,
things into a minimization thing subject to some inequality constraints whose side is less than or equal to, whose direction is less than or equal to.
6:38
Về mặt toán học, điều này tương đương với việc tối thiểu hóa sự phủ định của tổng doanh thu của bạn.
So how come this is general? This is because if you have a maximization function, if you want to maximize your total revenue,
6:49
Vì vậy, bạn không cần phải nghiên cứu cách giải quyết các bài toán tối đa hóa về mặt kỹ thuật.
Mathematically, it is equivalent to minimize the negation of your total revenue.
6:55
Bạn chỉ cần học cách giải quyết các bài toán tối thiểu hóa.
So you don't need to study how to solve maximization problems technically.
7:00
Bởi vì tất cả các bài toán tối đa hóa có thể được diễn đạt lại dưới dạng một bài toán tối thiểu hóa.
You just need to learn how to solve minimization problems.
7:04
Vậy còn các ràng buộc bằng hoặc lớn hơn hoặc bằng thì sao?
Because all the maximization problems may be reformulated as a minimization problem.
7:11
Chà, cả hai có thể được diễn đạt bằng một hoặc nhiều ràng buộc nhỏ hơn hoặc bằng.
Then how about equality or greater than or equal to constraints?
7:15
Nếu bạn nói 3 lớn hơn 2, về cơ bản điều đó chỉ có nghĩa là âm 3 nhỏ hơn hoặc bằng âm 2.
Well, they both may be expressed by one or several less than or equal to constraints.
7:23
Được rồi, vậy khi bạn có một ràng buộc lớn hơn hoặc
If you say 3 is greater than 2, basically that just means negative 3 is less than or equal to negative 2.
7:30
bằng, tất cả những gì bạn cần làm là đảo ngược các bên để bạn có âm gi nhỏ hơn hoặc bằng âm bi.
Alright, so when you have a greater than or
7:33
Hầu như chúng giống nhau. Được rồi, vì vậy bạn không cần phải lo lắng cụ thể về các ràng buộc lớn hơn hoặc bằng.
equal to constraint, all you need to do is to flip the sides so that you get negative gi is less than or equal to negative bi.
7:45
Bạn chỉ cần tập trung vào nhỏ hơn hoặc bằng. Đối với sự bằng nhau, nó cũng tương tự như vậy.
Pretty much they are the same. Alright, so you don't need to specifically worry about greater than or equal to constraints.
7:52
Nếu bạn nói A bằng B, thì trong trường hợp đó, A nhỏ hơn hoặc bằng B,
you only need to focus on less than or equal to. For equality, it's pretty much the same thing.
7:57
và A lớn hơn hoặc bằng B cùng một lúc.
If you say A is equal to B, then in that case, A is less than or equal to B,
8:03
Vì vậy, bạn thay thế một ràng buộc bằng nhau bằng hai ràng buộc bất đẳng thức.
and A is greater than or equal to B at the same time.
8:06
Và tất nhiên, cái sau có thể thực sự được biểu diễn dưới dạng một ràng buộc nhỏ hơn hoặc bằng.
So you replace one equality constraint by two inequality constraints.
8:11
Vì vậy, như một ví dụ, giả sử chúng ta muốn tối đa hóa x1 trừ x2.
And of course, the latter may actually be represented as a less than or equal to constraint.
8:17
Bạn chỉ cần tối thiểu hóa âm x1 cộng x2. Bạn chỉ cần đảo ngược dấu.
So as an example, suppose we want to maximize x1 minus x2.
8:23
Và sau đó, nếu bạn phải tuân theo một ràng buộc
You just need to minimize negative x1 plus x2. You just flip the sign.
8:29
Và sau đó, nếu bạn bị ràng buộc bởi một điều kiện
And then, if you are subject to a constraint
8:33
nói rằng các giá trị này phải lớn hơn hoặc bằng âm 3, bạn có thể thấy rằng nó được thay thế bằng một điều kiện tương đương nhỏ hơn hoặc bằng.
saying that these values must be greater than or equal to negative 3, you may see that it is replaced by an equivalent less than or equal to constraint.
8:45
Giá trị âm 3 của bạn trở thành 3, giá trị âm 2 của bạn trở thành 2, giá trị 1 của bạn trở thành âm 1.
Your negative 3 becomes 3, your negative 2 becomes 2, your 1 becomes negative 1.
8:51
Bạn chỉ cần đảo dấu. Cuối cùng, nếu bạn có một ràng buộc bằng nhau, bạn thay thế nó bằng hai ràng buộc nhỏ hơn hoặc bằng, theo cách trên.
You just flip the sign. And lastly, if you have an equality constraint, you replace it by two less than or equal to constraints, according to the above way.
9:03
Vì vậy, bạn không cần phải lo lắng quá nhiều về
So pretty much, you don't need to really worry too much about
9:07
việc tối đa hóa lớn hơn hoặc bằng hoặc các ràng buộc bằng nhau, vì chúng có thể được chuyển đổi, biến đổi thành định dạng cụ thể mà bạn quan tâm.
maximization greater than or equal to or equality constraints, because they may all be converted, transformed into the specific format that you care about.